Solving a Hamiltonian Path Problem with a bacterial computer

Solving a Hamiltonian Path Problem with a bacterial computer

Jordan Baumgardner1, Karen Acker2, Oyinade Adefuye2,3,
Samuel Thomas Crowley1, Will DeLoache2, James O Dickson4, Lane Heard1,
Andrew T Martens2, Nickolaus Morton1, Michelle Ritter5, Amber Shoecraft4,6,
Jessica Treece1, Matthew Unzicker1, Amanda Valencia1, Mike Waters2, A
Malcolm Campbell2, Laurie J Heyer4, Jeffrey L Poet5 and Todd T Eckdahl*1

Address: 1Department of Biology, Missouri Western State University, St Joseph, MO 64507, USA, 2Department of Biology, Davidson College,
Davidson, NC 28036, USA, 3Department of Biology, North Carolina Central University, Durham, NC 27707, USA, 4Department of Mathematics,
Davidson College, Davidson, NC 28036, USA, 5Department of Computer Science, Math and Physics, Missouri Western State University, St Joseph,
MO 64507, USA and 6Natural Science and Math Department, Johnson C. Smith University, Charlotte, NC 28216, USA

Email: Jordan Baumgardner - jbaumgardner@missouriwestern.edu; Karen Acker - karen.acker@gmail.com;
Oyinade Adefuye - oyinadeadefuye@yahoo.com; Samuel Thomas Crowley - stc8033@missouriwestern.edu;
Will DeLoache - wideloache@davidson.edu; James O Dickson - jidickson@davidson.edu; Lane Heard - axenmoon@hotmail.com;
Andrew T Martens - a.t.martens@gmail.com; Nickolaus Morton - nmorton@missouriwestern.edu;
Michelle Ritter - mritter2@missouriwestern.edu; Amber Shoecraft - ashoecraft@jcsu.edu; Jessica Treece - jtreece@kcumb.edu;
Matthew Unzicker - mru8487@missouriwestern.edu; Amanda Valencia - avalencia@missouriwestern.edu;
Mike Waters - miwaters@davidson.edu; A Malcolm Campbell - macampbell@davidson.edu; Laurie J Heyer - laheyer@davidson.edu;
Jeffrey L Poet - poet@missouriwestern.edu; Todd T Eckdahl* - eckdahl@missouriwestern.edu

* Corresponding author

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.

+++++

OPEN ACCESS/PDF gratuito do artigo aqui.