Hybrid architecture for accelerating DNA codeword library searching

Qinru Qiu, Daniel Burns, Qing Wu, Prakash Mukre

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

3 Scopus citations

Abstract

A large and reliable DNA codeword library is the key to the success of DNA based computing. Searching for the set of reliable DNA codewords is an NP-hard problem, which can take days on the state-of-art high performance cluster computers. This work presents a hybrid architecture that consists of a general purpose microprocessor and a hardware accelerator for accelerating the discovery of DNA reverse complement, edit distance codes. Two applications of this architecture were implemented and evaluated, including a code generator that uses a genetic algorithm (GA) to produce nearly locally optimal codes in a few minutes, and a code extender that uses exhaustive search to produce locally optimum codes in about 1.5 hours for the case of length 16 codes. The experimental results demonstrate that the GA can find ~99% of the words in locally optimum libraries, and that the hybrid architecture provides more than 1000X speed-up compared to a software only implementation.

Original languageEnglish (US)
Title of host publication2007 IEEE Symposium on Computational Intelligence and Bioinformatics and Computational Biology, CIBCB 2007
Pages323-330
Number of pages8
StatePublished - Dec 1 2007
Externally publishedYes
Event2007 4th IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2007 - Honolulu, HI, United States
Duration: Apr 1 2007Apr 5 2007

Publication series

Name2007 IEEE Symposium on Computational Intelligence and Bioinformatics and Computational Biology, CIBCB 2007

Other

Other2007 4th IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2007
CountryUnited States
CityHonolulu, HI
Period4/1/074/5/07

ASJC Scopus subject areas

  • Artificial Intelligence
  • Biomedical Engineering
  • Health Informatics

Fingerprint Dive into the research topics of 'Hybrid architecture for accelerating DNA codeword library searching'. Together they form a unique fingerprint.

  • Cite this

    Qiu, Q., Burns, D., Wu, Q., & Mukre, P. (2007). Hybrid architecture for accelerating DNA codeword library searching. In 2007 IEEE Symposium on Computational Intelligence and Bioinformatics and Computational Biology, CIBCB 2007 (pp. 323-330). [4221240] (2007 IEEE Symposium on Computational Intelligence and Bioinformatics and Computational Biology, CIBCB 2007).