2014 EvoMinerFrequentSubtreeMiningin

• (Deepak et al., 2014) ⇒ Akshay Deepak, David Fernández-Baca, Srikanta Tirthapura, Michael J. Sanderson, and Michelle M. Mcmahon. (2014)."EvoMiner: Frequent Subtree Mining in Phylogenetic Databases".; In: Knowledge and Information Systems Journal, 41(3). doi:10.1007/s10115-013-0676-0

Subject Headings: Frequent Tree Pattern; Frequent Tree Pattern Mining Task.

Cited By

• Google Scholar: ~ 22 Citations
• ACM DL: ~ 2 Citations (Retrieved:2019-10-06).
• Semantic Scholar: ~ 8 Citations (Retrieved:2019-10-06).
• Springer: ~ 10 Citations (Retrieved:2019-10-06).

Quotes

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 EvoMinerFrequentSubtreeMiningin	Srikanta Tirthapura Akshay Deepak David Fernández-Baca Michael J. Sanderson Michelle M. Mcmahon			EvoMiner: Frequent Subtree Mining in Phylogenetic Databases				10.1007/s10115-013-0676-0		2014