de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Selecting Optimal Minimum Spanning Trees that Share a Topological Correspondence with Phylogenetic Trees

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons118128

Kalaghatgi,  Prabhav
Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44907

Lengauer,  Thomas
Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1701.02844.pdf
(Preprint), 455KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Kalaghatgi, P., & Lengauer, T. (2017). Selecting Optimal Minimum Spanning Trees that Share a Topological Correspondence with Phylogenetic Trees. Retrieved from http://arxiv.org/abs/1701.02844.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-002C-3E81-2
Zusammenfassung
Choi et. al (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. In this work we remove this indeterminacy by introducing so-called vertex-ranked MSTs. We note that the effectiveness of CLGrouping is inversely related to the number of leaves in the MST. This motivates the problem of finding a vertex-ranked MST with the minimum number of leaves (MLVRMST). We provide a polynomial time algorithm for the MLVRMST problem, and prove its correctness for graphs whose edges are weighted with tree-additive distances.