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.