Algorithms for MDC-based multi-locus phylogeny inference: Beyond rooted binary gene trees on single alleles

Yun Yu, Tandy Warnow, Luay Nakhleh

Research output: Contribution to journalArticle


One of the criteria for inferring a species tree from a collection of gene trees, when gene tree incongruence is assumed to be due to incomplete lineage sorting (ILS), is Minimize Deep Coalescence (MDC). Exact algorithms for inferring the species tree from rooted, binary trees under MDC were recently introduced. Nevertheless, in phylogenetic analyses of biological data sets, estimated gene trees may differ from true gene trees, be incompletely resolved, and not necessarily rooted. In this article, we propose new MDC formulations for the cases where the gene trees are unrooted/binary, rooted/non-binary, and unrooted/non-binary. Further, we prove structural theorems that allow us to extend the algorithms for the rooted/binary gene tree case to these cases in a straightforward manner. In addition, we devise MDC-based algorithms for cases when multiple alleles per species may be sampled. We study the performance of these methods in coalescent-based computer simulations.

Original languageEnglish (US)
Pages (from-to)1543-1559
Number of pages17
JournalJournal of Computational Biology
Issue number11
StatePublished - Nov 1 2011
Externally publishedYes



  • algorithms
  • coalescence
  • dynamic programming
  • graph theory
  • phylogenetic trees

ASJC Scopus subject areas

  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Modeling and Simulation
  • Computational Theory and Mathematics

Cite this