A decomposition theorem and two algorithms for reticulation-visible networks.pdf (896.75 kB)

A decomposition theorem and two algorithms for reticulation-visible networks

Download (896.75 kB)
journal contribution
posted on 12.02.2018 by Andreas D.M. Gunawan, Bhaskar DasGupta, Louxin Zhang
In studies of molecular evolution, phylogenetic trees are rooted binary trees, whereas phy- logenetic 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 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.


The work was supported by a Singapore MOE ARF Tier-1 Grant R-146-000-177-112 and the Merlion Programme 2013. DasGupta was supported by NSF Grant IIS-1160995. This work was also presented at the RECOMB’2016.


Publisher Statement

Copyright © 2017 Elsevier B.V. or its licensors or contributors. ScienceDirect ® is a registered trademark of Elsevier B.V.


Elsevier Inc.



Issue date