Treffer: Minimized compact automaton for clumps over degenerate patterns.

Clumps are sequences of overlapping occurrences of a given pattern that play a vital role in the study of distribution of pattern occurrences. These distributions are used for finding functional fragments in biological sequences. In this paper we present a minimized compacted automaton (Overlap walking automaton, OWA) recognizing all the possible clumps for degenerate patterns and its usage for computation of probabilities of sets of clumps. We also present Aho–Corasick like automaton, RMinPatAut , recognizing all the sequences ending with pattern occurrences. The states of RMinPatAut are equivalence classes on the prefixes of the pattern words. We use RMinPatAut as an auxiliary structure for OWA construction. For degenerate patterns, RMinPatAut is Nerode-minimal, i.e., minimal in classical sense. In this case RMinPatAut can be constructed in linear time on the number of its states (it is bounded by 2 m , where m the length of pattern words). OWA can be constructed in linear time on the sum of its size and RMinPatAut size. [ABSTRACT FROM AUTHOR]