Geodesic
Computing phylogenetic trees using topologically related minimum spanning trees
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1003-1025.

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

Choi et al.(Choi et al. JMLR, 2011) introduced a minimum spanning tree (MST)-based method called CLGrouping, for constructing tree-structured probabilistic graphical models, a statistical framework that is commonly used for inferring phylogenetic trees. While CLGrouping works correctly if there is a unique MST, we observe an indeterminacy in the method in the case that there are multiple MSTs. We demonstrate the indeterminacy of CLGrouping using a synthetic quartet tree and a tree over primate genera. The indeterminacy of CLGrouping can be removed if the input MST shares a topological relationship with the corresponding phylogenetic tree. We introduce so-called vertex order based MSTs (VMSTs) that are guaranteed to have the desired topological relationship. We relate the number of leaves in the VMST to the degree of parallelism that is offered by CLGrouping. We provide polynomial-time algorithms for constructing VMSTs and for selecting a VMST with the optimal number of leaves. 
@article{JGAA_2017_21_6_a1,
     author = {Prabhav Kalaghatgi and Thomas Lengauer},
     title = {Computing phylogenetic trees using topologically related minimum
spanning trees},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1003--1025},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2017},
     doi = {10.7155/jgaa.00447},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00447/}
}
TY  - JOUR
AU  - Prabhav Kalaghatgi
AU  - Thomas Lengauer
TI  - Computing phylogenetic trees using topologically related minimum
spanning trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 1003
EP  - 1025
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00447/
DO  - 10.7155/jgaa.00447
LA  - en
ID  - JGAA_2017_21_6_a1
ER  - 
%0 Journal Article
%A Prabhav Kalaghatgi
%A Thomas Lengauer
%T Computing phylogenetic trees using topologically related minimum
spanning trees
%J Journal of Graph Algorithms and Applications
%D 2017
%P 1003-1025
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00447/
%R 10.7155/jgaa.00447
%G en
%F JGAA_2017_21_6_a1
Prabhav Kalaghatgi; Thomas Lengauer. Computing phylogenetic trees using topologically related minimum
spanning trees. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1003-1025. doi : 10.7155/jgaa.00447. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00447/

Cité par Sources :