Abstract
Alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. Dynamic programming is a technique to find optimal alignment, but it requires very long computation time. We have shown that dynamic programming for more than two sequences can be efficiently processed on a compact system which consists of an off-the-shelf FPGA board and its host computer (node). The performance is, however, not enough for comparing long sequences. In this paper, we describe a computation method for the multidimensional dynamic programming on distributed systems. The method is now being tested using two nodes connected by Ethernet. According to our experiments, it is possible to achieve 5.1 times speedup with 16 nodes, and more speedup can be expected for comparing longer sequences using more number of nodes. The performance is affected only a little by the data transfer delay when comparing long sequences. Therefore, our method can be mapped on any kinds of networks with large delays.
Chapter PDF
Similar content being viewed by others
References
National Center for Biotechnology Information (NCBI), NCBI-GenBank Flat File Release 137.0 (August 2003), http://www.ncbi.nlm.nih.gov/
European Molecular Biology Laboratory (EMBL), http://www.ebi.ac.uk/embl/
DNA Data Bank of Japan (DDBJ), http://www.ddbj.nig.ac.jp/
Henikoff, S., Henikoff, J.G.: Amino Acid Substitution Matrices from Protein Block. Proc. Natl. Acad. Sci. 89, 10915–10919 (1992)
Jones, D.T., et al.: The Rapid Generation of Mutation DataMatrices from Proten Sequences. CABIOS 8, 275–282 (1992)
Altschula, S.F., Gisha, W., Millerb, W., Meyersc, E.W., Lipman, D.J.: Basic Local Alignment Search Tool. Journal of Molecular Biology 215(3), 403–410 (1990)
Stephen, F., et al.: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research 25(17), 3389–3402 (1997)
Pearson, W.R., Lipman, D.J.: Improved tools for biological sequence comparison. Proceedings of the National Academy of Sciences of the USA 85, 2444–2448 (1988)
PARACEL, GeneMatcher2, http://www.paracel.com/
Lavenier, D.: SAMBA Systolic Accelerators For Molecular Biological Applications., Technical Report RR-2845 (1996)
Thomas White, C., et al.: BioSCAN: A VLSI-Based System for Biosequence Analysis. In: IEEE International Conference on Computer Design: VLSI in Computer & Processors, vol. 147, pp. 504–509 (1991)
TimeLogic Corporation, Decypher bioinformaticsacceleration solution (2002), http://www.timelogic.com/products.html
Puttegowda, K., Worek, W., Pappas, N., Dandapani, A., Athanas, P.: A Run-Time Reconfigurable System for Gene-Sequence Searching. In: International VLSI Design Conference (to appear, 2003)
Guccione, S.A., Keller, E.: Gene Matching Using JBits. In: International Conferenece on Field-Programmable Logic and Applications, pp. 1168–1171 (2002)
Yamaguchi, Y., Miyajima, Y., Maruyama, T., Konagaya, A.: High Speed Homology Search with Run-time Reconfiguration. In: International Conferenece on Field-Programmable Logic and Applications, pp. 281–291 (2002)
Yamaguchi, Y., Maruyama, T., Konagaya, A.: Three-Dimensional Dynamic Programming for Homology Search. In: International Conferenece on Field-Programmable Logic and Applications, pp. 505–514 (2004)
Masuno, S., Maruyama, T., Yoshiki, Y., Konagaya, A.: Multidimensional Dynamic Programming for Homology Search. In: International Conferenece on Field-Programmable Logic and Applications, pp. 173–178 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Masuno, S., Maruyama, T., Yamaguchi, Y., Konagaya, A. (2006). Multidimensional Dynamic Programming for Homology Search on Distributed Systems. In: Nagel, W.E., Walter, W.V., Lehner, W. (eds) Euro-Par 2006 Parallel Processing. Euro-Par 2006. Lecture Notes in Computer Science, vol 4128. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11823285_119
Download citation
DOI: https://doi.org/10.1007/11823285_119
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37783-2
Online ISBN: 978-3-540-37784-9
eBook Packages: Computer ScienceComputer Science (R0)