Multiple Sequence Alignment (MSA) is a fundamental analysis method used in bioinformatics and many comparative genomic applications. The time to compute an optimal MSA grows exponentially with respect to the number of sequences. Consequently, producing timely results on large problems requires more efficient algorithms and the use of parallel computing resources. Reconfigurable computing hardware provides one approach to the acceleration of biological sequence alignment. Other acceleration methods typically encounter scaling problems that arise from the overhead of inter-process communication and from the lack of parallelism. Reconfigurable computing allows a greater scale of parallelism with many custom processing elements that have a low-overhead interconnect. The proposed parallel algorithms and architecture accelerate the most computationally demanding portions of MSA. An overall speedup of up to 150 has been demonstrated on a large data set when compared to a single processor. The reduced runtime for MSA allows researchers to solve the larger problems that confront biologists today.
College and Department
Physical and Mathematical Sciences; Computer Science
BYU ScholarsArchive Citation
Lloyd, G Scott, "Accelerated Large-Scale Multiple Sequence Alignment with Reconfigurable Computing" (2011). All Theses and Dissertations. 2729.
communication network, communication protocol, computer architecture, interface, modules, dynamic programming, field-programmable gate array, FPGA, sequence alignment, reconfigurable hardware, traceback