Skip to Main content Skip to Navigation
Journal articles

A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees

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) time algorithm for computing the KAST of k trees on n leaves, in which at least one tree has maximum degree d. In this paper, an O(kn3 + nd)-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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410429
Contributor : Krister Swenson <>
Submitted on : Friday, December 13, 2019 - 6:38:17 PM
Last modification on : Wednesday, April 29, 2020 - 1:11:44 AM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

68

Files downloads

80