Parallel algorithm for global alignment of long aminoacid and nucleotide sequences

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 $\mathrm{O}(L^{4/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.