G-PAS 2.0 - an improved version of protein alignment tool with an efficient backtracking routine on multiple GPUs

• Autorzy: Frohmberg W. , Kierzynka M. , Blazewicz J. , Wojciechowski P.
• Języki publikacji: EN

Abstrakty

EN

Several highly efficient alignment tools have been released over the past few years, including those taking advantage of GPUs (Graphics Processing Units). G-PAS (GPU-based Pairwise Alignment Software) was one of them, however, with a couple of interesting features that made it unique. Nevertheless, in order to adapt it to a new computational architecture some changes had to be introduced. In this paper we present G-PAS 2.0 - a new version of the software for performing high-throughput alignment. Results show, that the new version is faster nearly by a fourth on the same hardware, reaching over 20 GCUPS (Giga Cell Updates Per Second).

Słowa kluczowe

EN

pairwise alignment; GPU computing; alignment with backtracking procedure

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2012
• Tom: Vol. 60, nr 3
• Strony: 491--494
• Opis fizyczny: Bibliogr. 28 poz., rys., tab.

Twórcy

autor

Frohmberg W.

autor

Kierzynka M.

autor

Blazewicz J.

autor

Wojciechowski P.

• Institute of Computing Science, Poznań University of Technology, 3 Piotrowo St., 60-965 Poznań, Poland

Bibliografia

• [1] M. Ciznicki, M. Kierzynka, K. Kurowski, B. Ludwiczak, K. Napierala, and J. Palczynski, “Efficient isosurface extraction using marching tetrahedra and histogram pyramids on multiple GPUs”, Lecture Notes in Computer Science 7204, 343-352 (2012).
• [2] M. Blazewicz, S.R. Brandt, M. Kierzynka, K. Kurowski, B. Ludwiczak, J. Tao, and J. Weglarz, “CaKernel - a parallel application programming framework for heterogenous computing architectures”, Scientific Programming 19 (4), 185-197 (2011).
• [3] W. Jendernalik, J. Jakusz, G. Blakiewicz, R. Piotrowski, and S. Szczepanski, “CMOS realisation of analogue processor for early vision processing”, Bull. Pol. Ac.: Tech. 59 (2), 141-147 (2011).
• [4] L. Ligowski and W. Rudnicki, “An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases”, IPDPS doi:10.1109/IPDPS.2009.5160931 (2009).
• [5] Y. Liu, D.L. Maskell and B. Schmidt, “CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDAenabled GPUs based on SIMT and virtualized SIMD abstractions”, BMC Research Notes 3, 93 (2010).
• [6] S.A. Manavski and G. Valle, “CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment”, BMC Bioinformatics 9 (2), S10 (2008).
• [7] L. Ligowski, W.R. Rudnicki, Y. Liu, and B. Schmidt, “Accurate scanning of sequence databases with the Smith-Waterman algorithm”, GPU Computing Gems, Emerald Edition 1, 155-157 (2011).
• [8] J. Blazewicz, W. Frohmberg, M. Kierzynka, and P. Wojciechowski, “G-MSA - A GPU-based, fast and accurate algorithm for multiple sequence alignment”, J. Paralleland Distributed Computing, doi:10.1016/j.jpdc.2012.04.004 (2012).
• [9] K. Kwarciak and P. Formanowicz, “A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions” Bull. Pol. Ac.: Tech. 59 (1), 111-115 (2011).
• [10] J. Blazewicz, P. Formanowicz, F. Guinand, M. Kasprzak, “A heuristic managing errors for DNA sequencing”, Bioinformatics 18, 652-660 (2002).
• [11] J. Blazewicz, W. Frohmberg, M. Kierzynka, E. Pesch, and P. Wojciechowski, “Protein alignment algorithms with an efficient backtracking routine on multiple GPUs”, BMC Bioinformatics 12, 181 (2011).
• [12] S.B. Needleman and C.D.Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins”, J. Mol. Biol. 48 (3), 443-53 (1970).
• [13] T.F. Smith and M.S. Waterman, “Identification of Common Molecular Subsequences”, J. Molecular Biology 147, 195-97 (1981).
• [14] O. Gotoh, “An improved algorithm for matching biological sequences”, J. Molecular Biology 162, 705-708 (1981).
• [15] K.-M. Chao, W. R. Pearson, and W. Miller, “Aligning two sequences within a specified diagonal band”, Comput. Appl.Biosci. 8 (5), 481-487 (1992).
• [16] M. Gribskov, A.D. McLachlan, and D. Eisenberg, “Profile analysis: detection of distantly related proteins”, PNAS 84, 4355-4358 (1987).
• [17] M. Gribskov, R. Luthy, and D. Eisenberg, “Profile analysis”, Methods in Enzymology 183, 146-159 (1990).
• [18] M.S. Waterman, “Sequence alignments in the neighborhood of the optimum with general application to dynamic programming”, PNAS 80, 3123-3124 (1983).
• [19] M.S. Waterman and T.H. Byers, “A dynamic programming algorithm to find all solutions in a neighborhood of the optimum”, Math. Biosci. 77, 179-188 (1985).
• [20] D. Naor and D. Burtlag, “On suboptimal alignment of biological sequences”, Proc. 4th Annual Symposium on CombinatorialPattern Matching 1, 179-196 (1993).
• [21] M. Zuker, “Suboptimal sequence alignment in molecular biology, alignment with error analysis”, J. Mol. Biol. 221, 403-420 (1991).
• [22] M. Vingron and P. Argos, “Determination of reliable regionsin protein sequence alignments”, Protein Engin. 7, 565-569 (1990).
• [23] A.J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimal decoding algorithm”, IEEE Trans. Inf.Theory IT-13, 260-269 (1967).
• [24] D. Zhang, “An implementation of Viterbi algorithm on GPU”, First Int. Conf. on Information Science and Engineering 1, CD-ROM (2009).
• [25] Z. Du, Z. Yin and D.A. Bader, “A tile-based parallel Viterbi algorithm for biological sequence alignment on GPU with CUDA”, Ninth IEEE Int. Workshop on High Performance ComputationalBiology Atlanta, GA 1, CD-ROM (2010).
• [26] E.W. Myers and W. Miller, “Optimal alignments in linear space”, Comput. Appl. Biosci. 4 (1), 11-17 (1988).
• [27] R.L. Graham, “Bounds on multiprocessing timing anomalies”, SIAM J. Appl. Math. 17 (2), 416-429 (1969).
• [28] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Handbook on Scheduling: From Theory to Applications, Springer, Berlin, 2007.