Can we solve a 3-SAT problem with supressor logic?

From GcatWiki
Jump to: navigation, search

What is the 3-SAT problem?

Advantages/Disadvantages to using the 3 SAT problem


1) Seems to have an equal balance of mathematics and biology.

2) Eventually, there is promise to make the problem difficult enough whereas a computer would have a hard time solving it.

3) Introducing a new concept (supressor supressor logic)


1) Using the same concept/idea that has been used by previous Missouri Western/Davidson iGEM teams. (XOR gate)

2) Finding enough for everyone to work on for the entire summer.

3) Finding a promoter that is turned on without the use of a small particle.

How did Sakamoto et al. use a DNA computer to solve a 3-SAT problem?

Sakamoto et al.


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?

Will's Version of the PPT for SSL 3SAT Will's Version of the PPT for SSL 3SAT

Powerpoint on 3SAT SSL (Bryce and Clif) I don't know how to post the powerpoint on here. Bryce and Clif's Version

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:

  1. AUG CCCG CUG ... rest of Gene
  2. AUG CCCG CUGC CUG ... rest of Gene
  3. AUG CCCG gg CUGC AGG ... rest of Gene
  4. 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?


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)

LC using 4-base frameshift mutations: cag CCCG aa GGGC tt GTTG cag (may also have any multiple of 3 bases between the mutations)

LC using 5-base frameshift mutations: cag CCCGC a GGGCG t GTTGC cag (may also have any multiple of 3 bases between the mutations)

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

Logical expression2.GIF


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.

Suppressor inputs.GIF

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.

LE circuit.GIF

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 12 different frameshift suppressor tRNAs to encode the Sakamoto 3-SAT problem

Discovery of frameshift tRNAs. How many are known?

Magliery, Anderson, Schultz

Library approach used to discover efficient suppressors of four-base codons AGGA, UAGA, CCCU, and CUAG using mutated versions of serine tRNA.

Anderson, Maglieri, Schultz

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:

Rodriguez, Lester, Dougherty

3 Suppressor tRNAs in a single protein, in vitro

Three suppressor tRNAs in vivo (E. coli)

Incorporating unnatural amino acids using frameshift suppression. They used three in one eukaryotic cell.

Table2 Anderson2002.GIF

Dunham et al.

Hohsaka et al.

Processing of tRNA precursors in E. coli

Mörl and Marchfelder describe processing

The final cut.GIF

How many different frameshift suppressor tRNAs can be in one cell without causing toxicity?

Can we have twelve of them? If not, what is the maximum? Is there an impact of codon usage on this?

Can we have both 4- and 5-base suppressor tRNAs in one cell?

Are there particular combinations of suppressors that are more tolerated than others?

How many frameshift mutations can be suppressed in a single gene?

How close together can the frameshift mutations of a given LC be?

Can we mix 4- and 5-base frameshift mutations in a given LC?