Speeding up genome computation with a systolic accelerator
Dominique D. Lavenier · 2001
The comparison of dna or protein sequences is a fundamental task in molecular biology that occurs in a variety of ways. The goal is to find similarities, areas which share common subsequences, between sequences. The operation can range from sequencing of dna molecules to database scanning. Similarities are detected by algorithms whose computational complexities are quadratic with respect to the length of the sequences. This is timeconsuming when a large amount of data (a large set of sequences, which is also called a bank) must be processed. Several approaches exist to speed-up the computation. The simplest approach is to wait for technology to improve processor speed. This approach is not very fruitful since biological databases are growing at a exponential rate. Every year the size of the banks are scaled by a factor ranging from 1.5 to 2. This exceeds the growth rate of processor performance. Another solution which has been widely adopted consists of introducing heuristics into the comparison algorithms. This is a very efficient method. Speed-ups between 10 to 100 can be achieved. There are two major drawbacks to heuristics. They cannot be applied to all comparison algorithms, and if they are they may seriously diminish the quality of results. In practice, when a heuristic is efficient at reducing the execution time, its resultant quality is lower. A last alternative to get high quality results in a short time is through parallel computation. Three possibilities exist for this approach. Massively parallel machines, networks of workstations, or dedicated hardware. The first