Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time

Philippe Gambette (1) , Andreas D.M. Gunawan (2) , Anthony Labarre (1) , Stéphane Vialette (1) , Louxin Zhang (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Mathematics [Singapore]

A phylogenetic network is a rooted acyclic digraph whose leaves are labeled with a set of taxa. The tree containment problem is a fundamental problem arising from model validation in the study of phylogenetic networks. It asks to determine whether or not a given network displays a given phylogenetic tree over the same leaf set. It is known to be NP-complete in general. Whether or not it remains NP-complete for stable networks is an open problem. We make progress towards answering that question by presenting a quadratic time algorithm to solve the tree containment problem for a new class of networks that we call genetically stable networks, which include tree-child networks and comprise a subclass of stable networks.

Keywords: phylogenetic network; genetically stable; tree containment

Domains: Data Structures and Algorithms [cs.DS]; Bioinformatics [q-bio.QM]

Philippe Gambette, Andreas D.M. Gunawan, Anthony Labarre, Stéphane Vialette, Louxin Zhang. Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time. IWOCA 2015, Oct 2015, Verona, Italy. pp.197-208, ⟨10.1007/978-3-319-29516-9_17⟩. ⟨hal-01226035⟩