Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees
Open Access
- 1 June 2010
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 26 (12), i140-i148
- https://doi.org/10.1093/bioinformatics/btq198
Abstract
Motivation: Reticulate network is a model for displaying and quantifying the effects of complex reticulate processes on the evolutionary history of species undergoing reticulate evolution. A central computational problem on reticulate networks is: given a set of phylogenetic trees (each for some region of the genomes), reconstruct the most parsimonious reticulate network (called the minimum reticulate network) that combines the topological information contained in the given trees. This problem is well-known to be NP-hard. Thus, existing approaches for this problem either work with only two input trees or make simplifying topological assumptions. Results: We present novel results on the minimum reticulate network problem. Unlike existing approaches, we address the fully general problem: there is no restriction on the number of trees that are input, and there is no restriction on the form of the allowed reticulate network. We present lower and upper bounds on the minimum number of reticulation events in the minimum reticulate network (and infer an approximately parsimonious reticulate network). A program called PIRN implements these methods, which also outputs a graphical representation of the inferred network. Empirical results on simulated and biological data show that our methods are practical for a wide range of data. More importantly, the lower and upper bounds match for many datasets (especially when the number of trees is small or reticulation level is low), and this allows us to solve the minimum reticulate network problem exactly for these datasets. Availability: A software tool, PIRN, is available for download from the web page: http://www.engr.uconn.edu/~ywu. Contact:ywu@engr.uconn.edu Supplementary information: Supplementary data is available at Bioinformatics online.This publication has 20 references indexed in Scilit:
- Computing galled networks from real dataBioinformatics, 2009
- A practical method for exact computation of subtree prune and regraft distanceBioinformatics, 2008
- Computing the minimum number of hybridization events for a consistent evolutionary historyDiscrete Applied Mathematics, 2007
- Application of Phylogenetic Networks in Evolutionary StudiesMolecular Biology and Evolution, 2005
- Reconstructing Reticulate Evolution in Species—Theory and PracticeJournal of Computational Biology, 2005
- Bounding the Number of Hybridisation Events for a Consistent Evolutionary HistoryJournal of Mathematical Biology, 2005
- Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombinationJournal of Computer and System Sciences, 2005
- On the Computational Complexity of the Rooted Subtree Prune and Regraft DistanceAnnals of Combinatorics, 2005
- A Framework for Representing Reticulate EvolutionAnnals of Combinatorics, 2005
- Phylogeny and Subfamilial Classification of the Grasses (Poaceae)Annals of the Missouri Botanical Garden, 2001