Name
Title | ||
|---|---|---|
Solving the tree containment problem in linear time for nearly stable phylogenetic networks. |
Abstract | ||
|---|---|---|
A phylogenetic network is a rooted acyclic digraph whose leaves are uniquely labeled with a set of taxa. The tree containment problem asks whether or not a phylogenetic network displays a phylogenetic tree over the same set of labeled leaves. It is a fundamental problem arising from validation of phylogenetic network models. The tree containment problem is NP-complete in general. To identify network classes on which the problem is polynomial time solvable, we introduce two classes of networks by generalizations of tree-child networks through vertex stability, namely nearly stable networks and genetically stable networks. Here, we study the combinatorial properties of these two classes of phylogenetic networks. We also develop a linear-time algorithm for solving the tree containment problem on binary nearly stable networks. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.dam.2017.07.015 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Phylogenetic trees,Phylogenetic networks,Tree containment,Reticulation visibility,Nearly stable networks,Genetically stable networks | Discrete mathematics,Combinatorics,Phylogenetic tree,Vertex (geometry),Generalization,Time complexity,Taxon,Mathematics,Digraph,Phylogenetic network,Binary number | Journal |
Volume | ISSN | Citations |
246 | 0166-218X | 1 |
PageRank | References | Authors |
0.38 | 10 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philippe Gambette | 1 | 77 | 9.61 |
| Andreas D. M. Gunawan | 2 | 33 | 6.84 |
| Anthony Labarre | 3 | 69 | 9.62 |
| Stéphane Vialette | 4 | 648 | 48.10 |
| Louxin Zhang | 5 | 890 | 96.47 |