Solving a Hamiltonian Path Problem with a bacterial computer Export

@article{citeulike:5271694, abstract = {BACKGROUND:The Hamiltonian Path Problem asks whether there is a route in a directed graph from a beginning node to an ending node, visiting each node exactly once. The Hamiltonian Path Problem is NP complete, achieving surprising computational complexity with modest increases in size. This challenge has inspired researchers to broaden the definition of a computer. DNA computers have been developed that solve NP complete problems. Bacterial computers can be programmed by constructing genetic circuits to execute an algorithm that is responsive to the environment and whose result can be observed. Each bacterium can examine a solution to a mathematical problem and billions of them can explore billions of possible solutions. Bacterial computers can be automated, made responsive to selection, and reproduce themselves so that more processing capacity is applied to problems over time.RESULTS:We programmed bacteria with a genetic circuit that enables them to evaluate all possible paths in a directed graph in order to find a Hamiltonian path. We encoded a three node directed graph as DNA segments that were autonomously shuffled randomly inside bacteria by a Hin/hixC recombination system we previously adapted from Salmonella typhimurium for use in Escherichia coli. We represented nodes in the graph as linked halves of two different genes encoding red or green fluorescent proteins. Bacterial populations displayed phenotypes that reflected random ordering of edges in the graph. Individual bacterial clones that found a Hamiltonian path reported their success by fluorescing both red and green, resulting in yellow colonies. We used DNA sequencing to verify that the yellow phenotype resulted from genotypes that represented Hamiltonian path solutions, demonstrating that our bacterial computer functioned as expected.CONCLUSION:We successfully designed, constructed, and tested a bacterial computer capable of finding a Hamiltonian path in a three node directed graph. This proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems. The results of our experiments also validate synthetic biology as a valuable approach to biological engineering. We designed and constructed basic parts, devices, and systems using synthetic biology principles of standardization and abstraction.}, author = {Baumgardner, Jordan and Acker, Karen and Adefuye, Oyinade and Crowley, Samuel and DeLoache, Will and Dickson, James and Heard, Lane and Martens, Andrew and Morton, Nickolaus and Ritter, Michelle and Shoecraft, Amber and Treece, Jessica and Unzicker, Matthew and Valencia, Amanda and Waters, Mike and Campbell, A. Malcolm and Heyer, Laurie and Poet, Jeffrey and Eckdahl, Todd}, citeulike-article-id = {5271694}, citeulike-linkout-0 = {http://dx.doi.org/10.1186/1754-1611-3-11}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/19630940}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=19630940}, doi = {10.1186/1754-1611-3-11}, issn = {1754-1611}, journal = {Journal of Biological Engineering}, keywords = {algorithm, article, biology, graphtheory}, number = {1}, pages = {11+}, posted-at = {2009-07-29 07:33:39}, priority = {2}, title = {Solving a Hamiltonian Path Problem with a bacterial computer}, url = {http://dx.doi.org/10.1186/1754-1611-3-11}, volume = {3}, year = {2009} }

TY - JOUR ID - citeulike:5271694 L3 - citeulike-article-id:5271694 N2 - BACKGROUND:The Hamiltonian Path Problem asks whether there is a route in a directed graph from a beginning node to an ending node, visiting each node exactly once. The Hamiltonian Path Problem is NP complete, achieving surprising computational complexity with modest increases in size. This challenge has inspired researchers to broaden the definition of a computer. DNA computers have been developed that solve NP complete problems. Bacterial computers can be programmed by constructing genetic circuits to execute an algorithm that is responsive to the environment and whose result can be observed. Each bacterium can examine a solution to a mathematical problem and billions of them can explore billions of possible solutions. Bacterial computers can be automated, made responsive to selection, and reproduce themselves so that more processing capacity is applied to problems over time.RESULTS:We programmed bacteria with a genetic circuit that enables them to evaluate all possible paths in a directed graph in order to find a Hamiltonian path. We encoded a three node directed graph as DNA segments that were autonomously shuffled randomly inside bacteria by a Hin/hixC recombination system we previously adapted from Salmonella typhimurium for use in Escherichia coli. We represented nodes in the graph as linked halves of two different genes encoding red or green fluorescent proteins. Bacterial populations displayed phenotypes that reflected random ordering of edges in the graph. Individual bacterial clones that found a Hamiltonian path reported their success by fluorescing both red and green, resulting in yellow colonies. We used DNA sequencing to verify that the yellow phenotype resulted from genotypes that represented Hamiltonian path solutions, demonstrating that our bacterial computer functioned as expected.CONCLUSION:We successfully designed, constructed, and tested a bacterial computer capable of finding a Hamiltonian path in a three node directed graph. This proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems. The results of our experiments also validate synthetic biology as a valuable approach to biological engineering. We designed and constructed basic parts, devices, and systems using synthetic biology principles of standardization and abstraction. IS - 1 JF - Journal of Biological Engineering SN - 1754-1611 TI - Solving a Hamiltonian Path Problem with a bacterial computer VL - 3 SP - 11 KW - algorithm KW - article KW - biology KW - graphtheory AU - Baumgardner, Jordan AU - Acker, Karen AU - Adefuye, Oyinade AU - Crowley, Samuel AU - DeLoache, Will AU - Dickson, James AU - Heard, Lane AU - Martens, Andrew AU - Morton, Nickolaus AU - Ritter, Michelle AU - Shoecraft, Amber AU - Treece, Jessica AU - Unzicker, Matthew AU - Valencia, Amanda AU - Waters, Mike AU - Campbell, Malcolm AU - Heyer, Laurie AU - Poet, Jeffrey AU - Eckdahl, Todd PY - 2009/// UR - http://dx.doi.org/10.1186/1754-1611-3-11 ER -