Mining periodic patterns with gap requirement from sequences
Authors:
Open Access
- 1 August 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 1 (2) , 7
Abstract
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequenceSof lengthLand a patternPof lengthl, we considerPa frequently occurring pattern inSif the probability ofobservingPgiven a randomly picked length-lsubsequence ofSexceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns areperiodicwith agap requirement. That is to say, the characters inPshould match subsequences ofSin such a way that the matching characters inSare separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study.Keywords
This publication has 19 references indexed in Scilit:
- Mining periodic patterns with gap requirement from sequences2005
- 10-11 bp periodicities in complete genomes reflect protein structure and DNA folding.Bioinformatics, 1999
- 3-, 10.5-, 200- and 400-base periodicities in genome sequencesPhysica A: Statistical Mechanics and its Applications, 1998
- Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm.Bioinformatics, 1998
- Detecting periodic patterns in biological sequences.Bioinformatics, 1998
- Short-range Order in Two Eukaryotic Genomes: Relation to Chromosome StructureJournal of Molecular Biology, 1996
- Assessment of protein coding measuresNucleic Acids Research, 1992
- The SWISS-PROT protein sequence data bankNucleic Acids Research, 1992
- Basic local alignment search toolJournal of Molecular Biology, 1990
- The Mosaic Genome of Warm-Blooded VertebratesScience, 1985