Multiple Sequence Alignment on an FPGA

Molecular Biologists frequently compute multiple sequence alignments (MSAs) to identify similar regions in protein families. Progressive alignment is a widely used approach to compute MSAs. However, aligning a few hundred sequences by popular progressive alignment tools requires several hours on sequential computers. Due to the rapid growth of biological sequence databases biologists have to compute MSAs in a far shorter time. In this paper we present a new approach to MSA on reconfigurable hardware platforms to gain high performance at low cost. To derive an efficient mapping onto this type of architecture, fine-grained parallel processing elements (PEs) have been designed. Using this PE design as a building block we have constructed a linear systolic array to perform a pairwise sequence distance computation using dynamic programming. This results in an implementation with significant runtime savings on a standard off-the-shelf FPGA.