Parallel divide-and-conquer phylogeny reconstruction by maximum likelihood

Z. Du, A. Stamatakis, F. Lin, U. Roshan, L. Nakhleh

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

9 Scopus citations


Phylogenetic trees are important in biology since their applications range from determining protein function to understanding the evolution of species. Maximum Likelihood (ML) is a popular optimization criterion in phylogenetics. However, inference of phylogenies with ML is NP-hard. Recursive-Iterative-DCM3 (Rec-I-DCMS).is a divideand-conquer framework that divides a dataset into smaller subsets (subproblems), applies an external base method to infer subtrees, merges the subtrees into a comprehensive tree, and then refines the global tree with an external global method. In this study we present a novel parallel implementation of Rec-I-DCM3 for inference of large trees with ML. Parallel-Rec-I-DCM3 uses RAxML as external base and global search method. We evaluate program performance on 6 large real-data alignments containing 500 up to 7.769 sequences. Our experiments show that P-Rec-I-DCM3 reduces inference times and improves final tree quality over sequential Rec-I-DCM3 and stand-alone RAxML.

Original languageEnglish (US)
Title of host publicationHigh Performance Computing and Communcations - First International Conference, HPCC 2005, Proceedings
Number of pages10
StatePublished - 2005
Event1st International Conference on High Performance Computing and Communcations, HPCC 2005 - Sorrento, Italy
Duration: Sep 21 2005Sep 23 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3726 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st International Conference on High Performance Computing and Communcations, HPCC 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parallel divide-and-conquer phylogeny reconstruction by maximum likelihood'. Together they form a unique fingerprint.

Cite this