Name
Abstract | ||
|---|---|---|
Given a finite set X, a collection T of rooted phylogenetic trees on X and an integer k, the Hybridization Number problem asks if there exists a phylogenetic network on X that displays all trees from T and has reticulation number at most k. We show two kernelization algorithms for Hybridization Number, with kernel sizes 4 k ( 5 k ) t and 20 k 2 ( Δ + - 1 ) respectively, with t the number of input trees and Δ + their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an n f ( k ) t -time algorithm, with n = | X | and f some computable function of k. We study constructing a network displaying a given collection of phylogenetic trees.Our kernelization techniques work for inputs consisting of multiple binary trees.Previous results were restricted to two trees and/or binary trees.A unified and simplified approach for dealing with common chains of nonbinary trees.Polynomial-time solvability with fixed number of reticulations. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jcss.2016.03.006 | J. Comput. Syst. Sci. |
Keywords | DocType | Volume |
Fixed-parameter tractability,Kernelization,Phylogenetic tree,Phylogenetic network,Hybridization number | Journal | 82 |
Issue | ISSN | Citations |
6 | 0022-0000 | 8 |
PageRank | References | Authors |
0.57 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leo van Iersel | 1 | 215 | 24.58 |
| Steven Kelk | 2 | 193 | 25.60 |
| Celine Scornavacca | 3 | 216 | 18.80 |