title: Protein alignment algorithms with an efficient backtracking routine on multiple GPUs.
abstract: BACKGROUND
  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.
  
  
  RESULTS
  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.
  
  
  CONCLUSIONS
  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.
authors: Poznań University of Technology, Poznań, Poland.
authors: Jacek
authors: J
authors: Blazewicz
authors: Wojciech
authors: W
authors: Frohmberg
authors: Michal
authors: M
authors: Kierzynka
authors: Erwin
authors: E
authors: Pesch
authors: Pawel
authors: P
authors: Wojciechowski
references: Comput Biol Chem. 2009 Jun;33(3):224-30
references: 19477687
references: J Comput Biol. 1994 Winter;1(4):337-48
references: 8790475
references: BMC Bioinformatics. 2005 Dec 12;6:298
references: 16343337
references: BMC Bioinformatics. 2008 Sep 17;9:377
references: 18798993
references: Genome Res. 2005 Feb;15(2):330-40
references: 15687296
references: J Mol Biol. 1970 Mar;48(3):443-53
references: 5420325
references: Bioinformatics. 2009 Oct 1;25(19):2455-65
references: 19648142
references: Comput Appl Biosci. 1988 Mar;4(1):11-7
references: 3382986
references: Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
references: 7984417
references: Curr Opin Struct Biol. 2008 Jun;18(3):382-6
references: 18485694
references: Proc Natl Acad Sci U S A. 1992 Nov 15;89(22):10915-9
references: 1438297
references: BMC Res Notes. 2010 Apr 06;3:93
references: 20370891
references: BMC Res Notes. 2009 May 06;2:73
references: 19416548
references: J Mol Biol. 2000 Sep 8;302(1):205-17
references: 10964570
references: BMC Bioinformatics. 2008 Mar 26;9 Suppl 2:S10
references: 18387198
references: Trends Genet. 2000 Jun;16(6):276-7
references: 10827456
references: J Mol Biol. 1982 Dec 15;162(3):705-8
references: 7166760
references: J Mol Biol. 1981 Mar 25;147(1):195-7
references: 7265238
references: Bioinformatics. 2007 Jan 15;23(2):156-61
references: 17110365
references: BMC Res Notes. 2008 Oct 29;1:107
references: 18959793
references: BMC Bioinformatics. 2007 Jun 07;8:185
references: 17555593