Print Email Facebook Twitter Maximum parsimony distance on phylogenetic trees Title Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm Author Jones, M.E.L. (TU Delft Discrete Mathematics and Optimization; Centrum Wiskunde & Informatica (CWI)) Kelk, Steven (Universiteit Maastricht) Stougie, Leen (Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam; INRIA-Erable) Date 2021 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. Subject Fixed parameter tractabilityMaximum agreement forestMaximum parsimonyPhylogenetics To reference this document use: http://resolver.tudelft.nl/uuid:8d5fc924-a45d-4472-a20c-54d511c45632 DOI https://doi.org/10.1016/j.jcss.2020.10.003 ISSN 0022-0000 Source Journal of Computer and System Sciences, 117, 165-181 Part of collection Institutional Repository Document type journal article Rights © 2021 M.E.L. Jones, Steven Kelk, Leen Stougie Files PDF 1_s2.0_S0022000020300969_main.pdf 725.73 KB Close viewer /islandora/object/uuid:8d5fc924-a45d-4472-a20c-54d511c45632/datastream/OBJ/view