title: Solving a four-destination traveling salesman problem using Escherichia coli cells as biocomputers.
abstract: The Traveling Salesman Problem involves finding the shortest possible route visiting all destinations on a map only once before returning to the point of origin. The present study demonstrates a strategy for solving Traveling Salesman Problems using modified E. coli cells as processors for massively parallel computing. Sequential, combinatorial DNA assembly was used to generate routes, in the form of plasmids made up of marker genes, each representing a path between destinations, and short connecting linkers, each representing a given destination. Upon growth of the population of modified E. coli, phenotypic selection was used to eliminate invalid routes, and statistical analysis was performed to successfully identify the optimal solution. The strategy was successfully employed to solve a four-destination test problem.
authors.affiliation: University of Alberta , Edmonton, Alberta T6G 2R3, Canada.
authors.forename: Michael
authors.initials: M
authors.lastname: Esau
authors.forename: Mark
authors.initials: M
authors.lastname: Rozema
authors.forename: Tuo Huang
authors.initials: TH
authors.lastname: Zhang
authors.forename: Dawson
authors.initials: D
authors.lastname: Zeng
authors.forename: Stephanie
authors.initials: S
authors.lastname: Chiu
authors.forename: Rachel
authors.initials: R
authors.lastname: Kwan
authors.forename: Cadence
authors.initials: C
authors.lastname: Moorhouse
authors.forename: Cameron
authors.initials: C
authors.lastname: Murray
authors.forename: Nien-Tsu
authors.initials: NT
authors.lastname: Tseng
authors.forename: Doug
authors.initials: D
authors.lastname: Ridgway
authors.forename: Dominic
authors.initials: D
authors.lastname: Sauvageau
authors.forename: Michael
authors.initials: M
authors.lastname: Ellison
mesh_terms: D019295:Computational Biology / Q000379:methods*; D039301:Computers, Molecular; D004926:Escherichia coli / Q000235:genetics* / Q000502:physiology*; D008954:Models, Biological; D010957:Plasmids / Q000235:genetics