Rational design of DNA sequences for nanotechnology, microarrays and molecular computers using Eulerian graphs

Abstract

Nucleic acids are molecules of choice for both established and emerging nanoscale technologies. These technologies benefit from large functional densities of 'DNA processing elements' that can be readily manufactured. To achieve the desired functionality, polynucleotide sequences are currently designed by a process that involves tedious and laborious filtering of potential candidates against a series of requirements and parameters. Here, we present a complete novel methodology for the rapid rational design of large sets of DNA sequences. This method allows for the direct implementation of very complex and detailed requirements for the generated sequences, thus avoiding 'brute force' filtering. At the same time, these sequences have narrow distributions of melting temperatures. The molecular part of the design process can be done without computer assistance, using an efficient 'human engineering' approach by drawing a single blueprint graph that represents all generated sequences. Moreover, the method eliminates the necessity for extensive thermodynamic calculations. Melting temperature can be calculated only once (or not at all). In addition, the isostability of the sequences is independent of the selection of a particular set of thermodynamic parameters. Applications are presented for DNA sequence designs for microarrays, universal microarray zip sequences and electron transfer experiments.

Figure 1

Schematic representation of transformation of a given DNA sequence into Eulerian graph Γ_nn and its adjacency matrix A(Γ_nn). (A) Graphical representation of the transformation showing annealing of identically labeled vertices into final form of Γ_nn. Construction of adjacency matrix A(Γ_nn) follows established mathematical rules. (B) Correspondence of matrix elements of A(Γ_nn) and entries in the first term of Equation 1.

Figure 2

Example of construction of adjacency matrix A(Γ_nn) and corresponding Eulerian graph Γ_nn using the set of structural requirements defined in the text. (A) Initial form of matrix A(Γ_nn) after implementation of requirements for length, nucleobase composition, presence of only one ∼TT∼ and ∼CC∼ motif and absence of ∼CA∼ and ∼AG∼ stacking interactions in all generated contextually isostable sequences. (B) First intermediate form of the adjacency matrix A(Γ_nn) after relations between diagonal and off-diagonal elements were used to fill the C-row and column. (C) Second intermediate form of A(Γ_nn) with elements a_AT and a_TG determined by the rules of Equation 3 (see text for details). (D) Final form of the A(Γ_nn) with remaining off-diagonal elements calculated from the previous intermediate form. (E) Eulerian graph Γ_nn defined by A(Γ_nn) (F) Distribution of T_m predicted for contextually nn-isostable sequences generated from the graph E using nnn-level of thermodynamic formulation of Equation 1w ith parameters from (2).

Figure 3

Schematic example of our algorithm that generates sets of contextually isostable DNA sequences from basic cycles γ_k defined by decomposition of the Eulerian graph Γ_nn. (A) Given its connectivity, the original graph Γ_nn is decomposed of into three basic cycle subgraphs γ_a + 2γ_b. (B) The first level of building template structures T from γ_k is demonstrated. All four possible ways of annealing one basic cycle γ_a to another basic cycle γ_b via identical vertices are shown (A–D). (C) Completion of the template structures T by annealing the second basic cycle γ_b to intermediate structure A from level B. Final template A-A1 means that the intermediate structure A is connected to the second γ_bvia the upper left A-vertex. Final template A-A2 means that the intermediate structure A is connected to the second γ_b via the lower right A-vertex and so forth. The remaining templates [derived from (B) to (D)] are omitted for clarity. (D) Left panel: The complete set of sequences as read from all final templates, starting at base A. Central panel: Selection of a unique sequence set from the complete list. Reduction in the number of sequences is the consequence of many identities among templates, which, in turn, is a consequence of the symmetry of graph Γ_nn. This redundancy is only generated due to the ‘manual’ nature of the construction for demonstration purposes. However, in the final software implementation, these redundancies are avoided. Right panel: the final set of contextually isostable sequences generated by systematic permutation of the permutable segments.

Figure 4

Schematic representation of how to generate the set of sequences that are contextually isostable at the next-nearest-neighbor level. The ‘mother’ oligomer ATGACATGATCATCA is converted into template graphs T^* by a systematic search for identically oriented 2-, 3- and 4-tuples. If more than one n-tuple is found in the sequence, they are combined into the node vertex of T^*. This operation defines permutable segments. Their systematic permutation yields the contextually isostable ‘daughter’ oligomers, shown in the central panel. For comparison, multiple alignment of the resulting sequences using ClustalW is shown.

Figure 5

Design of permutable blocks for the synthesis of contextually isostable zip-code sequences for universal microarrays. (A) Demonstration of the topology of template graph T^* (top) and several arrangements of the permutable segments in the final zip-code templates. The permutable segments have different lengths to minimize cross-hybridization that derives from the periodicity of the zip sequences. The different shading of the template vertices demonstrates that contextual isostability is a property derived from the template graph topology, rather than from the concrete nucleobase identities. Vertices in the permutable blocks can be arbitrarily filled with any nucleobase. As long as these vertex assignments remain unchanged throughout the permutation, the resulting set of sequences will be contextually isostable. This increases the overall effectivity of the design: Once the satisfactory (sub)set of contextually isostable zip-sequences is selected, its common thermodynamic properties can be fine-tuned by systematic replacement of the nucleobases in the oligomers. (B) An example of how to adjust the T_m for contextually nn-isostable 37mers, generated from eight permutable segments that are defined by the common template T^*. The assignments of nucleobases to vertices in the right template (set 2) were generated by systematic replacements of A→G, T→C, C→A and G→T in the left template (set 1). The resulting block permutation yielded 40 320 sequences. T_m predictions were calculated for these two series using all four selections of node base X = A, T, C and G. See Table 2 for results.

Figure 6

Graph-based design of generalized permutable blocks for the generation of at least 4000 contextually isostable sequences with a given subset of next-nearest-neighbor (nnn-) interactions. This graph facilitates the feasibility analysis for the use of such sequences in n-mer-based universal microarrays for expression profiling (80). See text for details.

Figure 7

Histograms of T_m calculated on nn-level of approximation for sets of probes of 49 yeast ORFs. (A) Affymetrix probe set (935) from yeast S98 microarray. (B) Probes designed by our method with up to three mismatched bases between daughter and target sequences (853). (C) Probes designed with up to two mismatched bases between daughter and target sequences (795). (D) Probes designed with up to one mismatched base between daughter and target sequences (786). (E) Probes designed with no mismatched bases between daughter and target sequences (744).