Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей
Тетуев Руслан Курбанбиевич, Пятков Максим Иванович, Панкратов Антон Николаевич
Институт математических проблем биологии РАН – филиал ИПМ им. М.В.Келдыша РАН, Пущино, Московская область, Россия
Аннотация. Разработан параллельный алгоритм для глобального выравнивания протяженных последовательностей. Алгоритм использует произвольную матрицу замен. Аффинная система штрафов за внутренние и концевые разрывы в выравнивании может быть задана раздельно для каждой последовательности. Реализована возможность управления выбором оптимального выравнивания из множества альтернативных. Параметрами параллельного алгоритма являются шаги сетки, которая разбивает матрицу глобального выравнивания на блоки. Проведены исследования и выработаны критерии выбора этих параметров как для оптимизации использования памяти, так и по сокращению времени работы алгоритма. Показано, что при выборе размеров блоков, обеспечивающих оптимизацию сложности по памяти, алгоритм позволяет выравнивать протяженные последовательности длины
L, используя объем памяти O(
L4/3). Дополнительно показано, что алгоритм идеально масштабируется на многоядерных системах, демонстрируя суперлинейное ускорение. Алгоритм реализован в виде высокопроизводительного параллельного веб-приложения на языке JavaScript, доступного по адресу
http://sbars.impb.ru/aligner.html.
Ключевые слова: глобальное выравнивание, аффинная система штрафов, концевые вставки, параллельные вычисления, суперлинейное ускорение.