Molecular biologists use hidden Markov models (HMMs) as a popular tool to statistically describe biological sequence families. This statistical description can then be used for sensitive and selective database scanning, e.g., new protein sequences are compared with a set of HMMs to detect functional similarities. Efficient dynamic-programming algorithms exist for solving this problem; however, current solutions still require significant scan times. These scan time requirements are likely to become even more severe due to the rapid growth in the size of these databases. This paper shows how reconfigurable architectures can be used to derive an efficient fine-grained parallelization of the dynamic programming calculation. We describe how this technique leads to significant runtime savings for HMM database scanning on a standard off-the-shelf field-programmable gate array (FPGA).

Profile hidden Markov models (profile HMMs) are used as a popular bioinformatics tool for sensitive database searching, e.g. a set of not annotated protein sequences is compared to a database of profile HMMs to detect functional similarities. HMMer is a commonly used package for profile HMM-based methods. However, searching large databases with HMMer suffers from long runtimes on traditional computer architectures. These runtime requirements are likely to become even more severe due to the rapid growth in size of both sequence and model databases. In this paper, we present a new reconfigurable architecture to accelerate HMMer database searching. It is described how this leads to significant runtime savings on off-the-shelf field-programmable gate arrays (FPGAs).

This paper explores the use of pre-routed cores as execution objects in an object-oriented programming model and execution environment for dynamic computing on FPGA. In order to maintain FPGA computing performance it is crucial to thoroughly analyze the issues at the lowest level of device detail in order to ensure that computing circuit encapsulation is as efficient as possible. The first methodology that allows a core to scale its interface bandwidth to the maximum available in a routing channel was presented. Cores can be constructed independently from the rest of the system using a framework that is independent of the method used to place and route primitive components within the core. The authors used an architecture model and CAD tools that mirror those used in industry. Abutting cores are instantly connected by co-location of interface wires. Eliminating run-time routing drastically reduces the time taken to construct a system using a set of cores. It was illustrated how, although pre-routing has an adverse impact on core performance by up to 14%, it can improve functional density by up to six times for rapid reconfiguration

Protein sequences with unknown functionality are often compared to a set of known sequences to detect functional similarities. Efficient dynamic-programming algorithms exist for solving this problem, however current solutions still require significant scan times. These scan time requirements are likely to become even more severe due to exponential database growth. In this paper we present a new approach to bio-sequence database scanning using re-configurable FPGA-based hardware platforms to gain high performance at low cost. Efficient mappings of the Smith-Waterman algorithm using fine-grained parallel processing elements (PEs) that are tailored towards the parameters of a query have been designed. We use customization opportunities available at run-time to dynamically hyper customize the systolic array to make better use of available resource. Our FPGA implementation achieves a speedup of approximately 170 for linear gap penalties and 125 for affine gap penalties as compared to a standard desktop computing platform. We show how hyper-customization at run-time can be used to further improve the performance.

Summary: Aligning hundreds of sequences using progressive alignment tools such as ClustalW requires several hours on state-of-the-art workstations. We present a new approach to compute multiple sequence alignments in far shorter time using reconfigurable hardware. This results in an implementation of ClustalW with significant runtime savings on a standard off-the-shelf FPGA. Availability: An online server for ClustalW running on a Pentium IV 3 GHz with a Xilinx XC2V6000 FPGA PCI-board is available at http://beta.projectproteus.org. The PE hardware design in Verilog HDL is available on request from the first author. Contact: [email protected]

Summary form only given. Molecular biologists frequently compare an unknown protein sequence with a set of other known sequences (a database scan) to detect functional similarities. Even though efficient dynamic programming algorithms exist for the problem, the required scanning time is still very high, and because of the rapid database growth finding fast solutions is of highest importance to research in this area. We present a new approach to biosequence database scanning on reconfigurable hardware platforms to gain high performance at low cost. To derive an efficient mapping onto this type of architecture, we have designed fine-grained parallel processing elements (PEs). Since our solution is based on reconfigurable hardware, we can design PEs that are tailored towards the parameters of a query. This results in an implementation with significant runtime savings on a standard off-the-shelf FPGA.