Computation with 3D DNA structures


 

Natasa Jonoska
Department of Mathematics
and
Stephen Karl
Department of Biology
and
Masahico Saito
Department of Mathematics
University of South Florida


 
 


OUTLINE




- Motivation

- Junction molecules

- The 3-vertex colorability problem with DNA graph structures

- Graphs made with single stranded DNA

- Current experiments

- Actions of recombinases and tangles

- Permutations and braids

- Conclusion
 
 



MOTIVATION




$\bullet$ Well established fact that the activation of genes in a cell depends on the three dimensional structure of the DNA within the cell. (A. Rich, M. Frank-Kamenetskii, Cozzarelli, ...)

$\bullet$ Explosion in new laboratory techniques and products of biotechnology. Many three dimensional DNA structures have been formed: DNA polyhedra, a quadrilateral, a truncated octahedron and a cube made of junction molecules; knots (using B and Z form of DNA); Borromean DNA rings, PD-loop using PNA2/DNA triplex, a two dimensional lattice made of DNA tiles...(Seeman, Shen, Winfree, Rich ...)

$\bullet$ Difficulty in describing the information carried within a three dimensional structure by linear means. Example: knots and all the available knot invariants none of which is a complete invariant. (Too many names to mention...)
 
 



JUNCTION MOLECULES




A four armed branched junction molecule
 
 

                               \begin{figure}\begin{center}\mbox{\epsfxsize=2.5in\epsfbox{karmed.eps}}\end{center}\end{figure}
 

- Length of the arms is couple of hundred base pairs

- 3'end is indicated with an arrow

- additional oligo-dT bubbles might be added to the arms for flexibility
 
 



THE 3-VERTEX-COLORABILITY PROBLEM





                                 \begin{figure}\begin{center}\mbox{\epsfxsize=3in\epsfbox{colorgraph22.eps}}\end{center}\end{figure}

Definition of 3-vertex-colorability. Let G be a graph with vertices V and edges E. The graph G is 3-vertex-colorable if there is a surjective (onto) function $f:V\rightarrow\{a,b,c\}$ such that if two vertices $v,w\in V$ are adjacent (connected by an edge) then $f(v)\ne f(w)$. The n-colorability is defined similarly.

In other words: color the vertices of the graph such that adjacent vertices are colored distinctly.

3-vertex-colorability is NP-complete.
 
 



Procedure:

1.
Combine all vertex building blocks with all edge molecules in a single tube and allow the complementary ends to hybridize and be ligated.
2.
Remove partially formed 3D DNA structures with open ends that have not been matched. This could be done by using an exonuclease enzyme.
3.
Remove by gel electrophoresis the graphs that are larger than the original graph formed in the above steps.

 

 

          3.a) if there is no graph in the tube, then the graph is neither 2- nor 3-colorable.

          3.b) if a graph remains in the tube then the graph is 3-colorable.
 
 


 
                                    \begin{figure}\begin{center}\mbox{\epsfxsize=3in\epsfbox{colorgraph22.eps}}\end{center}\end{figure}
 

                                  \begin{figure}\begin{center}\mbox{\epsfxsize=3.2in\epsfbox{knot2.eps}}\e......quences that correspondto the three colors.\end{figure}
 
 



CURRENT EXPERIMENTS




In solving Road Coloring Problem with DNA we have an operation ``match''.

Q: Given two mixes of DNA molecules, can we determine whether sequences of strings from one tube are present in the other.

Our strings are short DNA segments of 20bp.

We do know what are the strings (order of the nucleotides that make up the strings) but we have no knowledge of the order in which these strings appear in the DNA molecules.
 



 
 

                          \begin{figure}\begin{center}\mbox{\epsfxsize=4in\epsfbox{match.eps}}\end{center}\end{figure}
 
 



GRAPHS MADE OF ONE
SINGLE-STRANDED MOLECULE





Q: can we characterize the graphs that can be constructed by one single stranded DNA molecule?

The detection of such graphs would be much simplified.

Consider only three degree vertices graphs since:
 

\begin{figure}\begin{center}\mbox{\epsfxsize=6in\epsfbox{perturb.eps}}\end{center}\end{figure}
 
 
 



 

Define c(G)

Define c(G) to be minimum number of strands that can form the graph G.
 

                     \begin{figure}\begin{center}\mbox{\epsfxsize=4.7in\epsfbox{graphcycle.eps}}\end{center}\end{figure}
 
 

                     \begin{figure}\begin{center}\mbox{\epsfxsize=4.7in\epsfbox{knot2.eps}}\end{center}\end{figure}

Hence, c(G)=1
 



 

Main questions
 

Q1: given a graph G, determine c(G).

Q2: characterize graphs G such that c(G)=1.
 
 

 Different connections in a vertex of degree 3.
\begin{figure}\begin{center}\mbox{\epsfxsize=5in\epsfbox{vertexmove.eps}}\end{center}\end{figure}

We say that a graph is weakly connected if there is an edge e such that if we remove e from G then G becomes disconnected.
 
 

                                      \begin{figure}\begin{center}\mbox{\epsfxsize=3in\epsfbox{weak.eps}}\end{center}\end{figure}
 



 

Plannar graphs

Using the following change of connections within 3-armed branched molecules
 

\begin{figure}\begin{center}\mbox{\epsfxsize=6in\epsfbox{move.eps}}\end{center}\end{figure}

we can prove:

Proposition. If G is a planar graph that is not weakly connected, then $c(G)\le 2$.

Q: Is this true for graphs with higher genus?
 
 



ACTION OF RECOMBINASES AND TANGLES



Recombinases require DNA to be in certain configuration in oder to act. This is modeled by tangles (De Witt Sumners):
 

\begin{figure}\begin{center}\mbox{\epsfxsize=6in\epsfbox{tangle.eps}}\end{center}\end{figure}

Since a substrate and the product are known, tangle equations describe the action of the enzyme.
 
 



 

Future study:

Knowing the action of the enzyme over the DNA, what are the possible DNA structures (topoisomers) that can be formed?

How can they be used in a conjunction with a known topoisomerases in obtaining a desired DNA structure?
 
 



PERMUATIONS AND BRAIDS




Well known math fact: the group of all possible permutations of k elements can be generated with the set of transpositions (permutations of two elements).

A k-string braid is presented with:
 

\begin{figure}\begin{center}\mbox{\epsfxsize=5in\epsfbox{braid.eps}}\end{center}\par\end{figure}
 
 



 

DNA to permutations

Composition of braids $\equiv$k element permutations

Braids $\equiv$k (ds)DNA molecule with recombinase sites

Then

k (ds)DNA molecule with recombinase sites $\equiv$k element permutations
 
 

Future study:

Determine the laboratory conditions to represent k-element permutations by DNA braids.

What additional structures need to be imposed (H-form, or other triple helix) to the DNA strings in order to keep the braid in tact.

What is the largest k?
 
 




CONCLUSION





Long term benefits:

-systematically develop theories of DNA computing that use 3D structures.

-better understanding of when, under what condition, how and what three dimensional DNA structures can be formed

-through understanding of the natural processes of topoisomerases and recombinases, better understanding of natural processes and biochemical processes in vivo, in particular, relationship between 3D DNA structures and gene activation in vivo.
 

Natasha Jonoska