An FPGA Implementation of Multiple Sequence Alignment Based on Carrillo-Lipman Method

Multiple sequence alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. In this paper, we describe a compact system with an FPGA board and a host computer for multiple sequence alignment based on Carrillo-Lipman method. In our system, two dimensional dynamic programming is repeatedly applied along other dimensions to realize multidimensional search with a simple and common architecture, and unnecessary parts of the search space for finding the optimal alignment are skipped using Carrillo-Lipman method to reduce the computation time.