Phylogenetic incongruence through the lens of Monadic Second Order logic

Abstract : Within the field of phylogenetics there is growing interest in measures for summarising the dissimilarity, or incongruence, of two or more phylogenetic trees. Many of these measures are NP-hard to compute and this has stimulated a considerable volume of research into fixed parameter tractable algorithms. In this article we use Monadic Second Order logic to give alternative, compact proofs of fixed parameter tractability for several well-known incongruence measures. In doing so we wish to demonstrate the considerable potential of MSOL - machinery still largely unknown outside the algorithmic graph theory community - within phylogenetics. A crucial component of this work is the observation that many measures, when bounded, imply the existence of an agreement forest of bounded size, which in turn implies that an auxiliary graph structure, the display graph, has bounded treewidth. It is this bound on treewidth that makes the machinery of MSOL available for proving fixed parameter tractability.
Type de document :
Article dans une revue
Journal of Graph Algorithms and Applications (JGAA), Brown University, 2016, 20 (2), pp.189-215. 〈10.7155/jgaa.00390〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01348425
Contributeur : Isabelle Gouat <>
Soumis le : samedi 23 juillet 2016 - 10:59:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 24 octobre 2016 - 10:28:13

Fichier

KelkIerselScornavaccaWeller201...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Steven Kelk, Leo Van Iersel, Celine Scornavacca, Mathias Weller. Phylogenetic incongruence through the lens of Monadic Second Order logic. Journal of Graph Algorithms and Applications (JGAA), Brown University, 2016, 20 (2), pp.189-215. 〈10.7155/jgaa.00390〉. 〈lirmm-01348425〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

145