Article ID Journal Published Year Pages File Type
10333946 Theoretical Computer Science 2005 12 Pages PDF
Abstract
Given an input sequence of data, a rigid pattern is a repeating sequence, possibly interspersed with dont-care characters. The data could be a sequence of characters or sets of characters or even real values. In practice, the patterns or motifs of interest are the ones that also allow a variable number of gaps (or dont-care characters): these are patterns with spacers termed extensible patterns In a bioinformatics context, similar patterns have also been called flexible patterns or motifs. The extensibility is succinctly defined by a single integer parameter D⩾1 which is interpreted as the allowable space to be between 1 and D characters between two successive solid characters in a reported motif. We introduce a data structure called the inexact-suffix tree and present an algorithm based on this data structure. This has been tested on primarily biological data such as DNA and protein sequences. However the generality of the system makes it equally applicable in other data mining, clustering, and knowledge extraction applications.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,