High-speed implementation of smith-waterman algorithm for DNA sequence scanning in VLSI

Chao Cheng, Keshab K Parhi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In this paper, a novel pipelined algorithm is applied in the hardware implementation of Smith-Waterman algorithm. The proposed algorithm can cut down the computation time from O(m+n) to O(m+n/J), where J is the pipeline level, m and n are the lengths of the query sequence and subject sequence respectively. It's obvious that if the length of subject sequence is much larger than the query sequence, i.e., nm, the computation of scanning protein sequences will be speeded up by a factor of J.

Original languageEnglish (US)
Title of host publication2008 42nd Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2008
Pages1528-1533
Number of pages6
DOIs
StatePublished - Dec 1 2008
Event2008 42nd Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2008 - Pacific Grove, CA, United States
Duration: Oct 26 2008Oct 29 2008

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393

Other

Other2008 42nd Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2008
CountryUnited States
CityPacific Grove, CA
Period10/26/0810/29/08

Keywords

  • DNA sequence
  • FPGA
  • Look-ahead pipelining
  • Smith-Waterman Algorithm
  • VLSI

Fingerprint Dive into the research topics of 'High-speed implementation of smith-waterman algorithm for DNA sequence scanning in VLSI'. Together they form a unique fingerprint.

  • Cite this

    Cheng, C., & Parhi, K. K. (2008). High-speed implementation of smith-waterman algorithm for DNA sequence scanning in VLSI. In 2008 42nd Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2008 (pp. 1528-1533). [5074677] (Conference Record - Asilomar Conference on Signals, Systems and Computers). https://doi.org/10.1109/ACSSC.2008.5074677