Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching

Qinru Qiu, Daniel Burns, Prakash Mukre, Qing Wu

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

3 Scopus citations

Abstract

A large and reliable DNA codeword library is key to the success of DNA based computing. Searching for sets of reliable DNA codewords is an NP-hard problem, which can take days on 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 multi-deme genetic algorithm (GA) for the application of DNA codeword searching. The presented architecture provides more than 1000X speed-up compared to a software only implementation. A code extender that uses exhaustive search to produce locally optimum codes in about 1.5 hours for the case of length 16 codes is also described. The experimental results demonstrate that the GA can find ∼99% of the words in locally optimum libraries. Finally, we investigate the performance impact of migration, mating and mutation functions in the hardware accelerator. The analysis shows that a modified GA without mating is the most effective for DNA codeword searching.

Original languageEnglish (US)
Title of host publicationProceedings of GECCO 2007
Subtitle of host publicationGenetic and Evolutionary Computation Conference
Pages1349-1356
Number of pages8
DOIs
StatePublished - Aug 27 2007
Externally publishedYes
Event9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007 - London, United Kingdom
Duration: Jul 7 2007Jul 11 2007

Publication series

NameProceedings of GECCO 2007: Genetic and Evolutionary Computation Conference

Other

Other9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007
CountryUnited Kingdom
CityLondon
Period7/7/077/11/07

Keywords

  • DNA
  • Genetic algorithm
  • Hardware acceleration

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching'. Together they form a unique fingerprint.

  • Cite this

    Qiu, Q., Burns, D., Mukre, P., & Wu, Q. (2007). Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching. In Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference (pp. 1349-1356). (Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/1276958.1277211