Abstract
In this work, we implement a genome alignment system which applies parallelization schemes to the ClustalW algorithm and the interface of database querying. Parallel construction of the distance matrices and parallelization of progressive alignment in the ClustalW algorithm are performed on PC-based Linux cluster with message-passing interface libraries. Achieved experiments show good speedup and significant parallel performance.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Vingron, M., Argos, P.: A fast and sensitive multiple sequence alignment algorithm. Comput. Appl. Biosci. 5, 115–121 (1989)
Gupta, S.K., Kececioglu, J.D., Schäffer, A.A.: Improving the Practical Time and Space Efficiency of the Shortest-Paths Approach to Sum-of-Pairs Multiple Sequence Alignment. J. Comput. Bio. 2, 459–472 (1995)
Zhang, C., Wong, A.K.C.: Toward efficient multiple molecular sequence alignment: a system of genetic algorithm and dynamic programming. IEEE Trans. Systems, Man and Cybernetics, Part B. 27, 918–932 (1997)
Luo, J., Ahmad, I., Ahmed, M., Paul, R.: Parallel Multiple Sequence Alignment with Dynamic Scheduling. In: IEEE Int. Conf. Info. Tech.: Coding and Computing, vol. 1, pp. 8–13 (2005)
Higgins, D.G., Sharp, P.M.: CLUSTAL: a Package for Performing Multiple Sequence Alignment in a Microcomputer. Gene. 73, 237–244 (1988)
Kleinjung, J., Douglas, N., Herringa, J.: Parallelized multiple alignment. Bioinformatics 18, 1270–1271 (2002)
Li, K.-B.: ClustalW-MPI: ClustalW analysis using distributed and parallel computing. Bioinformatics 19, 1585–1586 (2003)
Li, Y., Sze, S.M., Chao, T.-S.: A Practical Implementation of Parallel Dynamic Load Balancing for Adaptive Computing in VLSI Device Simulation. Engineering with Computers 18, 124–137 (2002)
Feng, D.F., Doolittle, R.F.: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol. 25, 351–360 (1987)
Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. J. Mol. Evol. 4, 406–425 (1987)
National Center for Biotechnology Information. [Online]. Available: http://www.ncbi.nlm.nih.gov/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, Y., Chen, CK. (2005). Parallelization of Multiple Genome Alignment. In: Yang, L.T., Rana, O.F., Di Martino, B., Dongarra, J. (eds) High Performance Computing and Communications. HPCC 2005. Lecture Notes in Computer Science, vol 3726. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11557654_102
Download citation
DOI: https://doi.org/10.1007/11557654_102
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29031-5
Online ISBN: 978-3-540-32079-1
eBook Packages: Computer ScienceComputer Science (R0)