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

8 Scopus citations

Abstract

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
Pages776-785
Number of pages10
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
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

Other

Other1st International Conference on High Performance Computing and Communcations, HPCC 2005
Country/TerritoryItaly
CitySorrento
Period9/21/059/23/05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this