Comments | ru_algorithms: Поиск консенсуса.

potan in ru_algorithms

Поиск консенсуса.

Dec 05, 2013 11:31

Не могу найти подходящий алгоритм для следующей задачи ( Read more... )

Comments 16

spamsink December 5 2013, 07:45:07 UTC

Это называется Planted Motif Search, посмотрите.

potan December 5 2013, 08:31:49 UTC

Thanks!
Правда, там расстояние Хемминга - посмотрю, можно ли что-нибудь адаптировать.

nivanych December 6 2013, 09:20:56 UTC

Видимо, можно для любого метрического пространства...

potan December 6 2013, 10:08:50 UTC

Для векторного пространства существуют простые способы.
В общем виде кроме метрики нужно еще что-то типа возможности генерировать точки "между" двумя данными.

Thread 6

urod December 5 2013, 09:44:45 UTC

Первое, что приходит в голову - это или simulated annealing, или генетические алгоритмы.

Но у меня ощущение, что если строка локально оптимальна (нет улучшающей элементарной операции), то она и глобально оптимальна. Если удастся доказать эту гипотезу, то начинаем с любой строки и делаем любые улучшающие операции, пока они не закончатся.

PS: а строки испорчены независимо друг от друга, или есть филогенетическое дерево?

potan December 5 2013, 10:05:33 UTC

Thanks!
Я уже начал смотреть в стороны генетических алгоритмов. По парным выравниваниям генерировать "детей", а потом отбирать тех, среднее расстояние до которых по выборке минимально.

Независимо. Вероятностная модель фиксирована или медленно меняется.

urod December 5 2013, 09:59:15 UTC

PPS: а ещё погуглите на ancestral genome reconstruction algorithm, см. например эту статью

http://www.biomedcentral.com/1471-2105/13/S19/S4

potan December 6 2013, 10:12:26 UTC

Thanks!

kray_zemli December 5 2013, 18:01:42 UTC

У биологов есть программы для "выравнивания" (сортировки по совпадениям) похожих генетических последовательностей. Покопайте туда.

potan December 6 2013, 10:12:06 UTC

Да, я знаю. Но там консенсус строят с учетом филогенетического дерева, которое предпологается бинарным. Или используют множественное выравнивание, сложность которого очень быстро растет.

huzhepidarasa December 6 2013, 07:50:50 UTC

n-way diff, который используется в системах контроля версий. Обычно n == 3, но не обязательно, можно больше. Каждому фрагменту сопоставляете вес (сколько раз он встретился). Как-то так.

potan December 6 2013, 10:15:50 UTC

Thanks!
Думал, что в системах контроля версий n==2. Интересно посмотреть :-).

huzhepidarasa December 6 2013, 15:43:47 UTC

Когда надо слить две независимо изменявшихся ветки, n == 3 совершенно необходимо, иначе непонятно, кто чего менял.