Main Article Content
The most general model of a pairwise global alignment with the possibility of aligning long sequences is considered. The model features are alignment of sequences in different alphabets including nucleotides and amino acids, alternative alignments with the same score, predefined or fully customazible scoring matrix and gap penalty systems for each sequence including end gap penalties.
Developed versatile parallel algorithm for global alignment is based on the Needleman-Wunsch algorithm with an arbitrary scoring matrix and Gotoh algorithm for the affine system of penalties for gaps. The main features of the algorithm include optimal memory consumption and parallel computation. It is proved that algorithm can align two sequences of length L in memory space O(L^4/3).
Pyatkov M.I., Pankratov A.N. SBARS: fast creation of dotplots for DNA sequences on different scales using GA-, GC- content. // Bioinformatics. - 2014. - №12 (30) - P. 1765—1766.
Gotoh O. An improved algorithm for matching biological sequences. // Journal of Molecular Biology. – 1982. - №3 (162) - P. 705–708.
Myers E.W., Miller W. Optimal alignments in linear space. // Computer Applications in the Biosciences. – 1988. - №1 (4) – P. 11–17.
Driga A., Lu P., Schaeffer J., Szafron D., Charter K., Parsons I. FastLSA: A Fast, Linear-Space, Parallel and Sequential Algorithm for Sequence Alignment. // Algorithmica. – 2006. - №3 (45) – P. 337-375.
Galvez S., Diaz D., Hernandez P., Esteban F.J., Caballero J.A., Dorado G. Next-generation bioinformatics: using many-core processor architecture to develop a web service for sequence alignment. // Bioinformatics. – 2010. - №5 (26) – P. 683-686.
Tetuev R.K., Pyatkov M.I., Pankratov A.N. Parallel algorithm for global alignment of long aminoacid and nucleotide sequences. // Mathematical Biology and Bioinformatics. – 2017. - №1 (12) – P. 137-150.