Article

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

Authors:

Qing WuAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1349 - 1356

https://doi.org/10.1145/1276958.1277211

Published: 07 July 2007 Publication History

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.

References

[1]

L. M. Adleman, "Molecular Computation of Solutions to Combinatorial Problems," Science, vol. 266, pp. 1021--1024, November 1994.

[2]

A. Brenneman and A. Condon, "Strand Design for Biomolecular Computation", Theoretical Computer Science, vol. 287, pp.39--58, 2002.

Digital Library

[3]

S.-Y. Shin, I.-H. Lee, D. Kim, and B.-T. Zhang, Multiobjective Evolutionary Optimization of DNA Sequences for Reliable DNA Computing", IEEE Transactions on Evolutionary Computation, vol. 9(20), pp.143--158, 2005.

Digital Library

[4]

F. Tanaka, A. Kameda, M. Yamamoto, and A. Ohuchi, Design of Nucleic Acid Sequences for DNA Computing based on a Thermodynamic Approach, Nucleic Acids Research, 33(3), pp.903--911, 2005.

[5]

J. Santalucia, " A Unified View of polymer, dumbbell, and oligonucleotide DNA nearest neighbor thermodynamics", Proc. Natl. Acad. Sci., Biochemistry, pp. 1460--1465, February 1998.

[6]

A. D'yachkov, P.L. Erdös, A. Macula, V. Rykov, D. Torney, C-S. Tung, P. Vilenkin and S. White, "Exordium for DNA Codes," Journal of Combinatorial Optimization, vol. 7, no. 4, pp. 369--379, 2003.

[7]

R. Deaton, M. Garzon, R.C. Murphy, J.A. Rose, D.R. Franceschetti, and S.E. Jr. Stevens, "Genetic search of reliable encodings for DNA--based computation," Proceedings of the First Annual Conference on Genetic Programming, pp. 9--15, July 1996.

[8]

Bishop, M., Macula, A., Pogozelski, W., and Rykov, V., "DNA Codeword Library Design", Proc. Foundations of Nanoscience -- Self Assembled Architectures and Devices, (FNANO), April 2005.

[9]

Tulpan, D.C., Hoos, H., Condon, A.,"Stochastic Local Search Algorithms for DNA Word Design", Eighth International Meeting on DNA Based Computers(DNA8), June 2002.

Digital Library

[10]

S. Houghten, D. Ashlock and J. Lennarz, "Bounds on Optimal Edit Metric Codes", Brock University Tech. Rer.t # CS-05-07, July 2005.

[11]

O. Milenkovic and N. Kashyap, "On the Design of Codes for DNA Computing," Lecture Notes in Computer Science, pp. 100--119, Springer Verlag, Berlin-Heidelberg, 2006.

Digital Library

[12]

R. Brualdi, and V. Pless, "Greedy Codes," Journal of Combinatorial Theory Series A, vol. 64, pp. 10--30, 1993.

Digital Library

[13]

http://www.xilinx.com/

[14]

http://www.annapmicro.com/

[15]

D. Burns, K. May, T. Renz, and V. Ross, "Spiraling in on Speed-Ups of Genetic Algorithm Solvers for Coupled Non--Linear ODE System Parameterization and DNA Code Word Library Synthesis," MAPLD International Conference, 2005.

[16]

P.D. Michailidis and K.G. Margaritis, "New Processor Array Architectures for the Longest Common Subsequence Problem," The Journal of Supercomputing, vol. 32, pp. 51--69, 2005.

Digital Library

[17]

Y.C. Lin and J.W. Yeh, "A Scalabl and Efficient Systolic Algorithm for the Longest Common subsequence Problem," Journal of Information Science and Engineering, vol. 18, pp. 519--532, 2002

Cited By

Ashlock DHoughten SZhang ABorodovsky MOzsoyoglu GMikler A(2010)Ring optimization of edit metric codes in DNAProceedings of the First ACM International Conference on Bioinformatics and Computational Biology10.1145/1854776.1854809(222-229)Online publication date: 2-Aug-2010
https://dl.acm.org/doi/10.1145/1854776.1854809

Index Terms

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

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an ...
A cloud model based DNA genetic algorithm for numerical optimization problems

Bio-inspired algorithms for optimization are significant topics in the areas of computational intelligence. Traditional genetic algorithm easily gets stuck at a local optimum, and often has slow convergent speed. To overcome these drawbacks, the Cloud ...
An efficient crossover architecture for hardware parallel implementation of genetic algorithm

In this article a new architecture for hardware implementation of genetic algorithm in reconfigurable embedded systems is presented. The main idea is based on the efficient use of a genetic algorithm's crossover operator to enhance the speed of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
251
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ashlock DHoughten SZhang ABorodovsky MOzsoyoglu GMikler A(2010)Ring optimization of edit metric codes in DNAProceedings of the First ACM International Conference on Bioinformatics and Computational Biology10.1145/1854776.1854809(222-229)Online publication date: 2-Aug-2010
https://dl.acm.org/doi/10.1145/1854776.1854809

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten