Solving a Four-Destination Traveling Salesman Problem Using Escherichia coli Cells As Biocomputers
详细信息 查看全文
- 作者：Michael Esau ; Mark Rozema ; Tuo Huang Zhang ; Dawson Zeng ; Stephanie Chiu ; Rachel Kwan ; Cadence Moorhouse ; Cameron Murray ; Nien-Tsu Tseng ; Doug Ridgway ; Dominic Sauvageau ; Michael Ellison
- 刊名：ACS Synthetic Biology
- 出版年：2014
- 出版时间：December 19, 2014
- 年：2014
- 卷：3
- 期：12
- 页码：972-975
- 全文大小：257K
- ISSN：2161-5063
文摘
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.