Geodesic
Phylogenetic incongruence through the lens of Monadic Second Order logic
Journal of Graph Algorithms and Applications, Tome 20 (2016) no. 2, pp. 189-215.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00390
Keywords: Phylogenetics, Distances, MSOL, fixed parameter tractability, treewidth, cliquewidth 
@article{JGAA_2016_20_2_a1,
     author = {Steven Kelk and Leo van Iersel and Celine Scornavacca and Mathias Weller},
     title = {Phylogenetic incongruence through the lens of {Monadic} {Second} {Order} logic},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {189--215},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2016},
     doi = {10.7155/jgaa.00390},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00390/}
}
TY  - JOUR
AU  - Steven Kelk
AU  - Leo van Iersel
AU  - Celine Scornavacca
AU  - Mathias Weller
TI  - Phylogenetic incongruence through the lens of Monadic Second Order logic
JO  - Journal of Graph Algorithms and Applications
PY  - 2016
SP  - 189
EP  - 215
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00390/
DO  - 10.7155/jgaa.00390
LA  - en
ID  - JGAA_2016_20_2_a1
ER  - 
%0 Journal Article
%A Steven Kelk
%A Leo van Iersel
%A Celine Scornavacca
%A Mathias Weller
%T Phylogenetic incongruence through the lens of Monadic Second Order logic
%J Journal of Graph Algorithms and Applications
%D 2016
%P 189-215
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00390/
%R 10.7155/jgaa.00390
%G en
%F JGAA_2016_20_2_a1
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, Tome 20 (2016) no. 2, pp. 189-215. doi : 10.7155/jgaa.00390. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00390/

Cité par Sources :