title: On the fixed parameter tractability of agreement-based phylogenetic distances.
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 [Formula: see text]-time algorithm for any of these problems into an [Formula: see text]-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.
authors.affiliation: School of Engineering and Computing Sciences, Durham University, Durham, DH1 3LE, UK.
authors.forename: Magnus
authors.initials: M
authors.lastname: Bordewich
authors.affiliation: Institut des Sciences de l'Evolution, Université de Montpellier, CNRS, IRD, EPHE, Place E. Bataillon CC, 064-34095, Montpellier Cedex 5, France. celine.scornavacca@umontpellier.fr.
authors.forename: Celine
authors.initials: C
authors.lastname: Scornavacca
authors.affiliation: School of Engineering and Computing Sciences, Durham University, Durham, DH1 3LE, UK.
authors.forename: Nihan
authors.initials: N
authors.lastname: Tokac
authors.affiliation: Institut de Biologie Computationnelle (IBC), Laboratory of Informatics, Robotics, and Microelectronics of Montpellier (LIRMM), Université de Montpellier, 161 rue Ada, 34392, Montpellier Cedex 5, France.
authors.forename: Mathias
authors.initials: M
authors.lastname: Weller
mesh_terms: D000465:Algorithms; D002965:Classification / Q000379:methods*; D006824:Hybridization, Genetic; D008957:Models, Genetic; D010802:Phylogeny
keywords: Cluster reduction; Hybridization number; Phylogenetic network; SPR distance; TBR distance