Constructing a smallest refining galled phylogenetic network

Trinh N.D. Huynh, Jesper Andreas Jansson, Nguyen Bao Nguyen, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

26 Citations (Scopus)

Abstract

Reticulation events occur frequently in many types of species. Therefore, to develop accurate methods for reconstructing phylogenetic networks in order to describe evolutionary history in the presence of reticulation events is important. Previous work has suggested that constructing phylogenetic networks by merging gene trees is a biologically meaningful approach. This paper presents two new efficient algorithms for inferring a phylogenetic network from a set T of gene trees of arbitrary degrees. The first algorithm solves the open problem of constructing a refining galled network for T (if one exists) with no restriction on the number of hybrid nodes; in fact, it outputs the smallest possible solution. In comparison, the previously best method (SpNet) can only construct networks having a single hybrid node. For cases where there exists no refining galled network for T, our second algorithm identifies a minimum subset of the species set to be removed so that the resulting trees can be combined into a galled network. Based on our two algorithms, we propose two general methods named RGNet and RGNet+. Through simulations, we show that our methods outperform the other existing methods neighbor-joining, NeighborNet, and SpNet.
Original languageEnglish
Title of host publicationResearch in Computational Molecular Biology: 9th Annual International Conference, RECOMB 2005, Cambridge, MA, USA, May 14-18, 2005. Proceedings
EditorsSatoru Miyano, Jill Mesirov , Simon Kasif, Sorin Istrail, Pavel Pevzner, Michael Waterman
Pages265-280
Number of pages16
Publication statusPublished - 17 Oct 2005
Externally publishedYes
Event9th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2005 - Cambridge, MA, United States
Duration: 14 May 200518 May 2005

Publication series

NameLecture Notes in Bioinformatics (Subseries of Lecture Notes in Computer Science)
PublisherSpringer Verlag
VolumeLNBI 3500
ISSN (Print)0302-9743

Conference

Conference9th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2005
Country/TerritoryUnited States
CityCambridge, MA
Period14/05/0518/05/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this