# IGEM 2009 Project

Vocabulary:

- A
**variable**is simply a letter of the alphabet (e.g. A) that comes in two types called literals -- a and a'. Note: Alternative notations could be A and a, or (a) and (not a). - A
**clause**is made up of two or more literals with the logical operator OR between (e.g. (a OR b') is a clause.) - A
**SAT problem**in conjunctive normal form is comprised of two or more clauses with the logical operator AND between. The number of literals in each clause is the value of k in our use of k-SAT to describe a problem. - An
**input**is an assignment of one of the corresponding literals to each of the variables. For example, (a, b' c') is one of eight possible inputs in a 3-variable problem.

Examples:

(a OR b') AND (a' OR b') AND (a OR b) is a 2-variable, **2-SAT problem** with 3 clauses using 4 literals.

(a OR b OR c) AND (a' OR b OR d) AND (a OR b' OR d') is a 4-variable, **3-SAT problem** with 3 clauses using 7 literals.

- The question of interest for a SAT problem is whether or not there exists an input that makes the overall logical expression true.
- The question of interest for a MAX SAT problem is to determine the maximum number of clauses satisfied when considered over the set of all possible inputs.

Biology Based:

- Which reporters are we going to use?
- What naming system are we going to use for the suppressor tRNAs?
- How do you build the tRNA construct?
- How are we going to build the 5-mer BioBricks?

Using Stop Codons to Truncate Translation

Davidson ATG+5mer BioBrick Sequences

Frameshift Mutation Leader PCR primers

Align E. coli tRNA sequences

Compare 2 tRNA structures

**Team Progress Table**

Student Name | 5mer Codon | Anticodon Sequence | Codon Short Name | tRNA Status | 5mer+XFP Status | 5mer+Drug resistance Status |
---|---|---|---|---|---|---|

Olivia Ho-Shing | CCAUC | GUGAUCCAA-9 | Pro4 | Ligated to pBad (100% match) |
'Ligated to pLac-RBS, and that to pBad-tRNA (100% match) |
No 5mer+Tet resistance |

Olivia Ho-Shing | CCAUC | UUUGAUGGAG-10 | Pro5 | Ligated to pBad (100% match) |
'Ligated to pLac-RBS, and that to pBad-tRNA (100% match) |
No 5mer+Tet resistance |

Romina Clemente | CUAGU | UUACUAGAC | Leu4 | Ligated to pBad (100% match) |
'Ligated to pLac-RBS, and that to pBad-tRNA (100% match) |
100% match 5mer+Tet resistance |

Shamita Punjabi | CCACU | CUAGUGGAC | Pro3 | Ligated to pBad (100% match) |
'Ligated to pLac-RBS, and that to pBad-tRNA (100% match) |
100% match 5mer+Tet resistance |

Leland Taylor | CCCUC | CUGAGGGUC | Pro6 | Ligated to pBad (100% match) |
'Ligated to pLac-RBS (100% match) |
No 5mer+Tet resistance |

Alyndria Thompson | CGGUC | UUGACCGAC | Arg2 | Ligated to pBad (100% match) |
'Ligated to pLac-RBS, and that to pBad-tRNA (100% match) |
100% match 5mer+Tet resistance |

Clif Davis | 5mer codon | Anticodon Sequence | Leu3 | 100% match |
5mer+GFP Status | 2 5mer+CAT sequenced-99% Match with a Conservative Mutation |

Student Name | 5mer codon | Anticodon Sequence | Codon Short Name | 100% match |
5mer+GFP Status | 5mer+CAT Resistance Status |

Student Name | 5mer codon | Anticodon Sequence | Codon Short Name | 100% match |
5mer+GFP Status | 5mer+CAT Resistance Status |

Student Name | 5mer codon | Anticodon Sequence | Codon Short Name | 100% match |
5mer+GFP Status | 5mer+CAT Resistance Status |

Student Name | 5mer codon | Anticodon Sequence | Codon Short Name | 100% match |
5mer+GFP Status | 5mer+CAT Resistance Status |

Student Name | 5mer codon | Anticodon Sequence | Codon Short Name | 100% match |
5mer+GFP Status | 5mer+CAT Resistance Status |

Math Based: (Davidson) We have posted a Mathematica notebook on the Wiggio. Basically we are at a point where we can choose the number of variables, SAT number(2-SAT, 3-SAT, etc), and the number of clauses to use at a time and produce a table of inputs as the rows and clauses as the columns, with a 1 if the input satisfies the clause and a 0 if the input fails to satisfy the clause. In addition, we can produce a "Super Table," which lists all the SAT problems given the number of clauses in conjunctive normal form and displays how many of the clauses in a given problem each input satisfies. Feel free to view the posted Mathematica notebook; there are some instructions within the notebook itself. When you open it, there will be a window which asks about dynamic content; be sure to click "Enable Dynamic."