A Theoretical Study of Extreme Parallelism in Sequence Alignments
Year: 2013
Journal of Information and Computing Science, Vol. 8 (2013), Iss. 4 : pp. 264–274
Abstract
In this paper, we describe fully parallelized architectures for one-to-one, one-to-many, and many-to-many sequence alignments using Smith-Waterman algorithm. The architectures utilize the principles of parallelism and pipelining to the greatest extent in order to take advantage of both intra- sequence and inter-sequence parallelization and to achieve high speed and throughput. First, we describe a parallelized Smith-Waterman algorithm for general single instruction, multiple data (SIMD) computers. The algorithm has an execution time of O(m+n), where m and n are the lengths of the two biological sequences to be aligned. Next, we propose a very-large-scale integration (VLSI) implementation of the parallel algorithm. Thirdly, we incorporate a pipelined architecture into the proposed VLSI circuit, producing a pipelined processor that can align a query sequence with a database of sequences at the speed of O(m+n+L), where m is the length of the query sequence and n and L are the maximum length and the number of sequences in the database, respectively. Finally, we make use of our pipeline architecture to perform all possible pairs of pair-wise alignments for a group of L sequences with a maximum sequence length of m in O(mL) time. Checking all pairs of pair-wise alignments is essential to the overlap-layout-consensus (OLC) approach for de novo assembly.
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2024-JICS-22602
Journal of Information and Computing Science, Vol. 8 (2013), Iss. 4 : pp. 264–274
Published online: 2013-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 11