Abstract:
A parallel algorithm is developed for the global alignment of long DNA and protein sequences. The algorithm uses an arbitrary substitution matrix. An affine internal and end gap penalty systems might be set up separately for each of the two sequences. The possibility to control the choice of an optimal alignment from the set of alternative ones is implemented. The two parameters of the parallel algorithm which are called grid steps were introduced. They are used to split the global alignment matrix into blocks of specified size. The analysis of these parameters was performed in order to obtain optimal values that reduce either time complexity or memory complexity of the algorithm. It is shown that when using the block sizes that provide lowest memory complexity, the algorithm allows to align two long sequences of length L using the memory of size O(L4/3). It is shown that the algorithm is well scaled on multi-core systems, reaching superlinear execution time acceleration. The algorithm is implemented as a high-performance parallel web application in JavaScript and is freely available at http://sbars.impb.ru/aligner.html.
Citation:
R. K. Tetuev, M. I. Pyatkov, A. N. Pankratov, “Parallel algorithm for global alignment of long aminoacid and nucleotide sequences”, Mat. Biolog. Bioinform., 12:1 (2017), 137–150
\Bibitem{TetPyaPan17}
\by R.~K.~Tetuev, M.~I.~Pyatkov, A.~N.~Pankratov
\paper Parallel algorithm for global alignment of long aminoacid and nucleotide sequences
\jour Mat. Biolog. Bioinform.
\yr 2017
\vol 12
\issue 1
\pages 137--150
\mathnet{http://mi.mathnet.ru/mbb285}
\crossref{https://doi.org/10.17537/2017.12.137}
Linking options:
https://www.mathnet.ru/eng/mbb285
https://www.mathnet.ru/eng/mbb/v12/i1/p137
This publication is cited in the following 4 articles:
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