Улучшение результатов работы MGRA2 и разработка алгоритма для решения проблемы медианы с событиями вставок и удалений

На данный момент из всего множества алгоритмов, которые реконструируют предковые геномы, существует два явных лидера GASTS и MGRA. Если первое программное средство пытается итеративно решать проблему медианы с помощью, так называемых адекватных подграфов, то второе программное средство пытается решить эту проблему используя максимум доступной информации с помощью модели T-консистентных цветов и множественного breakpoint графа. Удивительно то, что адекватные подграфы размера 1, это тоже самое, что хорошие циклы/пути в терминах MGRA. Дальнейшее изучение этой проблемы показало, что обобщение адекватных подграфов размера 2 с помощью T-конситентых цветов, улучшает качество реконструкции и позволяет достигать наилучших результатов.
Основной целью проекта является -- аккуратное обобщение адекватных подграфов в терминах модели MGRA, а так же разработка дополнительных эвристик, которые базируются на данном обобщение. Побочным эффектом данной деятельности должен получиться первый в своем роде median solver для данных с событиями вставок и удалений.

В ходе выполнения проекта студент познакомиться с такими понятиями как k-break, DCJ, нахождение кратчайшего парного расстония между геномами, проблемой медианы. Узнает подходы, которые используют современные программные средства при восстановление предковых геномов и истории перестроек, а так же детально узнает, как устроенна реализация двух лидирующих программных средств подобного рода - MGRA 2 и GASTS.
По итогам работы хочется получить работающий алгоритм, сравнительный анализ существующих подходов и нового алгоритма на симуляционных данных, а так же получить результат работы алгоритма на реальных биологических данных.