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
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

Fingerprint

Phylogeny
Locus
Genes
Gene
Binary trees
Binary
Coalescence
Sorting
Binary Tree
Phylogenetics
Exact Algorithms
Computer Simulation
Computer simulation
Minimise
Formulation
Theorem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Algorithms for MDC-based multi-locus phylogeny inference. / Yu, Yun; Warnow, Tandy; Nakhleh, Luay.

Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings. 2011. p. 531-545 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6577 LNBI).

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

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6577 LNBI, pp. 531-545, 15th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2011, Vancouver, BC, Canada, 3/28/11. https://doi.org/10.1007/978-3-642-20036-6_47
Yu Y, Warnow T, Nakhleh L. Algorithms for MDC-based multi-locus phylogeny inference. In Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings. 2011. p. 531-545. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-20036-6_47
Yu, Yun ; Warnow, Tandy ; Nakhleh, Luay. / Algorithms for MDC-based multi-locus phylogeny inference. Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings. 2011. pp. 531-545 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{bd1586e93bcf4881bc6f160966de9702,
title = "Algorithms for MDC-based multi-locus phylogeny inference",
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.",
author = "Yun Yu and Tandy Warnow and Luay Nakhleh",
year = "2011",
month = "4",
day = "4",
doi = "10.1007/978-3-642-20036-6_47",
language = "English (US)",
isbn = "9783642200359",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "531--545",
booktitle = "Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings",

}

TY - GEN

T1 - Algorithms for MDC-based multi-locus phylogeny inference

AU - Yu, Yun

AU - Warnow, Tandy

AU - Nakhleh, Luay

PY - 2011/4/4

Y1 - 2011/4/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79953207304&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79953207304&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20036-6_47

DO - 10.1007/978-3-642-20036-6_47

M3 - Conference contribution

AN - SCOPUS:79953207304

SN - 9783642200359

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 531

EP - 545

BT - Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings

ER -