Алгоритмическая задача про ДНК генеалогию

Решил перепостить сообщение уважаемого Павла Б. о алгоритмической задаче про ДНК генеалогию.

как известно, в алгоритмах я не особо силён. я сейчас попытаюсь описать некую задачу, а Вы помогите мне её сформулировать формально и предложить алгоритм решения, ладно?Причем не обязательно оптимальный алгоритм — мы тут не теоремки доказываем :)Сделал человек ДНК тест, получил большой файл с RAW results — со всеми мутациями.Сравниваем его с результатами другого человека — получаем некий набор одинаковых участков ДНК, каждый из которых характеризуется позицией (у каждой мутации есть некий адрес) и длиной.Общие участки ДНК между этими двумя людьми скорее всего принадлежали ДНК их общего предка. Этот общий предок был неизвестно сколько поколений назад, по какой линии и какая у него была фамилия, Y-DNA гаплогруппа и mt-DNA гаплогруппа (Y-DNA гаплогруппа — некое свойство, которое передается только по прямой мужской линии, у женщин его нет, mt-DNA гаплогруппа — свойство передающееся только по прямой женской линии).Если с кем то еще есть среди общих участвков ДНК участки, пересекающиеся с найденными выше пересечениями, можно предположить, что у всех трех есть некий общий предок, которому эти общие участки принадлежат (пока, для простоты мы считаем, что общий предок у двух людей один — т.е. родство только по одной линии, что для ашкеназов вообще то ВСЕГДА неправда).Теперь задача — если есть много таких данных, про многих людей — у кого с кем какие участки ДНК общие, у кого какие фамилия отца, матери, Y-DNA гаплогруппа и mt-DNA гаплогруппа — можно ли попытаться восстановить дерево общих предков?

От себя замечу, что это проблема решается тривиально с помощью любого из алгоритмов фазирования, и визуализация с помощью алгоритмов qpGraph.
Другой вариант (который мне представляется более разумным — это сравнение трех файлов на предмет наличия сегментов, которых мы будем считать общими по происхождению (так называемые IBD сегменты). Но здесь также как и в первом случае понадобится фазирование данных, т.к. в любом случае HIR-сегменты здесь менее информативны. Пример реализации алгоритмов можно подсмотреть в открытом коде типа открытого кода программы Beagle (так поступили например в  23andme) или даже в Plink. Затем можно представить найденные IBD-сегментов в виде попарных матчей. Далее трансформируем матрицу попарных матчей в сеть/network.  Затем находим в сети наиболее оптимальные штейнеровские деревья, и т.д.
Advertisements

Добавить комментарий

Please log in using one of these methods to post your comment:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s