PMC:1459173 / 1514-3156 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1459173","sourcedb":"PMC","sourceid":"1459173","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1459173","text":"Let s be a sequence of sets of characters from an alphabet Σ ⋃ {·}, where '.' ∉ Σ denotes a don't care (dot, for short) and the rest are solid characters, we use σ to denote a singleton character. For characters e1 and e2, we write e1 ∘ e2 if and only if e1 is a dot or e1 = e2. Allowing for spacers in a string is what makes it extensible. Such spacers are indicated by annotating the dot characters. Specifically, an annotated \".\" character is written as .α where α is a set of positive integers {α1, α2, ..., αk} or an interval α = [αl, αu], representing all integers between αl and αu including αl and αu. Whenever defined, d will denote the maximum number of consecutive dots allowed in a string. In such cases, for clarity of notation, we use the extensible wild card denoted by the dash symbol \"-\" instead of the annotated dot character, .[1,d] in the string. Note that '-' ∉ Σ. Thus a string of the form a.[1,d]b will be simply written as a-b. A motif m is extensible if it contains at least one annotated dot, otherwise m is rigid. Given an extensible string m, a rigid string m' is a realization of m if each annotated dot .α is replaced by l ∈ α dots. The collection of all such rigid realizations of m is denoted by R(m). A rigid string m occurs at position l on s if m[j] ∘ s[l + j - 1] holds for 1 ≤ j ≤ |m|. An extensible string m occurs at position l in s if there exists a realization m' of m that occurs at l. Note than an extensible string m could possibly occur more than once at a location on a sequence s. Throughout in the discussion we are interested mostly in the (unique) first left-most occurrence at each location.","tracks":[]}