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

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 n² 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.