A fast and scalable method for inferring phylogenetic networks from trees by aligning lineage taxon strings
Open Access
- 22 May 2023
- journal article
- research article
- Published by Cold Spring Harbor Laboratory in Genome Research
- Vol. 33 (7), 1053-1060
- https://doi.org/10.1101/gr.277669.123
Abstract
The reconstruction of phylogenetic networks is an important but challenging problem in phylogenetics and genome evolution, as the space of phylogenetic networks is vast and cannot be sampled well. One approach to the problem is to solve the minimum phylogenetic network problem, in which phylogenetic trees are first inferred, and then the smallest phylogenetic network that displays all the trees is computed. The approach takes advantage of the fact that the theory of phylogenetic trees is mature, and there are excellent tools available for inferring phylogenetic trees from a large number of biomolecular sequences. A tree–child network is a phylogenetic network satisfying the condition that every nonleaf node has at least one child that is of indegree one. Here, we develop a new method that infers the minimum tree–child network by aligning lineage taxon strings in the phylogenetic trees. This algorithmic innovation enables us to get around the limitations of the existing programs for phylogenetic network inference. Our new program, named ALTS, is fast enough to infer a tree–child network with a large number of reticulations for a set of up to 50 phylogenetic trees with 50 taxa that have only trivial common clusters in about a quarter of an hour on average.Funding Information
- Singapore Ministry of Education E Tier 1 (R-146-000-318-114)
- U.S. National Science Foundation (CCF-1718093, IIS-1909425)
This publication has 29 references indexed in Scilit:
- Ancient hybridizations among the ancestral genomes of bread wheatScience, 2014
- RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogeniesBioinformatics, 2014
- Fixed-Parameter Algorithms for Maximum Agreement ForestsSIAM Journal on Computing, 2013
- Inference of Population Splits and Mixtures from Genome-Wide Allele Frequency DataPLoS Genetics, 2012
- Fast computation of minimum hybridization networksBioinformatics, 2011
- Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic treesBioinformatics, 2010
- Computing the minimum number of hybridization events for a consistent evolutionary historyDiscrete Applied Mathematics, 2007
- Horizontal gene transfer, genome innovation and evolutionNature Reviews Microbiology, 2005
- Horizontal Gene Transfer in Prokaryotes: Quantification and ClassificationAnnual Review of Microbiology, 2001
- Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic treesBioinformatics, 1997