Team:MoWestern Davidson/project

Understanding SAT: the Lock and Door Analogy

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

Descriptions in parentheses are reference to the "lock and door" analogy.

Literal=(a key hole)= half of a variable. example (a)

Variable=(a color)= corresponding literals. example (a,a')

Clause=(a door)=a group of literals joined by OR. example (a OR b)

SAT Problem=(a hallway of doors)= clauses joined together by AND. example (a or b) AND (a' OR b')

A SAT problem is made by joining a certain number of clauses (doors) together with the logical operator "AND" (AND implies that you have to satisfy (open) all of the clauses (doors) to find a solution to the problem). Each clause contains literals (key holes) joined together by the logical operator "OR" (here OR implies that you need at least one literal (keyhole) for the clause (door) to be satisfied (opened)) and these literals (key holes) are selected from the number of variables (the different key colors) being used. So translating the janitor's problem from above into mathematical terms would yield:

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

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

In mathematical terms, this problem is a 3-variable (3 colors), 2-SAT (2 key holes), 4 clause (4 doors) SAT problem. Keep in mind that you can change any of these parameters by adding more variables (colors), more clauses (more doors), and you can make the problem 3-SAT, 4-SAT, etc (3, 4, etc key holes).

A related problem, MAX SAT uses the same terminology, but instead of wanting to be able to satisfy (open) all of the clauses (doors) this problem asks how many clauses (doors) can be satisfied. So in

The Math 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.

History of the SAT problem

Significance of SAT