PRec-I-DCM3: A parallel framework for fast and accurate large scale phylogeny reconstruction

Cristian Coarfa, Yuri Dotsenko, John Mellor-Crummey, Luay Nakhleh, Usman Roshan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Accurate reconstruction of phylogenetic trees very often involves solving hard optimization problems, particularly the maximum parsimony (MP) and maximum likelihood (ML) problems. Various heuristics have been devised for solving these two problems; however, they obtain good results within reasonable time only on small datasets. This has been a major impediment for large-scale phytogeny reconstruction, particularly for the effort to assemble the Tree of Life - the evolutionary relationship of all organisms on earth. Roshan et al. recently introduced Rec- I -DCM3, an efficient and accurate meta-method for solving the MP problem on large datasets of up to 14,000 taxa. Nonetheless, a drastic improvement in Rec- I Rec-I-DCM3's-DCM3's performance is still needed in order to achieve similar (or better) accuracy on datasets at the scale of the Tree of Life. In this paper, we improve the performance of Rec- I -DCM3 via parallelization. Experimental results demonstrate that our parallel method, PRec-I-DCM3, achieves significant improvements, both in speed and accuracy, over its sequential counterpart.

Original languageEnglish (US)
Title of host publicationProceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
EditorsJ. Ma, L.T. Yang
Pages346-350
Number of pages5
DOIs
StatePublished - Sep 1 2005
Event11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005 - Fukuoka, Japan
Duration: Jul 20 2005Jul 22 2005

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume2
ISSN (Print)1521-9097

Other

Other11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
CountryJapan
CityFukuoka
Period7/20/057/22/05

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'PRec-I-DCM3: A parallel framework for fast and accurate large scale phylogeny reconstruction'. Together they form a unique fingerprint.

Cite this