TY - JOUR

T1 - Maximum parsimony distance on phylogenetic trees

T2 - A linear kernel and constant factor approximation algorithm

AU - Jones, Mark

AU - Kelk, Steven

AU - Stougie, Leen

PY - 2021/5

Y1 - 2021/5

N2 - 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.

AB - 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.

KW - Fixed parameter tractability

KW - Maximum agreement forest

KW - Maximum parsimony

KW - Phylogenetics

UR - http://www.scopus.com/inward/record.url?scp=85097648036&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097648036&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2020.10.003

DO - 10.1016/j.jcss.2020.10.003

M3 - Article

AN - SCOPUS:85097648036

SN - 0022-0000

VL - 117

SP - 165

EP - 181

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -