Title

EvoMiner: frequent subtree mining in phylogenetic databases

Campus Units

Computer Science, Electrical and Computer Engineering

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

12-2014

Journal or Book Title

Knowledge and Information Systems

Volume

41

Issue

3

First Page

559

Last Page

590

DOI

10.1007/s10115-013-0676-0

Abstract

The problem of mining collections of trees to identify common patterns, called frequent subtrees (FSTs), arises often when trying to interpret the results of phylogenetic analysis. FST mining generalizes the well-known maximum agreement subtree problem. Here we present EvoMiner, a new algorithm for mining frequent subtrees in collections of phylogenetic trees. EvoMiner is an Apriori-like levelwise method, which uses a novel phylogeny-specific constant-time candidate generation scheme, an efficient fingerprinting-based technique for downward closure, and a lowest-common-ancestor-based support counting step that requires neither costly subtree operations nor database traversal. Our algorithm achieves speedups of up to 100 times or more over Phylominer, the current state-of-the-art algorithm for mining phylogenetic trees. EvoMiner can also work in depth-first enumeration mode to use less memory at the expense of speed. We demonstrate the utility of FST mining as a way to extract meaningful phylogenetic information from collections of trees when compared to maximum agreement subtrees and majority-rule trees—two commonly used approaches in phylogenetic analysis for extracting consensus information from a collection of trees over a common leaf set.

Comments

This is a manuscript of an article published as Deepak, Akshay, David Fernández-Baca, Srikanta Tirthapura, Michael J. Sanderson, and Michelle M. McMahon. "EvoMiner: frequent subtree mining in phylogenetic databases." Knowledge and information systems 41, no. 3 (2014): 559-590. The final publication is available at Springer via DOI: 10.1007/s10115-013-0676-0. Posted with permission.

Copyright Owner

Springer-Verlag London

Language

en

File Format

application/pdf

Published Version

Share

COinS