TY - JOUR
T1 - A Theoretical Study of Extreme Parallelism in Sequence Alignments
AU - Chung-E Wang
JO - Journal of Information and Computing Science
VL - 4
SP - 264
EP - 274
PY - 2024
DA - 2024/01
SN - 8
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jics/22602.html
KW - Sequence alignment, sequence database search, Smith-Waterman algorithm, parallel algorithm, 
VLSI circuit, pipelined architecture, de novo assembly, overlap-layout-consensus approach. 

AB -  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.