Parallel implementation and performance of fastDNAml

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel implementation and performance of fastDNAml: a program for maximum likelihood phylogenetic inference

Full text

Pdf (391 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM) table of contents

Denver, Colorado

Pages: 20 - 20

Year of Publication: 2001

ISBN:1-58113-293-X

Authors

Craig A. Stewart	University Information Technology Services, Indiana University, Bloomington IN
David Hart	University Information Technology Services, Indiana University, Bloomington IN
Donald K. Berry	University Information Technology Services, Indiana University, Bloomington IN
Gary J. Olsen	University of Illinois Urbana/Champaign, Urbana, IL
Eric A. Wernert	University Information Technology Services, Indiana University, Bloomington IN
William Fischer	Indiana University, Bloomington IN

Sponsors

ACM: Association for Computing Machinery
SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS\DATC : IEEE Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 32, Citation Count: 16

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/582034.582054 What is a DOI?

ABSTRACT

This paper describes the parallel implementation of fastDNAml, a program for the maximum likelihood inference of phylogenetic trees from DNA sequence data. Mathematical means of inferring phylogenetic trees have been made possible by the wealth of DNA data now available. Maximum likelihood analysis of phylogenetic trees is extremely computationally intensive. Availability of computer resources is a key factor limiting use of such analyses. fastDNAml is implemented in serial, PVM, and MPI versions, and may be modified to use other message passing libraries in the future. We have developed a viewer for comparing phylogenies. We tested the scaling behavior of fastDNAml on an IBM RS/6000 SP up to 64 processors. The parallel version of fastDNAml is one of very few computational phylogenetics codes that scale well. fastDNAml is available for download as source code or compiled for Linux or AIX.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Joint Center for Structural Genomics. Home page, http://www.jcsg.org/, accessed May 2001.
	2	Korber, B., M. Muldoon, J. Theiler, F. Gao, R. Gupta, A. Lapedes, B.H. Hahn, S. Wolinsky, T. Bhattacharya. 2000. Timing the Ancestor of the HIV-1 Pandemic Strains, http://www.sciencemag.org/cgi/content/full/288/5472/1789, accessed May 2001.
	3	Olsen, G. J., H. Matsuda, R. Hagstrom, and R. Overbeek. 1994. fastDNAml: A tool for construction of phylogenetic trees of DNA sequences using maximum likelihood. Comput. Appl. Biosci. 10: 41-48.
	4	Olsen, G.J. Home page. http://geta.life.uiuc.edu/~gary/, accessed May 2001.
	5	Felsenstein, J. 1981. Evolutionary trees from DNA sequences: A maximum likelihood approach. J. Mol. Evol. 17: 368-376.
	6	Stewart, C.A., T.W. Tan, M. Buckhorn, D. Hart, D.K. Berry, L. Zhang, E. Wernert, M. Sakharkar, W. Fischer, D.F. McMullen. 2000. Evolutionary biology and high performance computing. In: R.F. Enenkel. Software Tools for Computational Biology, http://www.cas.ibm.com/archives/1999/workshop_report/bio.html, accessed May 2001.
	7	Felsenstein, J. 1978. The number of evolutionary trees. Syst. Zool. 27: 27-33.
	8	National center for biotechnology information. Home page, http://www.ncbi.nlm.nih.gov/, accessed May 2001.
	9	Maidak B.L., J.R. Cole, T.G. Lilburn, C.T. Parker Jr., P.R. Saxman, R.J. Farris, G.M. Garrity, G.J. Olsen, T.M. Schmidt, J.M. Tiedje. 2001. The RDP-II (Ribosomal Database Project). Nucleic Acids Res. 29(1):173-4
	10	Maddison, D.R. and W. P. Maddison. 1998. The Tree of Life: A multi-authored, distributed Internet project containing information about phylogeny and biodiversity. http://phylogeny.arizona.edu/tree/phylogeny.html, accessed July 2001.
	11	Hans L. Bodlaender , Michael R. Fellows , Tandy Warnow, Two Strikes Against Perfect Phylogeny, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.273-283, July 13-17, 1992
	12	Hershkovitz, M.A., and D.D. Leipe. 1998. Phylogenetic analysis. In: Bioinformatics: a practical guide to the analysis of genes and proteins. A.D. Baxevanis and B.F.F. Ouelette (Eds.), pp. 189-230. New York: Wiley-Liss.
	13	Jermiin, L. S., G.J. Olsen, and S. Easteal. 1997. Majority rule consensus of maximum likelihood trees. Mol. Biol. Evol. 14: 1296-1302.
	14	Swofford, D. L., G.J. Olsen, P.J. Waddell, and D.M. Hillis. 1996. Phylogenetic inference. In: Molecular Systematics, 2nd edition D. M. Hillis, C. Moritz and B. K. Mable (Eds.), pp. 407-514 Sunderland, MA: Sinauer Associates.
	15	Vivek Sarin , Ananth Grama , Ahmed Sameh, Analyzing the error bounds of multipole-based treecodes, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
	16	Van de Peer, Y., P. De Rijk, J. Wuyts, T. Winkelmans, and R. De Wachter. 2000. The European small subunit ribosomal RNA database. Nucleic Acids Research 28(1):175-6.
	17	Papakhian, M. The UITS Research SP system, http://spwww.iu.edu/, accessed May 2001.
	18	Quinn Snell , Michael Whiting , Mark Clement , David McLaughlin, Parallel phylogenetic inference, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.35-es, November 04-10, 2000, Dallas, Texas, United States
	19	Bader, D.A., B.M.E. Moret, T. Warnow, S.K. Wyman, and M. Yan. 2001. High-performance algorithm engineering for gene-order phylogenies. DIMACS Workshop on Whole Genome Comparison, Rutgers University. http://www.cs.utexas.edu/users/stacia/papers/dimacs.pdf, accessed May 2001.
	20	Blanchette, M., G. Bourque, and D. Sankoff. 1997. Breakpoint phylogenies. Genome Informatics 1997 (Eds: S. Miyano and T. Takagi) Universal Academy Press, Tokyo, pp. 5-34.
	21	Roshan, U., L. Nakhleh, J. Sun, and T. Warnow. 2001. Designing fast converging methods in phylogenetics: an experimental study. Proceedings of Intelligent Systems for Molecular Biology (ISMB) 2001, Copenhagen. http://bioinformatics.oupjournals.org/content/vol17/suppl_1/, accessed July 2001.
	22	C. Ceron , J. Dopazo , E. L. Zapata , J. M. Carazo , O. Trelles, Parallel implementation of DNAm1 program on message-passing architectures, Parallel Computing, v.24 n.5-6, p.701-716, June 1998 [doi>10.1016/S0167-8191(98)00002-7]
	23	Wernert, E. TreeViewer for maximum likelihood analysis of phylogenetic data, http://www.avl.iu.edu/projects/DNAml/, accessed May 2001.
	24	Open Inventor. http://www.sgi.com/software/inventor/, accessed July 2001.
	25	Hart, D. Maximum Likelihood Analysis of Phylogenetic Data, http://www.indiana.edu/~rac/hpc/fastDNAml/index.html, accessed May 2001.
	26	Hein, J. 1989. A tree reconstruction method that is economical in the number of pairwise comparisons used. Mol. Biol. Evol. 6: 669-684.
	27	Olsen, G. J. 1988. Phylogenetic analysis using ribosomal RNA. Methods Enzymol. 164: 793-812.
	28	Livny, M. The Condor Project Homepage. http://www.cs.wisc.edu/condor/, accessed July 2001.

CITED BY 16

	H. A. Schmidt , E. Petzold , A. Vingron , A. von Haeseler, Molecular phylogenetics: parallelized parameter estimation and quartet puzzling, Journal of Parallel and Distributed Computing, v.63 n.7-8, p.719-727, July 2003
	A. P. Stamatakis , T. Ludwig , H. Meier, A fast program for maximum likelihood-based inference of large phylogenetic trees, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Xizhou Feng , Duncan A. Buell , John R. Rose , Peter J. Waddell, Parallel algorithms for Bayesian phylogenetic inference, Journal of Parallel and Distributed Computing, v.63 n.7-8, p.707-718, July 2003
	Savrina F. Carrizo, Phylogenetic trees: an information visualisation perspective, Proceedings of the second conference on Asia-Pacific bioinformatics, p.315-320, January 01, 2004, Dunedin, New Zealand
	Tim Dwyer , Falk Schreiber, Optimal leaf ordering for two and a half dimensional phylogenetic tree visualisation, Proceedings of the 2004 Australasian symposium on Information Visualisation, p.109-115, February 01, 2004, Christchurch, New Zealand
	A. Stamatakis , M. Lindermeier , M. Ott , T. Ludwig , H. Meier, DRAxML@home: a distributed program for computation of large phylogenetic trees, Future Generation Computer Systems, v.21 n.5, p.725-730, May 2005
	Chunxi Chen , Bertil Schmidt, An adaptive grid implementation of DNA sequence alignment, Future Generation Computer Systems, v.21 n.7, p.988-1003, July 2005
	Alexandros P. Stamatakis , Thomas Ludwig , Harald Meier , Marty J. Wolf, Accelerating parallel maximum likelihood-based phylogenetic tree calculations using subtree equality vectors, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-16, November 16, 2002, Baltimore, Maryland
	Xizhou Feng , Kirk W. Cameron , Duncan A. Buell, Biology---PBPI: a high performance implementation of Bayesian phylogenetic inference, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
	Chao-Tung Yang , Tsu-Fen Han , Heng-Chuan Kan, On construction of a BioGrid platform for parallel bioinformatics applications, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	A. Stamatakis , F. Blagojevic , D. S. Nikolopoulos , C. D. Antonopoulos, Exploring New Search Algorithms and Hardware for Phylogenetics: RAxML Meets the IBM Cell, Journal of VLSI Signal Processing Systems, v.48 n.3, p.271-286, September 2007
	Chunxi Chen , Jagath C. Rajapakse, Grid-Enabled BLASTZ: Application to Comparative Genomics, Journal of VLSI Signal Processing Systems, v.48 n.3, p.301-309, September 2007
	Michael Ott , Jaroslaw Zola , Alexandros Stamatakis , Srinivas Aluru, Large-scale maximum likelihood-based phylogenetic analysis on the IBM BlueGene/L, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada
	Craig A. Stewart , Rainer Keller , Richard Repasky , Matthias Hess , David Hart , Matthias Muller , Ray Sheppard , Uwe Wossner , Martin Aumuller , Huian Li , Donald K. Berry , John Colbourne, A Global Grid for Analysis of Arthropod Evolution, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.328-337, November 08-08, 2004
	Michael Ott , Jaroslaw Zola , Srinivas Aluru , Andrew D. Johnson_aff3n4 , Daniel Janies , Alexandros Stamatakis, Large-scale phylogenetic analysis on current HPC architectures, Scientific Programming, v.16 n.2-3, p.255-270, April 2008
	Adam K. L. Wong , Andrzej M. Goscinski, Parallel computing on clusters and enterprise grids: practice and experience, International Journal of High Performance Computing and Networking, v.6 n.2, p.137-147, July 2009