Abstract
Multiple sequence alignment (MSA) is a very important problem in Computational Biology since it is often used to identify evolutionary relation-ships among the organisms and predict secondary/tertiary structure. Since MSA is known to be a computationally challenging problem, many proposals were made to accelerate it either by using parallel processing or hardware accelerators. In this paper, we propose an FPGA based accelerator to execute the most compute intensive part of DIALIGN, an iterative method to obtain multiple sequence alignments. The experimental results collected in our 200-element FPGA prototype show that a speedup of 383.41 was obtained when compared with the software implementation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anish, A.: Hardware Accelerated Protein Identification, MsC Thesis, Univ. Toronto (2003)
Boukerche, A., et al.: Reconfigurable Architecture for Biological Sequence Comparison in Reduced Memory Space. In: IEEE IPDPS/NIDISC (2007)
Boukerche, A., et al.: Parallel Strategies for the Local Biological Sequence Alignment in a Cluster of Workstations. Journal of Parallel and Distributed Computing 67, 170–185 (2007)
Carrillo, H., Lipman, D.: The Multiple Sequence Alignment Problem. SIAM Journal of Applied Math. 48, 1073–1082 (1988)
Durbin, R., Eddy, S., Krogh, A., Mitchison, G.: Biological Sequence Analysis, p. 356. Cambridge Univ Press, Cambridge (1998)
Forte Design Systems, Cynthesizer User’s Guide For Cynthesizer 2.4.0. (2005)
Gotoh, O.: An improved algorithm for matching biological sequences. Journal of Molecular Biology 162, 705–708 (1982)
Gotoh, O.: Significant Improvement in Accuracy of Multiple Protein Sequence Alignments by Iterative Refinements as Assessed by Reference to Structural Alignments. J. Mol. Biol. 264, 823–838 (1996)
Gusfield, D.: Algorithms on Strings, Trees and Sequences, p. 534. Cambridge Univ Press, Cambridge (1977)
Lavenier, D.: Speeding up genome computations with a systolic accelerator. SIAM news 31 (1998)
Lin, X., Peiheng, Z., Dongbo, B., Shengzhong, F., Ninghui, S.: To Accelerate Multiple Sequence Alignment using FPGAs. In: HPCASIA (2005)
Marongiu, A., Pallazari, P., Rosato, V.: Designing Hardware for Protein Sequence Alignment. Bioinformatics 19, 1739–1740 (2003)
Morgenstern, B., et al.: Multiple DNA and protein sequence alignment based on segment-to-segment comparison. In: Proc. Natl Acad. Sci., USA, pp. 12098–12103 (1996)
Morgenstern, B., et al.: DIALIGN: finding local similarities by multiple sequence alignment. Bioinformatics (1998)
Mount, D.: Bioinformatics: Sequence and Genome Analysis. C. S. Harbor Lab Press (2004)
Notredame, C., Higgins, D., Heringa, J.: T-Coffee: A novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 302, 205–217 (2002)
Needleman, S., Wunsch, C.: A general method applicable to the search for similarities in the amino acid sequence of two protein. J. Mol. Biol. 48, 443–453 (1970)
Oliver, T., Schmidt, B., Maskell, D.: Reconfigurable Architectures for Bio-sequence Database Scanning on FPGAs. IEEE Transactions on Circuits and Systems II 52(12), 851–855 (2005)
Oliver, T., Schmidt, B., Nathan, D., Clemens, R., Maskell, D.: Using Reconfigurable Hardware to Accelerate Multiple Sequence Alignment with ClustalW. Bioinformatics 21, 3431–3432 (2005)
Schmollinger, M., Nieselt, K., Kaufmann, M., Morgenstern, B.: DIALIGN P: Fast pair-wise and multiple sequence alignment using parallel processors BMC Bioinformatics (2004)
Setubal, J., Meidanis, J.: Introduction to Computational Molecular Biology. PWS Publishing Company, Boston (1997)
Smith, T., Waterman, M.: Identification of common molecular sub-sequences. J. Mol. Biology 147, 195–197 (1981)
Open SystemC Initiative Draft, Standard SystemC Language Reference Manual (2005)
Thompson, J., Higgins, D., Gibson, T.: Clustal W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting. Nucleic Ac. Res. 22, 4673–4680 (1994)
Wang, T., Jiang, T.: On the Complexity of the Multiple Sequence Alignment. J. Comp. Biol. 1, 337–348 (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boukerche, A., Correa, J.M., de Melo, A.C.M.A., Jacobi, R.P., Rocha, A.F. (2007). An FPGA-Based Accelerator for Multiple Biological Sequence Alignment with DIALIGN. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds) High Performance Computing – HiPC 2007. HiPC 2007. Lecture Notes in Computer Science, vol 4873. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77220-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-77220-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77219-4
Online ISBN: 978-3-540-77220-0
eBook Packages: Computer ScienceComputer Science (R0)