WELCOME TO iGEM 2014!

Your team has been approved and you are ready to start the iGEM season!
On this page you can document your project, introduce your team members, document your progress
and share your iGEM experience with the rest of the world!

Click here to edit this page!

Project Description

Content

In graph theory, the Single Pair Shortest Path Problem (SPP) is one of the basic problems with many applications. Many computational methodssuch as Dijkstra algorithm, A-star search algorithm and Floyd-Warshal algorithm etc., can solve it in a tolerable computational complexity. However, as the technology of the traditional silicon computers is gradually meeting its physical limits, new methods of the high-volume computing has been looked for for years. As developing rapidly, synthetic biology makes bacterial computing possible and great potential. Programming Escherichia coli, the simplest model organism to implement these kinds of basic problems is very necessary. It will bring up with a brand new bio-computing method with better computational complexity.

Here, we will design a series of genetic circuits in Escherichia coli to solve the SPP in a directed graph. The nodes and arrows are programed as well-assigned promoters and transcription factors (TFs) respectively. For each arrow, the promoter of its source node initiates the expression of the TF which induces specifically the promoter of the target node. The paths in the graph are described by the transcriptional regulatory cascades. The promoter of destination node in SPP is followed by a green fluorescent protein (GFP) as a reporter. The temporal ordering of the fluorescent protein expression in E.coli reflects the distance difference among varied paths. According theoretical analysis, we can find the the shortest path consisted by all those arrows with linear computational complexity.

References

1. Peter J. Bentley: Methods for improving simulations of biological systems: systemic computation and fractal proteins. J. R. Soc. Interface(2009)6, S451–S466.

2. Alla Borisyuk, Avner Friedman, Bard Ermentrout, David Terman: Tutorials in Mathematical Biosciences I Edited by: J.-M. Morel, F. Takens, B. Teissier. Springer Press; 2005

3. Adleman LM: Molecular computation of solutions to combinatorial problems. Science 1994, 266:1021-1024.

4. Lipton RJ: DNA solution of hard computational problems. Science 1995,268:542-545.

5. Benenson Y, Paz-Elizur T, Adar R, Keinan E, Livneh Z, Shapiro E: Programmable and autonomous computing machine made of biomolecules. Nature 2001, 414:430-434.

6. Wang X, Bao Z, Hu J, Wang S, Zahn A: Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction. Biosystems 2008, 91(1):117-225.

7. Gerd HG Moe-Behrens: The biological microprocessor, or how to build a computer with biological parts. CSBJ 2013, Volume No: 7, Issue: 8, April, e201304003.

8. Wang, B. et al. Engineering modular and orthogonal genetic logic gates for robust digital-like synthetic biology. Nat. Commun.2:508 doi: 10.1038/ncomms1516 (2011).

9. Gardner TS, Cantor CR, Collins JJ: Construction of a genetic toggle switch in Escherichia coli. Nature 2000,403:339-342.

10. Yaakov Benenson, Tamar Paz-Elizur et al. Programmable and autonomous computing machine made of biomolecules. Nature 2001, November 22; 414(6862): doi:10.1038/35106533.

11. Jordan Baumgardner, Karen Acker et al. Solving a Hamiltonian Path Problem with a bacterial computer. Journal of Biological Engineering 2009, 3:11 doi:10.1186/1754-1611-3-11.

12. Karmella A Haynes et al. Engineering bacteria to solve the Burnt Pancake Problem. Journal of Biological Engineering 2008, 2:8 doi:10.1186/1754-1611-2-8.

13. Advait A Apte1, John W Cain, Danail G Bonchev and Stephen S Fong: Cellular automata simulation of topological effects on the dynamics of feed-forward motifs. Journal of Biological Engineering 2008, 2:2 doi:10.1186/1754-1611-2-2.

14. Rosen, Kenneth H: Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill. ISBN 978-0-07-338309-5.

15. Hooshangi S, Thiberge S, Weiss R: Ultrasensitivity and noise propagation in a synthetic transcriptional cascade. Proc. Natl. Acad. Sci. USA, 2005, 102(10): 3581-3586.

You can use these subtopics to further explain your project

1. Overall project summary
2. Project Details
3. Materials and Methods
4. The Experiments
5. Results
6. Data analysis
7. Conclusions

It's important for teams to describe all the creativity that goes into an iGEM project, along with all the great ideas your team will come up with over the course of your work.

It's also important to clearly describe your achievements so that judges will know what you tried to do and where you succeeded. Please write your project page such that what you achieved is easy to distinguish from what you attempted.