2026-07-20T05:06:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6465 2024-03-06T10:38:21Z ddc:004 open_access

Minimal Phylogenetic Supertrees and Local Consensus Trees Jansson, Jesper Sung, Wing-Kin phylogenetic tree rooted triplet local consensus minimal supertree computational complexity bioinformatics The problem of constructing a minimally resolved phylogenetic supertree (i.e., having the smallest possible number of internal nodes) that contains all of the rooted triplets from a consistent set R is known to be NP-hard. In this paper, we prove that constructing a phylogenetic tree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard, and develop exact, exponential-time algorithms for both problems. The new algorithms are applied to construct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaf label set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in all trees in S, where ``minimal'' means either having the smallest possible number of internal nodes or the smallest possible number of rooted triplets. The second variant generalizes the RV-II tree, introduced by Kannan, Warnow, and Yooseph in 1998. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jesper Jansson and Wing-Kin Sung 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.53 urn:nbn:de:0030-drops-64653 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.53 eng https://creativecommons.org/licenses/by/3.0/legalcode