Solving a Hamiltonian Path Problem with a bacterial computer.

Area of Science:

• Synthetic Biology
• Computational Biology
• Bioengineering

Background:

• The Hamiltonian Path Problem, an NP-complete problem, involves finding a route in a directed graph that visits each node exactly once.
• Traditional computers face significant challenges with NP-complete problems due to their increasing computational complexity.
• Emerging fields like DNA computing and bacterial computing offer novel approaches to tackle these complex problems.

Purpose of the Study:

• To design and construct a bacterial computer capable of solving the Hamiltonian Path Problem.
• To demonstrate the feasibility of using engineered bacteria as a computational tool for NP-complete problems.
• To validate synthetic biology principles in creating functional biological systems for computation.

Main Methods:

• Engineered *Escherichia coli* with a genetic circuit utilizing a Hin/hixC recombination system.
• Represented graph nodes as linked halves of genes encoding red or green fluorescent proteins.
• Encoded a three-node directed graph as DNA segments for autonomous shuffling within bacteria.

Main Results:

• Bacterial populations exhibited phenotypes reflecting random ordering of graph edges.
• Bacterial clones successfully identifying a Hamiltonian path displayed a yellow fluorescent phenotype (red and green).
• DNA sequencing confirmed that yellow colonies corresponded to genotypes representing valid Hamiltonian path solutions.

Conclusions:

• Successfully designed, constructed, and tested a bacterial computer for the Hamiltonian Path Problem in a three-node graph.
• This proof-of-concept highlights bacterial computing as a viable strategy for addressing NP-complete problems.
• The study validates synthetic biology as a powerful approach for biological engineering and the creation of novel computational systems.