A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles IEEE/ACM Transactions on Computational Biology and Bioinformatics Year : 2021

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.
Fichier principal
Vignette du fichier
2019-WangFasterKAST.pdf (628.73 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-02410429 , version 1 (13-12-2019)

Identifiers

Cite

Biing-Feng Wang, Krister M. Swenson. A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2021, 18 (2), pp.416-430. ⟨10.1109/TCBB.2019.2922955⟩. ⟨lirmm-02410429⟩
91 View
169 Download

Altmetric

Share

More