A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees

Biing-Feng Wang 1 Krister Swenson 2
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The maximum agreement subtree method determines the consensus of a collection of phylogenetic trees by identifying maximum cardinality subsets of leaves for which all input trees agree. The trees induced by these maximum cardinality subsets are maximum agreement subtrees (MASTs). A single MAST may be misleading, since there can exist two MASTs which share almost no leaves; nevertheless, it may be impossible to inspect all MASTs, since the number of MASTs can be exponential in the number of leaves. To overcome this drawback, Swenson et al. suggested to further summarize the information common to all MASTs by their intersection, which is called the kernel agreement subtree (KAST). The construction of the KAST is the focus of this paper. Swenson et al. had an O(kn3+n4+nd+1)timealgorithmforcomputingtheKASTofktreesonnleaves,inwhichatleastonetreehasmaximumdegreed.Inthispaper,anO(kn^3 + n^d)$ -time algorithm is presented. We demonstrate the efficiency of our algorithm on simulated trees as well as on ribosomal RNA alignments, where trees with 13,000 taxa took only hours to process, whereas the previous algorithm did not terminate after a week of computation.
Document type :
Journal articles
Complete list of metadatas

Cited literature [50 references]  Display  Hide  Download

Contributor : Krister Swenson <>
Submitted on : Friday, December 13, 2019 - 6:38:17 PM
Last modification on : Tuesday, December 17, 2019 - 2:26:25 AM




Biing-Feng Wang, Krister Swenson. A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, In press, pp.1-1. ⟨10.1109/TCBB.2019.2922955⟩. ⟨lirmm-02410429⟩



Record views


Files downloads