A Polynomial-Time Algorithm for Minimizing the Deep Coalescence Cost for Level-1 Species Networks

Phylogenetic analyses commonly assume that the species history can be represented as a tree. However, in the presence of hybridization, the species history is more accurately captured as a network. Despite several advances in modeling phylogenetic networks, there is no known polynomial-time algorith...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2022-09, Vol.19 (5), p.2642-2653
Main Authors: LeMay, Matthew, Libeskind-Hadas, Ran, Wu, Yi-Chieh
Format: Article
Language:English
Subjects:
Algorithms
Coalescence
Cost analysis
deep coalescence
History
Hybridization
Networks
Phylogenetics
Phylogeny
Polynomials
Probabilistic logic
reconciliation
Sorting algorithms
Species
Statistics
Time complexity
Topology
Vegetation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Phylogenetic analyses commonly assume that the species history can be represented as a tree. However, in the presence of hybridization, the species history is more accurately captured as a network. Despite several advances in modeling phylogenetic networks, there is no known polynomial-time algorithm for parsimoniously reconciling gene trees with species networks while accounting for incomplete lineage sorting. To address this issue, we present a polynomial-time algorithm for the case of level-1 networks, in which no hybrid species is the direct ancestor of another hybrid species. This work enables more efficient reconciliation of gene trees with species networks, which in turn, enables more efficient reconstruction of species networks.
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2021.3105922