TY - JOUR
T1 - A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees
AU - Piovesan, Teresa
AU - Kelk, Steven
PY - 2013
Y1 - 2013
N2 - Here, we present a new fixed parameter tractable algorithm to compute the hybridization number r of two rooted, not necessarily binary phylogenetic trees on taxon set X in time (6(r)r!).poly(n), where n = vertical bar X vertical bar. The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on X, and several insights from the softwired clusters literature. This yields a surprisingly simple and practical bounded-search algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem.
AB - Here, we present a new fixed parameter tractable algorithm to compute the hybridization number r of two rooted, not necessarily binary phylogenetic trees on taxon set X in time (6(r)r!).poly(n), where n = vertical bar X vertical bar. The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on X, and several insights from the softwired clusters literature. This yields a surprisingly simple and practical bounded-search algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem.
U2 - 10.1109/TCBB.2012.134
DO - 10.1109/TCBB.2012.134
M3 - Article
C2 - 23702540
SN - 1557-9964
VL - 10
SP - 18
EP - 25
JO - IEEE ACM Transactions on Computational Biology and Bioinformatics (TCBB)
JF - IEEE ACM Transactions on Computational Biology and Bioinformatics (TCBB)
IS - 1
ER -