Overview

To solve the SAT problem, we constructed reporter genes to express a phenotype if E. coli solves the SAT problem. To design these reporter genes, we constructed a continuum to model the different levels of bacterial automation in solving the SAT problem. This allowed us to select the level of automation we desired and design reporter genes based off of that level. The basic concept behind the reporter genes involves inserting a 5 base pair insertion that throws off the reading frame in translation, causing a nonsense protein. We then provide the cells with different suppressor tRNAs that may or may not suppress this insertion. If the insertion is suppressed, the reading frame will be restored and the protein will be expressed. These suppressors represent the inputs of the SAT problem, and the 5 base pair insertions represent the clauses of the problem. In most designs the frame shift leader (FSL), this 5 base pair insertion, occurs at the beginning of the protein structure, immediately following start codon.

Automation Scale and FSL Design

Scale of Bacterial Automation

Low Bacterial Automation

Full Bacterial Automation

1. Single Literal: In this approach, the reporter gene has a FSL of one literal, a for example. The bacteria are given a set of tRNA variables as inputs to evaluate that literal, and if the bacteria receive that literal, then it will express a gene. This process is more of a screening to see if the design works. To evaluate the logical clauses and MAX SAT, we must look plates to see if the gene was expressed.

2. Single Clause: In this approach, the reporter gene has a FSL of one logical clause, (a OR b) for example. Bacteria are given a set of tRNA variables as inputs to evaluate that clause. If the clause is satisfied and suppression occurs, then the gene will be expressed. We must then determine how many colonies expressed the gene, thus satisfying the clauses.

3. Automated SAT with One Reporter Type: In this approach, 4 different FSLs that test for at least 1, 2, 3, and 4 clauses satisfied are inserted in the beginning of different copies of the same reporter gene used in separate bacterial clones. Each FSL design has the same SAT problem, (a OR b) AND (b OR c’) for example, encoded in it. Bacteria are given a set of tRNA variables as inputs and evaluate the logical clauses and MAX SAT by reporting the gene expression.

4. Fully Automated Population: In this approach, 4 different FSLs that test for at least 1, 2, 3, and 4 clauses satisfied are inserted in the beginning of different reporter genes used in separate bacterial clones on the same plate. Each FSL design has the same SAT problem, (a OR b) AND (b OR c’) for example, encoded in it. The first clone tests for 1 clause satisfied and if satisfied, the clone will produce GFP. The second clone tests for 2 clauses satisfied and will produce RFP if satisfied. The third clone tests for 3 clauses satisfied and will produce Chloramphenicol (CAT) resistance. The last clone tests for 4 clauses satisfied and will produce Tetracycline (TetR)resistance.

5. Fully Automated Single Clone: In this approach, 4 different FSLs that test for at least 1, 2, 3, and 4 clauses satisfied are inserted in the beginning of different reporter genes used in a single clone. The first reporter gene tests for at least 1 clause satisfied, and if satisfied, the gene GFP will be expressed. The second reporter gene tests for at least 2 clauses satisfied and will express RFP if satisfied. The third reporter gene tests for at least 3 clauses satisfied and will produce Chloramphenicol resistance. Tetracycline resistance is the last reporter gene that tests for all 4 clauses satisfied. Each FSL design has the same SAT problem, (a OR b) AND (b OR c’) for example, encoded in it. Bacteria are given a set of tRNA variables as inputs and evaluate the logical clauses and MAX SAT.

Designing the Locks and Keys

We employed two separate approaches to design and construct our suppressor tRNAs (Keys ) and the frameshifted reporter proteins (Locks ). The genomic sequence of the novel five nucleotide anticodon tRNAs were obtained from papers by Thomas J. Magliery, J. Christopher Anderson and Peter G. Schultz {Magliery et. al. & Anderson et. al.}. We used synthetic oligo nucleotides to assemble the twelve tRNAs with flanking biobrick prefix and suffix sticky ends. Alternately, the mutated reporter genes were designed and constructed by PCR directed mutagenesis.