Аннотация:
Разработан параллельный алгоритм для глобального выравнивания протяженных последовательностей. Алгоритм использует произвольную матрицу замен. Аффинная система штрафов за внутренние и концевые разрывы в выравнивании может быть задана раздельно для каждой последовательности. Реализована возможность управления выбором оптимального выравнивания из множества альтернативных. Параметрами параллельного алгоритма являются шаги сетки, которая разбивает матрицу глобального выравнивания на блоки. Проведены исследования и выработаны критерии выбора этих параметров как для оптимизации использования памяти, так и по сокращению времени работы алгоритма. Показано, что при выборе размеров блоков, обеспечивающих оптимизацию сложности по памяти, алгоритм позволяет выравнивать протяженные последовательности длины L, используя объем памяти O(L4/3). Дополнительно показано, что алгоритм идеально масштабируется на многоядерных системах, демонстрируя суперлинейное ускорение. Алгоритм реализован в виде высокопроизводительного параллельного веб-приложения на языке JavaScript, доступного по адресу http://sbars.impb.ru/aligner.html.
Работа выполнена при поддержке РФФИ, проекты №15-29-07063 и №16-01-00692.
Материал поступил в редакцию 14.03.2017, опубликован 13.04.2017
Тип публикации:
Статья
УДК:
575.112:004
Образец цитирования:
Р. К. Тетуев, М. И. Пятков, А. Н. Панкратов, “Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей”, Матем. биология и биоинформ., 12:1 (2017), 137–150
\RBibitem{TetPyaPan17}
\by Р.~К.~Тетуев, М.~И.~Пятков, А.~Н.~Панкратов
\paper Параллельный алгоритм глобального выравнивания протяжённых аминокислотных и нуклеотидных последовательностей
\jour Матем. биология и биоинформ.
\yr 2017
\vol 12
\issue 1
\pages 137--150
\mathnet{http://mi.mathnet.ru/mbb285}
\crossref{https://doi.org/10.17537/2017.12.137}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mbb285
https://www.mathnet.ru/rus/mbb/v12/i1/p137
Эта публикация цитируется в следующих 4 статьяx:
Oleg Zverkov, Alexandr Seliverstov, Gregory Shilovsky, “Alignment of a Hidden Palindrome”, Math.Biol.Bioinf., 19:2 (2024), 427
S.A. Makhortykh, Proceedings of the International Conference “Mathematical Biology and Bioinformatics”, 9, Proceedings of the International Conference “Mathematical Biology and Bioinformatics”, 2022
S. A. Makhortykh, L. I. Kulikova, A. N. Pankratov, R. K. Tetuev, “Generalized Spectral-Analytical Method and Its Applications in Image Analysis and Pattern Recognition Problems”, Pattern Recognit. Image Anal., 29:4 (2019), 621
A.N. Pankratov, R.K. Tetuev, M.I. Pyatkov, Proceedings of the International Conference “Mathematical Biology and Bioinformatics”, 7, Proceedings of the International Conference “Mathematical Biology and Bioinformatics”, 2018
Цитирование в формате AMSBIB
Обратная связь: