Mining Contiguous Sequential Generators in Biological Sequences

doi:10.1109/TCBB.2015.2495132

Mining Contiguous Sequential Generators in Biological Sequences

2016-09-01

18

PRE

AI

DOI：10.1109/TCBB.2015.2495132

Original

Original request for help

Save

Abstract

En 中文

The discovery of conserved sequential patterns in biological sequences is essential to unveiling common shared functions. Mining sequential generators as well as mining closed sequential patterns can contribute to a more concise result set than mining all sequential patterns, especially in the analysis of big data in bioinformatics. Previous studies have also presented convincing arguments that the generator is preferable to the closed pattern in inductive inference and classification. However, classic sequential generator mining algorithms, due to the lack of consideration on the contiguous constraint along with the lower-closed one, still pose a great challenge at spawning a large number of inefficient and redundant patterns, which is too huge for effective usage. Driven by some extensive applications of patterns with contiguous feature, we propose ConSgen, an efficient algorithm for discovering contiguous sequential generators. It adopts the n-gram model, called shingles, to generate potential frequent subsequences and leverages several pruning techniques to prune the unpromising parts of search space. And then, the contiguous sequential generators are identified by using the equivalence class-based lower-closure checking scheme. Our experiments on both DNA and protein data sets demonstrate the compactness, efficiency, and scalability of ConSgen.

Keywords:

Sequential pattern mining

closed sequential pattern

sequential generator

contiguous sequential generator

DNA sequence

protein sequence

motif finding

Mining Contiguous Sequential Generators in Biological Sequences

Abstract

AI Summary

Journal

Organization