Reconstructing reticulate evolution in species - Theory and practice

Luay Nakhleh, Tandy Warnow, C. Randal Linder

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

Abstract

We present new methods for reconstructing reticulate evolution of species due to events such as horizontal transfer or hybrid speciation; both methods are based upon extensions of Wayne Maddison's approach in his seminal 1997 paper. Our first method is a polynomial time algorithm for constructing phylogenetic networks from two gene trees contained inside the network. We allow the network to have an arbitrary number of reticulations, but we limit the reticulation in the network so that the cycles in network are node-disjoint ("galled") ; we prove accuracy guarantees for our first method by presenting a formal characterization of the set of gene trees defined by a species network. Our second method is a polynomial time algorithm for constructing networks with one reticulation, where we allow for errors in the estimated gene trees. Using simulations, we demonstrate improved performance of this method over both Neighbor-Net and Maddison's method.

Original languageEnglish (US)
Title of host publicationRECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology
Pages337-346
Number of pages10
Volume8
StatePublished - 2004
Externally publishedYes
EventRECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology - San Diego, CA., United States
Duration: Mar 27 2004Mar 31 2004

Other

OtherRECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology
CountryUnited States
CitySan Diego, CA.
Period3/27/043/31/04

Fingerprint

Genes
Polynomials
Gene Regulatory Networks

Keywords

  • Gene trees
  • Phylogenetic networks
  • Subtree prune and regraft

ASJC Scopus subject areas

  • Biochemistry, Genetics and Molecular Biology(all)
  • Computer Science(all)

Cite this

Nakhleh, L., Warnow, T., & Linder, C. R. (2004). Reconstructing reticulate evolution in species - Theory and practice. In RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology (Vol. 8, pp. 337-346)

Reconstructing reticulate evolution in species - Theory and practice. / Nakhleh, Luay; Warnow, Tandy; Linder, C. Randal.

RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology. Vol. 8 2004. p. 337-346.

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

Nakhleh, L, Warnow, T & Linder, CR 2004, Reconstructing reticulate evolution in species - Theory and practice. in RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology. vol. 8, pp. 337-346, RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology, San Diego, CA., United States, 3/27/04.
Nakhleh L, Warnow T, Linder CR. Reconstructing reticulate evolution in species - Theory and practice. In RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology. Vol. 8. 2004. p. 337-346
Nakhleh, Luay ; Warnow, Tandy ; Linder, C. Randal. / Reconstructing reticulate evolution in species - Theory and practice. RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology. Vol. 8 2004. pp. 337-346
@inproceedings{3bc2be5345674fd9b12cfa8651eb2f5a,
title = "Reconstructing reticulate evolution in species - Theory and practice",
abstract = "We present new methods for reconstructing reticulate evolution of species due to events such as horizontal transfer or hybrid speciation; both methods are based upon extensions of Wayne Maddison's approach in his seminal 1997 paper. Our first method is a polynomial time algorithm for constructing phylogenetic networks from two gene trees contained inside the network. We allow the network to have an arbitrary number of reticulations, but we limit the reticulation in the network so that the cycles in network are node-disjoint ({"}galled{"}) ; we prove accuracy guarantees for our first method by presenting a formal characterization of the set of gene trees defined by a species network. Our second method is a polynomial time algorithm for constructing networks with one reticulation, where we allow for errors in the estimated gene trees. Using simulations, we demonstrate improved performance of this method over both Neighbor-Net and Maddison's method.",
keywords = "Gene trees, Phylogenetic networks, Subtree prune and regraft",
author = "Luay Nakhleh and Tandy Warnow and Linder, {C. Randal}",
year = "2004",
language = "English (US)",
volume = "8",
pages = "337--346",
booktitle = "RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology",

}

TY - GEN

T1 - Reconstructing reticulate evolution in species - Theory and practice

AU - Nakhleh, Luay

AU - Warnow, Tandy

AU - Linder, C. Randal

PY - 2004

Y1 - 2004

N2 - We present new methods for reconstructing reticulate evolution of species due to events such as horizontal transfer or hybrid speciation; both methods are based upon extensions of Wayne Maddison's approach in his seminal 1997 paper. Our first method is a polynomial time algorithm for constructing phylogenetic networks from two gene trees contained inside the network. We allow the network to have an arbitrary number of reticulations, but we limit the reticulation in the network so that the cycles in network are node-disjoint ("galled") ; we prove accuracy guarantees for our first method by presenting a formal characterization of the set of gene trees defined by a species network. Our second method is a polynomial time algorithm for constructing networks with one reticulation, where we allow for errors in the estimated gene trees. Using simulations, we demonstrate improved performance of this method over both Neighbor-Net and Maddison's method.

AB - We present new methods for reconstructing reticulate evolution of species due to events such as horizontal transfer or hybrid speciation; both methods are based upon extensions of Wayne Maddison's approach in his seminal 1997 paper. Our first method is a polynomial time algorithm for constructing phylogenetic networks from two gene trees contained inside the network. We allow the network to have an arbitrary number of reticulations, but we limit the reticulation in the network so that the cycles in network are node-disjoint ("galled") ; we prove accuracy guarantees for our first method by presenting a formal characterization of the set of gene trees defined by a species network. Our second method is a polynomial time algorithm for constructing networks with one reticulation, where we allow for errors in the estimated gene trees. Using simulations, we demonstrate improved performance of this method over both Neighbor-Net and Maddison's method.

KW - Gene trees

KW - Phylogenetic networks

KW - Subtree prune and regraft

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

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

M3 - Conference contribution

AN - SCOPUS:2442436724

VL - 8

SP - 337

EP - 346

BT - RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology

ER -