Hardware accelerated design of non-crosshybridizing DNA libraries using the LLCS and pairwise nearest-neighbor model duplex stability metrics

Daniel J. Burns, Qinru Qiu, Prakash Mukre, Qing Wu, Thomas E. Renz

Research output: Contribution to conferencePaper

Abstract

The design of large and high quality non-hybridizing DNA Libraries is motivated by proposed schemes for nano-structure self-assembly, as well as their use in biological assays and analysis methods, as a means for encoding data onto synthetic DNA, and as physical taggants. In this poster paper we describe an approach to this design problem that uses reconfigurable hardware acceleration methods to speed both a design algorithm and the computationally expensive DNA binding affinity metric calculations that can consume up to 98% of design run times, and we summarize experimental results obtained using this approach. For example, we have developed a single chip FPGA design that integrates a hardware genetic algorithm (HGA), 2D systolic arrays for efficiently calculating either the Length of the Longest Common Sequence (LLCS, or Edit Distance) metric or the Pair-wise Nearest Neighbor Model (PNNM), and reverse compliment (RC) constraint checking, and also a second FPGA design that implements hardware exhaustive search (HES) that extends libraries by screening all possible oligo-mers (mers) of the desired length. Using a $2K PCMCIA FPGA card hosted in a notebook PC to implement this design, we have demonstrated a speed-up of ~1,000X over software when building 16mer DNA LLCS RC libraries. Using a $16K PCI-X board hosted by a workstation to host slightly larger designs, we demonstrated ~250X speed-up over software for building 16mer libraries with constraints based on the much more computationally costly PNNM. Finally, we have also obtained ~30,000X speed-up over software when building 32mer LLCS RC libraries due to n2 scaling vs. mer length in the highly parallel LLCS systolic array. While previous distributed software approaches obtained speed-ups that scaled roughly linearly vs. the number of computing nodes, these hardware acceleration methods require only relatively modest computing platforms, yet offer significant performance improvements and thereby enable new experiments. For example, by running multiple of trails of HGA (10 minutes) followed by HES (~1.5 hours), we observe that the HGA phase finds 98.9% of the words that can be found. Finally, we suggest that these methods can be extended to longer mers, other metrics, and other computation problems that involve DNA.

Original languageEnglish (US)
Pages179-184
Number of pages6
StatePublished - Dec 1 2008
Externally publishedYes
Event5th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2008 - Snowbird, UT, United States
Duration: Apr 22 2008Apr 25 2008

Other

Other5th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2008
CountryUnited States
CitySnowbird, UT
Period4/22/084/25/08

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Hardware accelerated design of non-crosshybridizing DNA libraries using the LLCS and pairwise nearest-neighbor model duplex stability metrics'. Together they form a unique fingerprint.

  • Cite this

    Burns, D. J., Qiu, Q., Mukre, P., Wu, Q., & Renz, T. E. (2008). Hardware accelerated design of non-crosshybridizing DNA libraries using the LLCS and pairwise nearest-neighbor model duplex stability metrics. 179-184. Paper presented at 5th Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2008, Snowbird, UT, United States.