Maximum parsimony distance on phylogenetic trees

A linear kernel and constant factor approximation algorithm

Journal Article (2021)
Author(s)

M.E.L. Jones (Centrum Wiskunde & Informatica (CWI), TU Delft - Discrete Mathematics and Optimization)

Steven Kelk (Universiteit Maastricht)

Leen Stougie (INRIA-Erable, Vrije Universiteit Amsterdam, Centrum Wiskunde & Informatica (CWI))

Research Group
Discrete Mathematics and Optimization
Copyright
© 2021 M.E.L. Jones, Steven Kelk, Leen Stougie
DOI related publication
https://doi.org/10.1016/j.jcss.2020.10.003
More Info
expand_more
Publication Year
2021
Language
English
Copyright
© 2021 M.E.L. Jones, Steven Kelk, Leen Stougie
Research Group
Discrete Mathematics and Optimization
Volume number
117
Pages (from-to)
165-181
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by establishing a linear kernel i.e., that after applying certain reduction rules the resulting instance has size that is bounded by a linear function of the distance. As powerful corollaries to this result we prove that the problem permits a polynomial-time constant-factor approximation algorithm; that the treewidth of a natural auxiliary graph structure encountered in phylogenetics is bounded by a function of the distance; and that the distance is within a constant factor of the size of a maximum agreement forest of the two trees, a well studied object in phylogenetics.