Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей

Разработан параллельный алгоритм для глобального выравнивания протяженных последовательностей. Алгоритм использует произвольную матрицу замен. Аффинная система штрафов за внутренние и концевые разрывы в выравнивании может быть задана раздельно для каждой последовательности. Реализована возможность управления выбором оптимального выравнивания из множества альтернативных. Параметрами параллельного алгоритма являются шаги сетки, которая разбивает матрицу глобального выравнивания на блоки. Проведены исследования и выработаны критерии выбора этих параметров как для оптимизации использования памяти, так и по сокращению времени работы алгоритма. Показано, что при выборе размеров блоков, обеспечивающих оптимизацию сложности по памяти, алгоритм позволяет выравнивать протяженные последовательности длины $L$, используя объем памяти $\mathrm{O}(L^{4/3})$. Дополнительно показано, что алгоритм идеально масштабируется на многоядерных системах, демонстрируя суперлинейное ускорение. Алгоритм реализован в виде высокопроизводительного параллельного веб-приложения на языке JavaScript, доступного по адресу http://sbars.impb.ru/aligner.html.