A decomposition theorem and two algorithms for reticulation-visible networks

In studies of molecular evolution, phylogenetic trees are rooted binary trees, whereas phylogenetic networks are rooted acyclic digraphs. Edges are directed away from the root and leaves are uniquely labeled with taxa in phylogenetic networks. For the purpose of validating evolutionary models, biolo...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2017-02, Vol.252, p.161-175
Main Authors: Gunawan, Andreas D.M., DasGupta, Bhaskar, Zhang, Louxin
Format: Article
Language:English
Subjects:
Cluster containment problem
Galled networks
Phylogenetic networks
Reticulation-visibility
Tree containment problem
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:In studies of molecular evolution, phylogenetic trees are rooted binary trees, whereas phylogenetic networks are rooted acyclic digraphs. Edges are directed away from the root and leaves are uniquely labeled with taxa in phylogenetic networks. For the purpose of validating evolutionary models, biologists check whether or not a phylogenetic tree (resp. cluster) is contained in a phylogenetic network on the same taxa. These tree and cluster containment problems are known to be NP-complete. A phylogenetic network is reticulation-visible if every reticulation node separates the root of the network from at least a leaf. We answer an open problem by proving that the tree containment problem is solvable in quadratic time for reticulation-visible networks. The key tool used in our answer is a powerful decomposition theorem. It also allows us to design a linear-time algorithm for the cluster containment problem for networks of this type and to prove that every galled network with n leaves has 2(n−1) reticulation nodes at most.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2016.11.001