Difference between revisions of "Can we solve a 3-SAT problem with supressor logic?"
(→How did Sakamoto et al. use a DNA computer to solve a 3-SAT problem?) |
(→Things we need to learn about) |
||
| Line 108: | Line 108: | ||
== Things we need to learn about == | == Things we need to learn about == | ||
| + | |||
| + | '''Note: We would need xx different frameshift suppressor tRNAs to encode the Sakamoto 3-SAT problem''' | ||
'''Discovery of frameshift tRNAs. How many are known?''' <br> | '''Discovery of frameshift tRNAs. How many are known?''' <br> | ||
Revision as of 20:19, 13 April 2009
Contents
What is the 3-SAT problem?
How did Sakamoto et al. use a DNA computer to solve a 3-SAT problem?
Sakamoto used hairpin formations in single stranded DNA (ssDNA) as a molecular computer. Hairpin structures are formed when complimentary bases on the same strand attach to each other forming a loop. As shown in Picture B above, C and -C are compliments of each other, and bind together. Picture A is what a normal ssDNA should look like. Sakamoto used this self assembly of secondary structures on a satisfiability (SAT) problem. The problem had six inputs and ten clauses. An example of a clause would be (a or b or -c), and could include any combinations of inputs from a to f including -a to -f. If the problem is satisfied, the ssDNA stays in it's normal form. If the problem is not satisfied, the ssDNA forms a hairpin. Later in the paper it explains that the hairpin forming molecules can be removed from the others with certain techniques.
The 10 clause 3-SAT problem solved in the paper is:
(a or b or –c)
(a or c or d)
(a or –c or –d)
(-a or –c or d)
(a or –c or e)
(a or d or –f)
(-a or c or d)
(a or c or –d)
(-a or –c or –d)
(-a or c or –d)
note: this problem uses inputs of a, b, c, d, e, -a, -c, -d, -f (f, -b, -e are not used)
What is suppressor logic?
Suppressor Logic uses suppressor tRNAs as inputs to avoid frameshift mutations in the production of an output amino acid sequence
A frameshift is a genetic mutation caused by the addition or deletion of nucelotides to a given sequence which codes for a protein. Since codons are read in a series of three, the addition or deletion of nucleotides will disrupt the reading frame. This disruption will most likely cause the production of a nonfunctional protein.
A frameshift occurs and, in this case, a guanine is added to the sequence. If nothing is done, enzyme A will not be made, meaning the clause will not be satisfied.
The suppressor tRNA allows the 4 letter sequence to be read as a single codon, therefore, keeping the protein on track.
If more than one frameshift mutation is introduced into a coding sequence, then logical operators can be encoded. Suppressor a binds to CCCG, supressor b binds to CUGC, and suppressor c binds to ACCG below:
- AUG CCCG CUG ... rest of Gene
- AUG CCCG CUGC CUG ... rest of Gene
- AUG CCCG gg CUGC AGG ... rest of Gene
- AUG CCCG gg CUGC gg ACCG AGG ... rest of Gene
| Construct | Gene | Logical operation |
|---|---|---|
| 1 | Phenotype | a |
| 2 | Phenotype | a AND b |
| 3 | Phenotype | a OR b |
| 4 | Phenotype | a OR b OR c |
| 1 | Repressor | NOT a |
| 2 | Repressor | a NAND b |
| 3 | Repressor | a NOR b |
| 4 | Repressor | NOT (a OR b OR c) |
Logical clauses can be connected by AND operators if the proteins produced are part of a biochemical pathway. In this case, a AND b AND c:
How could suppressor logic be used to solve the Sakamoto 3-SAT problem?
Definitions
Inputs = framshift suppressor tRNAs
Input value = supp a is 1, supp g is 0; supp b is 1, supp h is 0, etc. up to tth 6th pair of f and l
Logical clause (LC) = three inputs connected by OR, eg. (a OR b OR e)
Translation into DNA sequence cag CCCG aa GGGC tt GTTG cag
This makes an XOR logic gate as only one suppressor can be used at one time to maintain the reading frame.
Logical expression (LE) = string of LCs connected by AND
The design below encodes LC1 AND LC2 AND LC3
Subroutine
1. Individual bacteral cells use Hin/hix system to randomly choose of of the 64 possible combinations of 6 inputs. Suppressors a and g represent 1 and 0 for the first input; suppressors b and h are 1 and 0 for the second input; etc. up to the sixth input with suppressors f and l (lower case L). The triangles are hix sites for Hin recombination. Whichever of the two suppressor tRNAs in an input pair is facing forward determines whether the value of that input is 1 or 0.
2. Each bacterial cell carries out the following subroutine on each LC: IF LC=TRUE THEN "check the next LC" ELSEIF LC=FALSE "go get a new set of inputs with step 1" In order to do this, each of the activators below must turn on a repressor that turns off Hin production. Then if one of the activators is not made, Hin will be made, and new inputs will be established.
3. If/when a bacterial cell finds a set of inputs that satisfies the entire LE (ie. a solution to the 3-SAT problem), it will glow green.
Things we need to learn about
Note: We would need xx different frameshift suppressor tRNAs to encode the Sakamoto 3-SAT problem
Discovery of frameshift tRNAs. How many are known?
Library approach used to discover efficient suppressors of four-base codons AGGA, UAGA, CCCU, and CUAG using mutated versions of serine tRNA.
Signals for translational bypassing (slipping and hopping): mRNA secondary structure, "hungry" (underused) codons, upstream Shine-Dalgarno-like (RBS) sequences
Library approach extended in order to discover frameshift suppressor tRNAs with anticodons of size two to six bases. Two-base and six-base suppressors were not found, but the following five-base suppressors were found:
Processing of tRNA precursors in E. coli
Mörl and Marchfelder describe processing
Is there any evidence concerning the use of several (six?) frameshift tRNAs in one cell?
