Imposed constraints on the smith-waterman alignment algorithm for enhanced modeling of a single-molecule DNA sequencer

Patrick G. Humphrey, Gregory R. Bashford

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

Abstract

An effort has been underway to develop a system for de novo sequencing of single DNA molecules with very long reads. The system operates by optically detecting the passage of fluorescently tagged DNA bases through a detection zone. A successful system would be revolutionary with respect to speed, read length, cost and minimized laboratory infrastructure. An important part of system development is modeling of the detection process. In particular, predicting the expected error from a set of sequencing parameters is helpful in system design. This paper describes variations on the Smith-Waterman algorithm for subsequence alignment used in a single-molecule detection model. The alignment algorithm is used to check the modeled output sequence generated from a known input sequence. Variations based on reasonable assumptions led to over an order of magnitude improvement in alignment speed.

Original languageEnglish (US)
Title of host publication2005 IEEE International Conference on Electro Information Technology
StatePublished - 2005
Event2005 IEEE International Conference on Electro Information Technology - Lincoln, NE, United States
Duration: May 22 2005May 25 2005

Publication series

Name2005 IEEE International Conference on Electro Information Technology
Volume2005

Conference

Conference2005 IEEE International Conference on Electro Information Technology
CountryUnited States
CityLincoln, NE
Period5/22/055/25/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Imposed constraints on the smith-waterman alignment algorithm for enhanced modeling of a single-molecule DNA sequencer'. Together they form a unique fingerprint.

  • Cite this

    Humphrey, P. G., & Bashford, G. R. (2005). Imposed constraints on the smith-waterman alignment algorithm for enhanced modeling of a single-molecule DNA sequencer. In 2005 IEEE International Conference on Electro Information Technology [1627002] (2005 IEEE International Conference on Electro Information Technology; Vol. 2005).