### 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 language | English (US) |
---|---|

Title of host publication | RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology |

Pages | 337-346 |

Number of pages | 10 |

Volume | 8 |

State | Published - 2004 |

Externally published | Yes |

Event | RECOMB 2004 - Proceedings of the Eight Annual International Conference on Research in Computational Molecular Biology - San Diego, CA., United States Duration: Mar 27 2004 → Mar 31 2004 |

### Other

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

Country | United States |

City | San Diego, CA. |

Period | 3/27/04 → 3/31/04 |

### Fingerprint

### Keywords

- Gene trees
- Phylogenetic networks
- Subtree prune and regraft

### ASJC Scopus subject areas

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

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

}

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 -