Overview

The Satisfiability (Sat) Problem: A member of the NP Complete family (the most challenging of the non-deterministic polynomial time problems, can be compared to an analogy of locks and keys. Imagine a hallway of 4 doors, each with one lock.

each lock on each door can be opened by two different keys, (represented by the letters on each door- so the first lock can be opened by either the "G" (first green key) or the "B"(first blue key).) As long as you have at least one of the keys you can open the door. A janitor then, with three sets of keys blue ,(B,b), green ,(G,g), red ,(R,r)wants to find the combination of one blue key, one green key, and one red key that will open all four of the doors. The graphic below illustrates 3 of the janitor's possible 8 key combinations, and out of this set, only the first key ring can open all four doors. This key ring is said to "satisfy" the door problem.

The Real Math

Each sat problem is made by joining (logical operator "AND") a number of clauses (doors), which each contain a number of literals(key holes)joined to each other by the logical operator "OR" (here they are joined by being in the same lock.) so the same problem the janitor faced would be translated like this

(a OR b) AND (a OR b') AND (a OR c') AND (a'or c)

where (a,a') replaces the blue set of keys, (b,b') replaces green set of keys and (c,c') replaces the red set of keys.

In E.coli

Our team translated this np-complete problem into a modified biological process. In cells, the process of transcription codes DNA into RNA, and then the RNA is translated into a protein that is expressed once completed. Just as an English sentence requires a specific grouping of letters to form words, DNA must be read in 3 nucleotide groupings called codons to continue the process successfully. Transfer RNAs (tRNAs) are RNA molecules with 3 nucleotide anticodon loops that match specifically to codon sequences and supply the amino acids according to those sequences. These amino acids are required to construct the protein. If nucleotides are inserted or deleted, the reading frame is shifted, causing a frameshift mutation. That frameshift mutation causes the tRNA to supply the wrong amino acid in the peptide chain that then gives an unanticipated protein, or no protein.

With this biological background, the connection can be made between the “door and key” analogy and the biological interpretation. Our “doors” are engineered reporter gene DNA sequences including the 5 nucleotide frameshift mutation “keyhole”, resulting in our frameshift leaders (FSL). The “keys” that may or may not open the door are engineered 5 nucleotide anticodon suppressor tRNAs. Opening the door, thus solving the MAX SAT problem, would allow the cell to convey this outcome in the expression of the reporter gene (fluorescence/antibiotic resistance). The idea of using suppressor tRNAs to bypass designed mutation to solve a SAT problem is an extension using suppressor logic from papers by Thomas J. Magliery, J. Christopher Anderson and Peter G. Schultz {Magliery et. al. & Anderson et. al.}. This team worked with 2,3,4,5, and 6 nucleotide frameshift mutations. Their research found that 4 and 5 base codon suppression was most efficient in their mission of expanding the genetic code. The difference in the original amino acid and the modified 5mer amino acid is the addition of the 2 nucleotides.