Team:Jefferson VA SciCOS/Project

Abstract

Solving a 4-Node Traveling Salesman Problem Using the hin/hixC Recombinant System Bacterial computing has become a feasible way to autonomously solve quantitative problems. We sought to utilize the computational capacity of E.coli K-12 to solve the Traveling Salesman Problem, a problem in theoretical computer science that asks for the shortest possible route that visits each node in a system at least once and returns to the original node. We utilized a series of initial configurations for the hin/hixC recombinant system that were previously developed by a 2006 iGEM team to solve the Hamiltonian Path Problem. In addition, we created a fourth node by splitting blue fluorescent protein (BFP) with a hixC site and reinserted this node into one of the composite hin/hixC paths. To simulate varied distance, we added a ribosome binding site of a different strength in between the initial recombinant system and the fourth node.

Abstract

Solving a 4-Node Traveling Salesman Problem Using the hin/hixC Recombinant System Bacterial computing has become a feasible way to autonomously solve quantitative problems. We sought to utilize the computational capacity of E.coli K-12 to solve the Traveling Salesman Problem, a problem in theoretical computer science that asks for the shortest possible route that visits each node in a system at least once and returns to the original node. We utilized a series of initial configurations for the hin/hixC recombinant system that were previously developed by a 2006 iGEM team to solve the Hamiltonian Path Problem. In addition, we created a fourth node by splitting blue fluorescent protein (BFP) with a hixC site and reinserted this node into one of the composite hin/hixC paths. To simulate varied distance, we added a ribosome binding site of a different strength in between the initial recombinant system and the fourth node.