On the fixed parameter tractability of agreement-based phylogenetic distances
- 25 May 2016
- journal article
- research article
- Published by Springer Nature in Journal of Mathematical Biology
- Vol. 74 (1-2) , 239-257
Abstract
Three important and related measures for summarizing the dissimilarity in phylogenetic trees are the minimum number of hybridization events required to fit two phylogenetic trees onto a single phylogenetic network (the hybridization number), the (rooted) subtree prune and regraft distance (the rSPR distance) and the tree bisection and reconnection distance (the TBR distance) between two phylogenetic trees. The respective problems of computing these measures are known to be NP-hard, but also fixed-parameter tractable in their respective natural parameters. This means that, while they are hard to compute in general, for cases in which a parameter (here the hybridization number and rSPR/TBR distance, respectively) is small, the problem can be solved efficiently even for large input trees. Here, we present new analyses showing that the use of the “cluster reduction” rule—already defined for the hybridization number and the rSPR distance and introduced here for the TBR distance—can transform any \(O(f(p) \cdot n)\)-time algorithm for any of these problems into an \(O(f(k) \cdot n)\)-time one, where n is the number of leaves of the phylogenetic trees, p is the natural parameter and k is a much stronger (that is, smaller) parameter: the minimum level of a phylogenetic network displaying both trees.
Keywords
Funding Information
- Ministry of National Education, Republic of Turkey
This publication has 22 references indexed in Scilit:
- Faster exact computation of rSPR distanceJournal of Combinatorial Optimization, 2013
- Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees2013
- Fixed-Parameter Algorithms for Maximum Agreement ForestsSIAM Journal on Computing, 2013
- Computing the minimum number of hybridization events for a consistent evolutionary historyDiscrete Applied Mathematics, 2007
- Inferring a level-1 phylogenetic network from a dense set of rooted tripletsTheoretical Computer Science, 2006
- Bounding the Number of Hybridisation Events for a Consistent Evolutionary HistoryJournal of Mathematical Biology, 2005
- On the Computational Complexity of the Rooted Subtree Prune and Regraft DistanceAnnals of Combinatorics, 2005
- Subtree Transfer Operations and Their Induced Metrics on Evolutionary TreesAnnals of Combinatorics, 2001
- Gene Trees in Species TreesSystematic Biology, 1997
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984