Hardware Acceleration Of Multi-Deme Genetic Algorithm for DNA Codeword Searching
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2008
- Accession Number
- ADA597344
Entities
People
- Daniel Burns
- Prakash Mukre
- Qing Wu
- Qinru Qiu
Organizations
- Air Force Research Laboratory