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."
