2026-08-14T22:42:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9067 2024-03-06T10:43:17Z ddc:004 open_access

A Faster Construction of Greedy Consensus Trees Gawrychowski, Pawel Landau, Gad M. Sung, Wing-Kin Weimann, Oren phylogenetic trees greedy consensus trees dynamic trees A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in phylogenetic tree reconstruction. It is also central for predicting a species tree from a set of gene trees, as indicated recently in [Nature 2013]. This paper focuses on two of the most well-known and widely used consensus tree methods: the greedy consensus tree and the frequency difference consensus tree. Given k conflicting trees each with n leaves, the previous fastest algorithms for these problems were O(k n^2) for the greedy consensus tree [J. ACM 2016] and O~(min{k n^2, k^2n}) for the frequency difference consensus tree [ACM TCBB 2016]. We improve these running times to O~(k n^{1.5}) and O~(k n) respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Gawrychowski and Gad M. Landau and Wing-Kin Sung and Oren Weimann 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.63 urn:nbn:de:0030-drops-90676 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.63 eng https://creativecommons.org/licenses/by/3.0/legalcode