Адаптация алгоритма множественного выравнивания последовательностей библиотеки SeqAn для работы с глубокими выравниваниями
Высокое качество множественного выравнивания последовательностей чрезвычайно важно при решении многих биологических проблем. Современная биология ставит задачу множественного выравнивания тысячей последовательностей. Все существующие подходы можно условно разделить на две группы: 1) методы, основанные на рафинированности (итеративно перестраивающие получающееся выравнивание с целью устранения ошибок), и 2) методы, основанные на конситентности (увеличивающие вес отдельных попарных выравниваний, которые консистентны с попарными выравниваниями других последовательностей). Однако все инструменты, которые сегодня в состоянии оперировать большими наборами данных, являются рафинирующими. Несмотря на лучшее качество, методы, основанные на консистентности, не применяются для глубоких выравниваний ввиду их неприемлемо большого времени выполнения.
Данная работа посвящена развитию основанного на консистентности алгоритма SeqAn::T-Coffee с целью уменьшения времени выполнения с сохранением высокого качества выравнивания. Были выявлены узкие места исходного алгоритма и предложены следующие пути их устранения. 1) При построении библиотек попарного выравнивания использовать окаймленное выравнивание (banded-alignment). 2) При расширении триплетов (triplet extension) обрабатывать последовательности только внутри небольших кластеров иерархического дерева. 3) Также при обработке триплетов предлагается не добавлять новые ребра в граф выравнивания, что существенно влияет на производительность завершающего шага progressive alignment.
В результате удалось многократно сократить время выполнения программы с незначительной потерей в качестве (в 32 раза быстрее с падением в качестве на 1% для 200 последовательностей по сравнению с полной стратегией). Примечательно, что удалось добиться лучшего качества чем у Clustal Omega (показывавшего прежде самые лучшие результаты по времени и качеству среди прочих инструментов) при 1000 последовательностях на тестовых данных. Результаты внедрены в библиотеку SeqAn.