Поиск возможностей распараллеливания в программах множественного выравнивания и сравнение эффективностей параллельных реализацийдипломная работа (Специалист)
Аннотация:Алгоритмы множественного выравнивания представляют собой инструмент для установления функциональных, структурных или эволюционных взаимосвязей между биологическими последовательностями. несмотря на то, что задача была сформулирована более 20 лет назад, она не утрачивает своей актуальности, ведь набор алгоритмов множественного выравнивания это важный инструмент, используемый биологами повсеместно. Сложность задачи множественного выравнивания обуславливается экспоненциальным ростом времени счёта не параллельной программы либо увеличения числа биологических последовательностей, либо их длины. Даже использование эвристик в алгоритме множесвенного выравнивания даёт NP-полную задачу. Поэтому актуальна задача применения высокопроизводительных вычислений, и параллельная реализация существующих алгоритмов для ускорения времени счёта программ множественного выравнивания.
В работе рассмотрены наиболее популярные параллельные алгоритмы множественного выравнивания, дана оценка сложности, проведены тесты производительности и качества выравнивания. Осуществлена реализация попарного выравнивания последовательностей все-со-всеми в алгоритме ClustalW2 с помощью технологии MPI.