Algorithms for MDC-based multi-locus phylogeny inference

Yun Yu, Tandy Warnow, Luay Nakhleh

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

Abstract

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, or 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 paper, 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. Finally, we study the performance of these methods in coalescent-based computer simulations.

Original languageEnglish (US)
Title of host publicationResearch in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings
Pages531-545
Number of pages15
DOIs
StatePublished - Apr 4 2011
Externally publishedYes
Event15th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2011 - Vancouver, BC, Canada
Duration: Mar 28 2011Mar 31 2011

Publication series

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

Other

Other15th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2011
CountryCanada
CityVancouver, BC
Period3/28/113/31/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Algorithms for MDC-based multi-locus phylogeny inference'. Together they form a unique fingerprint.

  • Cite this

    Yu, Y., Warnow, T., & Nakhleh, L. (2011). Algorithms for MDC-based multi-locus phylogeny inference. In Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings (pp. 531-545). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6577 LNBI). https://doi.org/10.1007/978-3-642-20036-6_47