{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:01:10Z","timestamp":1761807670665},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Pairwise sequence alignment methods are widely used in biological research. The increasing number of sequences is perceived as one of the upcoming challenges for sequence alignment methods in the nearest future. To overcome this challenge several GPU (Graphics Processing Unit) computing approaches have been proposed lately. These solutions show a great potential of a GPU platform but in most cases address the problem of sequence database scanning and computing only the alignment score whereas the alignment itself is omitted. Thus, the need arose to implement the global and semiglobal Needleman-Wunsch, and Smith-Waterman algorithms with a backtracking procedure which is needed to construct the alignment.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In this paper we present the solution that performs the alignment of every given sequence pair, which is a required step for progressive multiple sequence alignment methods, as well as for DNA recognition at the DNA assembly stage. Performed tests show that the implementation, with performance up to 6.3 GCUPS on a single GPU for affine gap penalties, is very efficient in comparison to other CPU and GPU-based solutions. Moreover, multiple GPUs support with load balancing makes the application very scalable.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The article shows that the backtracking procedure of the sequence alignment algorithms may be designed to fit in with the GPU architecture. Therefore, our algorithm, apart from scores, is able to compute pairwise alignments. This opens a wide range of new possibilities, allowing other methods from the area of molecular biology to take advantage of the new computational architecture. Performed tests show that the efficiency of the implementation is excellent. Moreover, the speed of our GPU-based algorithms can be almost linearly increased when using more than one graphics card.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-12-181","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T18:19:25Z","timestamp":1309285165000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":47,"title":["Protein alignment algorithms with an efficient backtracking routine on multiple GPUs"],"prefix":"10.1186","volume":"12","author":[{"given":"Jacek","family":"Blazewicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Frohmberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Kierzynka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erwin","family":"Pesch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawel","family":"Wojciechowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,5,20]]},"reference":[{"issue":"3","key":"4596_CR1","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S Needlemana","year":"1970","unstructured":"Needlemana 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\u20133. 48: 443\u201353 48: 443-53 10.1016\/0022-2836(70)90057-4","journal-title":"J Mol Biol"},{"key":"4596_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith T, Waterman M: Identification of Common Molecular Subsequences. Journal of Molecular Biology 1981, 147: 195\u201397. 10.1016\/0022-2836(81)90087-5","journal-title":"Journal of Molecular Biology"},{"key":"4596_CR3","volume-title":"Computational Genome Analysis. Springer","author":"R Deonier","year":"2005","unstructured":"Deonier R, Tavare C, Waterman M: Computational Genome Analysis. Springer. 2005."},{"key":"4596_CR4","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: An Algorithmic Approach. The MIT Press","author":"P Pevzner","year":"2000","unstructured":"Pevzner P: Computational Molecular Biology: An Algorithmic Approach. The MIT Press. 2000."},{"key":"4596_CR5","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.compbiolchem.2009.04.005","volume":"33","author":"J Blazewicz","year":"2009","unstructured":"Blazewicz J, Bryja M, Figlerowicz M, Gawron P, Kasprzak M, Kirton E, Platt D, Przybytek J, Swiercz A, Szajkowski L: Whole genome assembly from 454 sequencing output via modified DNA graph concept. Computational Biology and Chemistry 2009, 33: 224\u2013230. 10.1016\/j.compbiolchem.2009.04.005","journal-title":"Computational Biology and Chemistry"},{"issue":"4","key":"4596_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L Wang","year":"1994","unstructured":"Wang L, Jiang T: On the complexity of multiple sequence alignment. J Comput Biol 1994, 1(4):337\u2013348. 10.1089\/cmb.1994.1.337","journal-title":"J Comput Biol"},{"issue":"3","key":"4596_CR7","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.sbi.2008.03.007","volume":"18","author":"J Pei","year":"2008","unstructured":"Pei J: Multiple protein sequence alignment. Current Opinion in Structural Biology 2008, 18(3):382\u2013386. 10.1016\/j.sbi.2008.03.007","journal-title":"Current Opinion in Structural Biology"},{"issue":"2","key":"4596_CR8","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1101\/gr.2821705","volume":"15","author":"CB Do","year":"2005","unstructured":"Do CB, Mahabhashyam MS, Brudno M, Batzoglou S: ProbCons: Probabilistic consistency-based multiple sequence alignment. Genome Res 2005, 15(2):330\u2013340. 10.1101\/gr.2821705","journal-title":"Genome Res"},{"key":"4596_CR9","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1186\/1471-2105-6-298","volume":"6","author":"T Lassmann","year":"2005","unstructured":"Lassmann T, Sonnhammer EL: Kalign - an accurate and fast multiple sequence alignment algorithm. BMC Bioinformatics 2005, 6: 298. [http:\/\/www.biomedcentral.com\/1471\u20132105\/6\/298] 10.1186\/1471-2105-6-298","journal-title":"BMC Bioinformatics"},{"key":"4596_CR10","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"J Thompson","year":"1994","unstructured":"Thompson J, Higgins D, Gibson T: CLUSTAL W: improving the sensitivity of progressivemultiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Research 1994, 22: 4673\u20134680. 10.1093\/nar\/22.22.4673","journal-title":"Nucleic Acids Research"},{"key":"4596_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins D, Heringa J: T-Coffee: A novel method for multiple sequence alignments. Journal of Molecular Biology 2000, 302: 205\u2013217. 10.1006\/jmbi.2000.4042","journal-title":"Journal of Molecular Biology"},{"issue":"19","key":"4596_CR12","doi-asserted-by":"publisher","first-page":"2455","DOI":"10.1093\/bioinformatics\/btp452","volume":"25","author":"C Kemena","year":"2009","unstructured":"Kemena C, Notredame C: Upcoming challenges for multiple sequence alignment methods in the high-throughput era. Bioinformatics 2009, 25(19):2455\u20132465. 10.1093\/bioinformatics\/btp452","journal-title":"Bioinformatics"},{"key":"4596_CR13","volume-title":"BMC Bioinformatics","author":"S Manavski","year":"2008","unstructured":"Manavski S, Valle G: CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics 2008., 9:"},{"key":"4596_CR14","first-page":"1","volume-title":"IPDPS","author":"L Ligowski","year":"2009","unstructured":"Ligowski L, Rudnicki W: An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases. IPDPS 2009, 1\u20139."},{"key":"4596_CR15","volume-title":"BMC Research Notes","author":"Y Liu","year":"2009","unstructured":"Liu Y, Maskell DL, Schmidt B: CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Research Notes 2009., 2:"},{"key":"4596_CR16","volume-title":"BMC Research Notes","author":"Y Liu","year":"2010","unstructured":"Liu Y, Maskell DL, Schmidt B: CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC Research Notes 2010., 3:"},{"key":"4596_CR17","doi-asserted-by":"publisher","first-page":"4247","DOI":"10.1016\/j.jcp.2010.02.009","volume":"229","author":"A Khajeh-Saeed","year":"2010","unstructured":"Khajeh-Saeed A, Poole S, Perot J: Acceleration of the Smith-Waterman algorithm using single and multiple graphics processors. Journal of Computational Physics 2010, 229: 4247\u20134258. 10.1016\/j.jcp.2010.02.009","journal-title":"Journal of Computational Physics"},{"key":"4596_CR18","volume-title":"20th IEEE International Conference on Application-specific Systems, Architectures and Processors","author":"Y Liu","year":"2009","unstructured":"Liu Y, Maskell DL, Schmidt B: MSA-CUDA: Multiple Sequence Alignment on Graphics Processing Units with CUDA. 20th IEEE International Conference on Application-specific Systems, Architectures and Processors 2009."},{"key":"4596_CR19","first-page":"11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers EW, Miller W: Optimal alignments in linear space. Comput Appl Biosci 1988, 4: 11\u201317.","journal-title":"Comput Appl Biosci"},{"key":"4596_CR20","first-page":"732","volume-title":"Proc SNPD 2008, IEEE Computer Society","author":"J Blazewicz","year":"2008","unstructured":"Blazewicz J, Kasprzak M, Swiercz A, Figlerowicz M, Gawron P, Platt D, Szajkowski L: Parallel Implementation of the Novel Approach to Genome Assembly. Proc SNPD 2008, IEEE Computer Society 2008, 732\u2013737."},{"key":"4596_CR21","unstructured":"ATI Stream[http:\/\/www.amd.com\/stream]"},{"key":"4596_CR22","unstructured":"OpenCL[http:\/\/www.khronos.org\/opencl]"},{"key":"4596_CR23","unstructured":"NVIDIA CUDA[http:\/\/www.nvidia.com\/object\/cuda_home.html]"},{"key":"4596_CR24","unstructured":"NVIDIA CUDA C Programming Best Practices Guide[http:\/\/www.nvidia.com\/object\/cuda_develop.html]"},{"key":"4596_CR25","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1981","unstructured":"Gotoh O: An Improved Algorithm for Matching Biological Sequences. Journal of Molecular Biology 1981, 162: 705\u2013708.","journal-title":"Journal of Molecular Biology"},{"key":"4596_CR26","doi-asserted-by":"publisher","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","volume":"89","author":"S Henikoff","year":"1992","unstructured":"Henikoff S, Henikoff J: Amino Acid Substitution Matrices from Protein Blocks. PNAS 1992, 89: 10915\u201310919. 10.1073\/pnas.89.22.10915","journal-title":"PNAS"},{"issue":"supp 3","key":"4596_CR27","first-page":"345","volume":"5","author":"M Dayhoff","year":"1978","unstructured":"Dayhoff M, Schwartz R, Orcutt B: A model of Evolutionary Change in Proteins. Atlas of protein sequence and structure, Nat Biomed Res Found 1978, 5(supp 3):345\u201358.","journal-title":"Atlas of protein sequence and structure, Nat Biomed Res Found"},{"issue":"2","key":"4596_CR28","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham RL: Bounds on multiprocessing timing anomalies. SIAM J Appl Math 1969, 17(2):416\u2013429. 10.1137\/0117039","journal-title":"SIAM J Appl Math"},{"key":"4596_CR29","volume-title":"Handbook on Scheduling: From Theory to Applications. Springer","author":"J Blazewicz","year":"2007","unstructured":"Blazewicz J, Ecker K, Pesch E, Schmidt G, Weglarz J: Handbook on Scheduling: From Theory to Applications. Springer. 2007."},{"key":"4596_CR30","first-page":"107","volume-title":"BMC Research Notes","author":"A Szalkowski","year":"2008","unstructured":"Szalkowski A, Ledergerber C, Krahenbuhl P, C D: SWPS3 - fast multi-threaded vectorized Smith-Waterman for IBM Cell\/B.E. and x86\/SSE2. BMC Research Notes 2008, 107."},{"key":"4596_CR31","unstructured":"Farrar M: Optimizing Smith-Waterman for the Cell Broad-band Engine.[http:\/\/farrar.michael.googlepages.com\/SW-CellBE.pdf]"},{"key":"4596_CR32","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1186\/1471-2105-9-377","volume":"9","author":"A Wirawan","year":"2008","unstructured":"Wirawan A, Kwoh C, Hieu N, Schmidt B: CBESW: Sequence Alignment on Playstation 3. BMC Bioinformatics 2008, 9: 377. 10.1186\/1471-2105-9-377","journal-title":"BMC Bioinformatics"},{"key":"4596_CR33","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1109\/TCSII.2005.853340","volume":"52","author":"T Oliver","year":"2005","unstructured":"Oliver T, Schmidt B, DL M: Reconfigurable architectures for bio-sequence database scanning on FPGAs. IEEE Trans Circuit Syst II 2005, 52: 851\u201355.","journal-title":"IEEE Trans Circuit Syst II"},{"key":"4596_CR34","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1186\/1471-2105-8-185","volume":"8","author":"T Li","year":"2007","unstructured":"Li T, Shum W, Truong K: 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA). BMC Bioinformatics 2007, 8: 185. 10.1186\/1471-2105-8-185","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"4596_CR35","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","volume":"23","author":"M Farrar","year":"2007","unstructured":"Farrar M: Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics 2007, 23(2):156\u2013161. 10.1093\/bioinformatics\/btl582","journal-title":"Bioinformatics"},{"key":"4596_CR36","unstructured":"Ensembl Databases - Release 55[ftp:\/\/ftp.ensembl.org\/pub\/release-55]"},{"key":"4596_CR37","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/S0168-9525(00)02024-2","volume":"16","author":"P Rice","year":"2000","unstructured":"Rice P, Longden I, Bleasby A: EMBOSS: The European Molecular Biology Open Software Suite. Trends in Genetics 2000, 16: 276\u201377. 10.1016\/S0168-9525(00)02024-2","journal-title":"Trends in Genetics"},{"key":"4596_CR38","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1145\/42411.42415","volume":"31","author":"J Gustafson","year":"1988","unstructured":"Gustafson J: Reevaluating Amdahl's Law. Communications of the ACM 1988, 31: 532\u2013533. 10.1145\/42411.42415","journal-title":"Communications of the ACM"},{"key":"4596_CR39","unstructured":"NVIDIA Fermi Architecture[http:\/\/www.nvidia.com\/object\/Fermi_architecture.html]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-12-181.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T14:10:47Z","timestamp":1630505447000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-12-181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,20]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["4596"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-12-181","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,20]]},"assertion":[{"value":"30 December 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"181"}}