Локальное выравнивание последовательностей с использованием внутрипроцессорного параллелизма

Целью проекта является изучение потенциала алгоритма полулокального выравнивания seaweed, а именно решения задачи поиска выравниваний, на которых достигаются оптимальные значения задачи наибольшей общей подпоследовательности для двух подстрок входных данных.

В ходе проекта реализован параллельный divide-and-conquer алгоритм seaweed решения задачи полулокального выравнивания в качестве учебной задачи. Помимо этого в ходе проекта получены новые теоретические результаты: доказательство необходимого инварианта для жадного алгоритма/branch-and-bound алгоритма поиска путей в графе, соответствующих оптимальным выравниваниям.

На основании полученного результата предложен и реализован эффективный по памяти алгоритм восстановления решения в случае глобального выравнивания для результатов алгоритма seaweed. В качестве дальнейшего исследования интересны вопросы решения задачи в случае локального выравнивания, в случае выравнивания с афинным штрафом за гэп, возможность исправления ошибок и т.п.