Automated constraint-based nucleotide sequence selection for DNA computation

We present techniques for automating the design of computational systems built using DNA, given a set of high-level constraints on the desired behavior and performance of the system. We have developed a program called SCAN that exploits a previously implemented computational melting temperature primitive to search a 'nucleotide space' for sequences satisfying a pre-specified set of constraints, including hybridization discrimination, primer 5' end and 3' end stability, secondary structure reduction, and prevention of oligonucleotide dimer formation. The first version of SCAN utilized 24 h of computer time to search a space of over 7.5 billion unary counter designs and found only nine designs satisfying all of the pre-specified constraints. One of SCAN's designs has been implemented in the laboratory and has shown a marked improvement in performance over the products of previous attempts at manual design. We conclude with some novel ideas for improving the overall speed of the program that offer the promise of an efficient method for selecting optimal nucleotide sequences in an automated fashion. (C) 1999 Elsevier Science Ireland Ltd. All rights reserved.