Title: High-speed Multiple Sequence Alignment on a reconfigurable platform

Authors: Tim Oliver, Bertil Schmidt, Douglas Maskell, Darran Nathan, Ralf Clemens

Addresses: School of Computer Engineering, Nanyang Technological University, 639798, Singapore. ' School of Computer Engineering, Nanyang Technological University, 639798, Singapore. ' School of Computer Engineering, Nanyang Technological University, 639798, Singapore. ' Project Proteus, School of Engineering, Ngee Ann Polytechnic, 599489, Singapore. ' Project Proteus, School of Engineering, Ngee Ann Polytechnic, 599489, Singapore

Abstract: Progressive alignment is a widely used approach to compute multiple sequence alignments (MSAs). However, aligning several hundred sequences by popular progressive alignment tools requires hours on sequential computers. Due to the rapid growth of 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. We have constructed a linear systolic array to perform pairwise sequence distance computations using dynamic programming. This results in an implementation with significant runtime savings on a standard FPGA.

Keywords: multiple sequence alignment; MSA; ClustalW; reconfigurable computing; fine-grained parallelism; FPGA; bioinformatics research; bioinformatics applications; high performance computing; systolic array; pairwise sequence distance.

DOI: 10.1504/IJBRA.2006.011038

International Journal of Bioinformatics Research and Applications, 2006 Vol.2 No.4, pp.394 - 406

Published online: 05 Oct 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article