Name
Abstract | ||
|---|---|---|
The detection of frequent patterns such as motifs and higher aggregates is of paramount interest in biology and invests many other applications of automated discovery. The problem with its variants is usually plagued with computational burden. A related difficulty is posed by the fact, that due to the sheer mole of candidates, the tables and indices at the outset tend to be bulky, un-manageable, and ultimately uninformative. For solid patterns, it is possible to compact the size of statistical indices by resort to certain monotonicities exhibited by popular scores. The savings come from the fact that these monotonicities enable one to partition the candidate over-represented words into families in such a way that it suffices to consider and weigh only one candidate per family. In this paper, we study the problem of extracting, from given source x and error threshold k, substrings of x that occur unusually often in x within k substitutions or mismatches. Specifically, we assume that the input textstring x of n characters is produced by an i.i.d. source, and design efficient methods for computing the probability and expected number of occurrences for substrings of x with (either exactly or up to) k mismatches. Two related schemes are presented. In the first one, an O(nk) time preprocessing of x is developed that supports the following subsequent query: for any substring w of x arbitrarily specified as input, the probability of occurrence of w in x within (either exactly or up to) k mismatches is reported in O(k^2) time. In the second scheme, a length or length range is arbitrarily specified, and the above probabilities are computed for all substrings of x having length in that range, in overall O(nk) time. Further, monotonicity conditions are introduced and studied for the probability and expected frequency of a substring under extension, increased number of errors, or both. Over intervals of constant frequency count, these monotonicities translate to some of the scores in use, thereby reducing the size of tables at the outset and enhancing the process of discovery. These latter derivations extend to patterns with mismatches an analysis previously devoted to exact patterns. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2005.09.017 | Discrete Applied Mathematics |
Keywords | Field | DocType |
expected frequency,constant frequency count,overall o,monotone score,k substitution,automated discovery,motif discovery,error threshold k,k mismatches,certain monotonicities,candidate over-represented word,length range,pattern matching,error threshold,motif | Discrete mathematics,Monotonic function,Combinatorics,Substring,Expected value,Preprocessor,Probability distribution,Partition (number theory),Pattern matching,Mathematics,Monotone polygon | Journal |
Volume | Issue | ISSN |
155 | 6-7 | Discrete Applied Mathematics |
Citations | PageRank | References |
10 | 0.77 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Apostolico | 1 | 1441 | 182.20 |
| Cinzia Pizzi | 2 | 139 | 15.73 |