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.

Here is the detailed explain for our project.

Overall project summary

Recent years, there were some researches aiming to solve specific mathematical problems using synthetic biology, one of which even shed lights on the possibility of solving Hamilton Problem in engineered bacteria. Inspired by them, we are trying to design and construct gene circuits to deal with other problem in graph theory. What we want to prove is that the organism have potential for computation as long as they are designed appropriately.

Project Details

SPP-for-short problem asks the shortest pathway between two given points in a directed graph. We came up with an idea to translate this shortest of space into quickest of time with the help of transcriptional cascades in Escherichia coli. That is to say that we build gene circuits to encode a directed graph where each nodes and edges within are represented by certain promoters and TFs respectively. Then a proof-of-concept experiment in vivo was carried to confirm the validation of this design.

Materials and Methods

We used several parts from iGEM registry and constructed five new parts and devices. The experiments involved are basic ones in gene engineering including gene amplification and expression; polymerase chain reaction; electrophoresis etc.

The Experiments

Results

We designed a series of genetic circuits in Escherichia coli forming a regulatory network in order to translate the form of mathematical problem from geometrical graph into biological structure. The nodes and arrows are marked by well-assigned promoters and transcription factors (TFs) respectively. The promoter of destination node in SPP is followed by a green fluorescent protein (GFP) as a reporter. In this way, the connections among nodes in a directed graph are simulated by transcriptional regulation network. The temporal ordering of the fluorescent protein expression in bacteria reflects distance differences among varied paths, in which an individual bacteria clone containing the shortest pathway encoded gene would show fluorescent earlier than the others. In the following one bit knock-out process, we verified the phenotype which showed fluorescent earlier resulted from the genotype that represented the shortest pathway solution, shedding lights on that our encoding system functioned as expected with linear computation complexity and this approach is theoretically proved feasible.

Data analysis

Conclusions

The bio-computing method we have come up with is a brand-new way to solve the SPP problem effectively. Based on the standardization principals and abstraction strategies of synthetic biology, the results also validated synthetic biology as a valuable approach to biological engineering. In the discussion concerning its augmentability, the potential value and superiority of solving NPC problems can be observed when combining metabolism pathway modification engineering.