Sequence analysis with the Kestrel SIMD parallel processor

Computer aided sequence analysis is a critical aspect of current bi-ological research. Sequence information from the genome sequencing projects lls databases so quickly that humans cannot examine it all. Hence there is a heavy reliance on computer algorithms to point out the few important nuggets for human examination. Sequence search algo-rithms range from simple to complex, as does the representation of the biological data. Typically though, simple algorithms are used on the simplest of data representations because of the large computational de-mands of anything more complex. This leads to missed hits because the simple search techniques are often not suÆciently sensitive. Here we describe the implementation of several sensitive sequence analysis algorithms on the Kestrel parallel processor, a single-instruction multiple-data (SIMD) processor developed and built at UCSC. Perfor-mance of the Smith-Waterman and Hidden Markov Model algorithms, with both Viterbi and Expectation Maximization methods ranges from 6 to 20 times faster than standard computers