Генетическая изменчивость является предпосылкой эволюционных изменений. При ее отсутствии никакое последующее видообразование не может быть достигнуто. Генетическая изменчивость в конечном итоге вся генерируется мутациями [1] .
Такие генные мутации, как инверсии, инсерции и делеции в ряду с заменой оснований являются самыми распространенными. Известно, что инверсии оказывают влияние на архитектуру генома как прокариот, так и эукариот, на поведение некоторых насекомых, половую изоляцию и в конечном счете на видообразование [2]. Многие бактерии имеют геном меньше, чем у своих предков из-за многочисленных инсерций, похожая ситуация наблюдается с беспозвоночными (насекомые) и многими позвоночными (рыбы, амфибии, птицы, млекопитающие) [3]. В процессе эволюции происходят вставки в последовательность ДНК, но чаще и намного масштабней происходят делеции. У птиц, возможно, из-за делеций было утрачено чуть менее, чем 300 генов. Таким образом, инверсии и индел вносят немалый вклад в эволюцию, создают «субстрат» для нее и в то же время являются ее инструментом [4].
На сегодняшний день существует два типа выравнивания: парное (сравниваются две последовательности) и множественное (более двух последовательностей). Алгоритмы, чаще используемого множественного выравнивания, не могут учесть инверсии и транслокации. Эти мутации считаются как сумма ин- серций и делеций или же просто делеции. Схожая картина и с парным выравниванием (прогрессивное выравнивание основано на итерации алгоритмов парного выравнивания). На данный момент не существует методов, которые являлись бы достаточно чувствительными к инверсиям и транслокациям.
В данной работе описывается алгоритм, позволяющий детектировать инверсии на основании отношения вероятности их возникновения к вероятности возникновения индел. Так как детекция инверсий через перебор имеет высокую вычислительную сложность, был предложен эвристический алгоритм, который не создает дополнительные копии последовательности и производит поиск инверсий параллельно.
Целью выпускной курсовой работы является разработка нового метода вычисления гомологии геномных последовательностей, который основан на метрике, учитывающей такие мутации ДНК, как делеция, инверсия и вставка.
В соответствии с поставленной целью были выдвинуты следующие задачи:
• Проанализировать существующие метрики построения филогенетических деревьев и выявить их недостатки;
• Разработать новую метрику гомологии геномных последовательностей, учитывающую выявленные на предыдущем этапе недостатки;
• Написать программу для парного выравнивания, учитывающего возможность возникновения инверсий.
Преимуществом разработанной программы выравнивания являются гибкость, так как ее основу можно легко заменить на любой из имеющихся алгоритмов выравнивания, и быстродействие, поскольку алгоритм не перебирает все возможные решения, а пользуется эвристикой.
Разработанный алгоритм позволяет проводить парное выравнивание нуклеотидных последовательностей с учетом возможности возникновения инверсии.
Следующим этапом развития проекта является его валидация на реальных геномных последовательностях, взятых из базы данных NCBI.
