@Article{JICS-8-264,
author = {Chung-E Wang},
title = {A Theoretical Study of Extreme Parallelism in Sequence Alignments},
journal = {Journal of Information and Computing Science},
year = {2024},
volume = {8},
number = {4},
pages = {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. 
},
issn = {1746-7659},
doi = {https://doi.org/},
url = {http://global-sci.org/intro/article_detail/jics/22602.html}
}