Tech Report CS-92-22

A Systolic Array for the Sequence Alignment Problem

Dzung T. Hoang

April 1992

Abstract:

This report introduces a new systolic algorithm for the sequence alignment problem. This work builds upon an existing systolic array for computing the edit distance between two sequences. The alignment array is meant to be used as the second phase in a two-phase design, with a modified edit distance array serving as the first phase. An implementation on the SPLASH programmable logic array is described. Because of the extensive pipelining in the systolic array, computing an alignment on the array takes that same amount of time as computing just the edit distance. Compared to conventional computers, SPLASH implementation performs several orders of magnitude faster.

(complete text in pdf or gzipped postscript)