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

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

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Accurate reconstruction of phylogenetic trees often involves solving hard optimisation problems, particularly the Maximum Parsimony (MP) and Maximum Likelihood (ML) problems. Various heuristics yield good results for these problems within reasonable time only on small datasets. This is a major impediment for large-scale phylogeny reconstruction. Roshan et al. introduced Rec-I-DCMS, an efficient and accurate meta-method for solving the MP problem on large datasets of up to 14,000 taxa. We improve the performance of Rec-I-DCM3 via parallelisation. The experiments demonstrate that our parallel method, PRec-I-DCM3, achieves significant improvements, both in speed and accuracy, over its sequential counterpart.

Original languageEnglish (US)
Pages (from-to)407-419
Number of pages13
JournalInternational Journal of Bioinformatics Research and Applications
Issue number4
StatePublished - 2006

All Science Journal Classification (ASJC) codes

  • Health Information Management
  • Health Informatics
  • Biomedical Engineering
  • Clinical Biochemistry


  • Bioinformatics research and applications
  • DCM3
  • Disk-Covering Method (DCM)
  • Maximum Parsimony (MP)
  • PRec-I-DCM3
  • Parallel computing
  • Phylogeny
  • Rec-I-DCM3
  • Scalability


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