Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Computer and System Sciences Année : 2021

Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm

Résumé

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 constantfactor 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.
Fichier principal
Vignette du fichier
Maximum_parsimony_distance_on_phylogenetic_trees_A.pdf (617.2 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03498430 , version 1 (21-12-2021)

Identifiants

Citer

Mark Jones, Steven Kelk, Leen Stougie. Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm. Journal of Computer and System Sciences, 2021, 117, pp.165-181. ⟨10.1016/j.jcss.2020.10.003⟩. ⟨hal-03498430⟩

Collections

INRIA INRIA2
17 Consultations
142 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More