The Teiresias algorithm is a combinatorial algorithm for the discovery of rigid patterns in biological sequences. It is named after the Greek prophet Teiresias and was created in 1997 by Isidore Rigoutsos and Aris Floratos. The problem of finding sequence similarities in the primary structure of related proteins or genes arises in the analysis of biological sequences. It can be shown that pattern discovery in its general form is NP-hard. The Teiresias algorithm is based on the observation that if a pattern spans many positions and appears exactly k times in the input then all fragments of the pattern have to appear at leastk times in the input. The algorithm is able to produce all patterns that have a user-defined number of copies in the given input, and manages to be very efficient by avoiding the enumeration of the entire space. Finally, the algorithm reports motifs that are maximal in both length and composition. A new implementation of the Teiresias algorithm was recently made available by the. Teiresias is also accessible through an interactive web-based user interface by the same center. See external links for both.
Pattern description
The Teiresias algorithm uses regular expressions to define the patterns. This allows the patterns reported to consist not only from the characters that appear in each position but from a specific group of characters or even from any character. The patterns created by the algorithm are patterns that have at least k instances in the input, where L ≤ W and L, W, k positive integers. A pattern is called an pattern if and only if any L consecutive literals or bracketed literals span at most W positions. The algorithm reports only maximal patterns. Given a set of sequences S, a pattern P that appears k times in S is called maximal if and only if there exists no pattern P' which is more specific than P and also appears exactly k times in S. If there exists such a pattern P' then we say that P cannot be maximal and P is considered to be subsumed by P'. A pattern P' is said to be more specific than a pattern P if and only if P' can be obtained from P by dereferencing a wild card or instantiating a bracketed literal to a literal, or appending a string of literals, bracketed literals or/and wild cards to the right of P, or prepending a string of literals, bracketed literals or/and wild cards to the left of P.
Algorithm description
Teiresias consists of two phases, Scanning and Convolution. During the first phase the input is scanned for the patterns that satisfy the minimum requirements, the elementary patterns. The elementary patterns consist of exactly L literals and/or bracketed literals and includes at most W-L wild cards. During convolution, the elementary patterns are recursively combined and maximal patterns are created. The order in which the convolutions are performed is very important since it guarantees that all patterns will be generated and all maximal patterns are generated before all the patterns that are subsumed by them. The order is dictated by the following rules
The priority of each pattern is defined by its contents from left to right.
A literal has higher priority than a bracketed literal and both have higher priority than wild cards.
Longer patterns have higher priority than shorter ones.
Ties are resolved alphabetically.
Given the assurance that all maximal patterns will be created first, it is easy to check a newly created pattern against all maximal ones to ensure that it is subsumed, in which case it is discarded. If the newly created pattern is not subsumed then it is added to the list of maximal patterns. When no more patterns can be combined to form new maximal patterns then the algorithm terminates. The length of any maximal pattern is bounded from above by the length of the longest input sequence.
Time complexity
The algorithm is "output-sensitive." The time complexity of the TEIRESIAS algorithm is where L and W are user-specified parameters that define the "minimum density" of a pattern, m is the number of characters the input includes, C ≤ 1 is the average number of patterns found in a hash entry, tH is the time needed for locating the hash entry corresponding to any given hash value, and the summation Σ is the maximum number of patterns that will ever be placed in the stack that keeps the patterns for extension during convolution.
