Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology (1995)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

SEEING CONSERVED SIGNALS: USING ALGORITHMS TO DETECT SIMILARITIES BETWEEN BIOSEQUENCES 79 N, there are algorithms that solve the text searching problem in O(P+N), O(PN), and O(PN3) time, depending on whether the pattern is a simple sequence, a regular expression, or context-free language, respectively. Fusing the concept of exact pattern matching and sequence comparison gives rise to the class of approximate pattern matching problems. Given a pattern, a database, a scoring scheme, and a threshold, one seeks all substrings of the database that align to some sequence denoted by the pattern with score better than the threshold. In essence, one is looking for substrings that are within a given similarity neighborhood of an exact match to the pattern. Within this framework, the similarity search problem is an approximate pattern matching problem where the pattern is a simple sequence. We showed earlier that this problem can be solved in O(PN) time. For the case of regular expressions, the approximate match problem can also be solved in O(PN) time (Myers and Miller, 1989), and, for context-free languages, an O(PN3) algorithm is known (Myers, 1994a). While the cost of searching for approximate matches to context-free languages is prohibitive, searching for approximate matches to regular expressions is well within reason and finds applications in searching for matches to structural patterns that occur in proteins. Parallel Computing The basic problem of comparing sequences has resisted better than quadratic, O(MN) time algorithms. This has led several investigators to study the use of parallel computers to achieve greater efficiency. As stated above, the S-matrix can be computed in any order consistent with the data dependencies of the fundamental recurrence. One naturally thinks of a row-by-row or column-by-column evaluation, but we pointed out as a third alternative that one could proceed in order of antidiagonals. Let antidiagonal k be the set of entries {(i j): i + j = k}. Note that to compute antidiagonal k, one only needs antidiagonals k − 1 and k − 2. The critical observation for parallel processing is that each entry in this antidiagonal can be computed independently of the other entries in the antidiagonal, a fact not true of the row-by-row and column-by-column 

SEEING CONSERVED SIGNALS: USING ALGORITHMS TO DETECT SIMILARITIES BETWEEN BIOSEQUENCES 80 evaluation procedures. For large SIMD (single-instruction, multiple-data) machines, a processor can be assigned to each entry in a fixed antidiagonal and compute its result independently of the others. With O(M) processors, each antidiagonal can be computed in constant time, for a total of O(N) total elapsed time. Note that total work, which is the product of processors and time per processor, is still O(MN). The improvement in time stems from the use of more processors, not from an intrinsically more efficient algorithm. This observation about antidiagonals has been used to design custom VLSI (very large scale integration) chips configured in what is called a systolic array. The ''array" consists of a vector of processors, each of which is identical, performs a dedicated computation, and communicates only with its left and right neighbors, making it easy to lay out physically on a silicon wafer. For sequence comparisons, processor i computes the entries for row i and contains three registers that we will call L(i), V(i), and U(i). At the completion of the kth step, the processors contain antidiagonals k and k − 1 in their L and V registers, respectively, and the characters of B flow through their U registers. That is, L(i)k = S(i, k − i − 1), V(i)k = S(i, k − i), and U(i)k = bk−i , where X(i)k denotes the value of register X at the end of the kth step. It follows from the basic recurrence for S-values that the following recurrences correctly express the values of the registers at the end of step k + 1 in terms of their values at the end of step k: These recurrences reveal that to accomplish step k + 1, processor i − 1 must pass its register values to processor i and each processor must have just enough hardware to perform three additions and a three-term maximum. Moreover, each processor must have a (2|ψ|+1)-element