Russian versionEnglish version   
Volume 12   Issue 1   Year 2017
Ruslan K. Tetuev, Maxim I. Pyatkov, Anton N. Pankratov

Parallel algorithm for global alignment of long aminoacid and nucleotide sequences

Mathematical Biology & Bioinformatics. 2017;12(1):137-150.

doi: 10.17537/2017.12.137.



  1. Oplachko E.S., Ustinin D.M., Ustinin M.N. Cloud Computing Technologies and their Application in Problems of Computational Biology. Mathematical Biology and Bioinformatics. 2013;8(2):449-466 (in Russ.). doi: 10.17537/2013.8.449
  2. Daugelaite J., O'Driscoll A., Sleator R.An Overview of Multiple Sequence Alignments and Cloud Computing in Bioinformatics. ISRN Biomathematics. 2013;2013:1-14. doi: 10.1155/2013/615630
  3. Camacho C., Coulouris G., Avagyan V., Ma N., Papadopoulos J., Bealer K., Madden T.L.BLAST+: architecture and applications. BMC Bioinformatics. 2009;10:421. doi: 10.1186/1471-2105-10-421
  4. Needleman S., Wunsch C.A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 1970;48(3):443-453. doi: 10.1016/0022-2836(70)90057-4
  5. Pankratov A., Pyatkov M., Tetuev R., Nazipova N., Dedus F.F. Search for Extended Repeats in Genomes Based on the Spectral-Analytical Method. Mathematical Biology and Bioinformatics. 2012;7(2):476-492 (in Russ.). doi: 10.17537/2012.7.476
  6. Pyatkov M.I., Pankratov A.N. SBARS: fast creation of dotplots for DNA sequences on different scales using GA-,GC-content. Bioinformatics. 2014;30(12):1765-1766. doi: 10.1093/bioinformatics/btu095
  7. NCBI BLAST: web site. (accessed 14 April 2017).
  8. Rice P., Longden I., Bleasby A. EMBOSS: The European Molecular Biology Open Software Suite. Trends in Genetics. 2000;16(6):276-277. doi: 10.1016/S0168-9525(00)02024-2
  9. Gotoh O. An improved algorithm for matching biological sequences. J. Mol. Biol. 1982;162(3):705-708. doi: 10.1016/0022-2836(82)90398-9
  10. Press W., Teukolsky S., Vetterling W., Flannery B. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press; 2007. 1256 p.
  11. Myers E., Miller W. Optimal alignments in linear space. Comput. Appl. Biosci. 1988;4(1):11-17. doi: 10.1093/bioinformatics/4.1.11
  12. Hirschberg D.S. A linear space algorithm for computing maximal common subsequences. Communications of the ACM. 1975;18(6):341-343. doi: 10.1145/360825.360861
  13. Altschul S., Gish W., Miller W., Myers E., Lipman D. Basic local alignment search tool. J. Mol. Biol. 1990;215:403-410. doi: 10.1016/S0022-2836(05)80360-2
  14. 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(45):337-375. doi: 10.1007/s00453-006-1217-y
  15. Chakraborty A., Bandyopadhyay S. FOGSAA: Fast Optimal Global Sequence Alignment Algorithm. Scientific Reports. 2013(3):1746. doi: 10.1038/srep01746
  16. Loving J., Hernandez Y., Benson G. BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm. Bioinformatics. 2014;30(22):3166-3173. doi: 10.1093/bioinformatics/btu507
  17. Farrar M. Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics. 2007;23(2):156-161. doi: 10.1093/bioinformatics/btl582
  18. Huson D., Chao Xie C. A poor man’s BLASTX - high-throughput metagenomic protein database search using PAUDA. Bioinformatics. 2014;30(1):38-39. doi: 10.1093/bioinformatics/btt254
  19. 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(26):683-686. doi: 10.1093/bioinformatics/btq017
  20. Blom J., Jakobi T., Doppmeier D., Jaenicke S., Kalinowski J., Stoye J., Goesmann A. Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming. Bioinformatics. 2011(27):1351-1358. doi: 10.1093/bioinformatics/btr151
  21. Levenshtein V.I. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady. 1966;10:707–10.
  22. Dayhoff M., Schwartz R., Orcutt B. A model of Evolutionary Change in Proteins. Atlas of protein sequence and structure. 1978;5:345-358.
  23. Henikoff S., Henikoff G. Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. USA. 1992;89(22):10915-10919. doi: 10.1073/pnas.89.22.10915
  24. Hamming R.W. Error Detecting and Error Correcting Codes. The Bell System Technical Journal. 1950;29(2):147-160. doi: 10.1002/j.1538-7305.1950.tb00463.x
  25. Xuhua X. In: Bioinformatics and the Cell. Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. Springer, 2007:124-127.
  26. Ibarra I., Melo F. Interactive software tool to comprehend the calculation of optimal sequence alignments with dynamic programming. Bioinformatics. 2010;26(13):1664-1669. doi: 10.1093/bioinformatics/btq252
Table of Contents Original Article
Math. Biol. Bioinf.
doi: 10.17537/2017.12.137
published in Russian

Abstract (rus.)
Abstract (eng.)
Full text (rus., pdf)


  Copyright IMPB RAS © 2005-2019