Davidson Missouri W/Traveling Salesperson Problem - Revision history

Amshoecraft at 15:20, 9 August 2007

2007-08-09T15:20:08Z

Synthetic Students at 16:11, 25 July 2007

2007-07-25T16:11:40Z

Synthetic Students at 19:42, 11 July 2007

2007-07-11T19:42:14Z

Synthetic Students: Traveling Salesperson Problem moved to Davidson Missouri W/Traveling Salesperson Problem

2007-07-11T19:36:48Z

Traveling Salesperson Problem moved to Davidson Missouri W/Traveling Salesperson Problem

Synthetic Students at 19:29, 11 July 2007

2007-07-11T19:29:45Z

Synthetic Students at 18:20, 9 July 2007

2007-07-09T18:20:11Z

Synthetic Students at 18:14, 9 July 2007

2007-07-09T18:14:48Z

WikiSysop at 15:37, 2 July 2007

2007-07-02T15:37:52Z

New page

[[Image:TSP 4N graph.jpg|300px]]

The graph above shows a modified complete graph with edges leaving the ending node (#4), returning to the start node (#1), and moving from the start to the stop node removed. If we wanted to solve this weighted and directed graph for the shortest path through all nodes, starting at node #1, ending at node #4, and passing through each node only once, we could use our current HPP ''E. coli'' computer construct with one slight modification.
 
 
[[Image:TSP 4N shortest.jpg|900px]]

Instead of putting each half-gene back to back along an edge, we could add in spacers of specified lengths that would allow us to model the various weights in the graph above. These weights would give edges different lengths (in base pairs). After performing PCR on all of the solved plasmids (with primers binding to the promoter and terminator), we would be able to find the shortest path through all of the nodes by running the PCR products on a gel. Because the total length of the genes in any Hamiltonian Path through the graph is a constant, the smallest solved fragment will have the lowest total spacer length and will, therefore, be the solution to the Traveling Salesperson Problem (shown above).
 
 
[[Image:TSP 4N longer.jpg|900px]]

This image shows an alternate route through the graph. The length of this fragment is longer than the length of the solution to the TSP.
 
 
[[Image:TSP 4N falsepos.jpg|900px]]

False positives can also come into play with this construct. However, certain rules can be put into place when choosing spacer lengths to avoid having false positive PCR products that are longer than the true solution.

← Older revision		Revision as of 15:20, 9 August 2007
Line 1:		Line 1:
−	<center>[[Davidson Missouri W\| <span style="color:red">Home</span>]] \| [[Davidson Missouri W/Background Information\| <span style="color:red">Background Information</span>]] \| [[Davidson Missouri W/Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Davidson Missouri W/~~Probability and Statistics~~\| <span style="color:red">~~Probability and Statistics~~</span>]] \| [[Davidson Missouri W/Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Davidson Missouri W/Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Davidson Missouri W/Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Davidson Missouri W/Backwards promotion and read-through transcription\| <span style="color:red">Backwards Promotion and Read-Through Transcription</span>]] \| [[Davidson Missouri W/Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>	+	<center>[[Davidson Missouri W\| <span style="color:red">Home</span>]] \| [[Davidson Missouri W/Background Information\| <span style="color:red">Background Information</span>]] \| [[Davidson Missouri W/Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Davidson Missouri W/Mathematical Modeling\| <span style="color:red">Mathematical Modeling</span>]] \| [[Davidson Missouri W/Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Davidson Missouri W/Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Davidson Missouri W/Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Davidson Missouri W/Backwards promotion and read-through transcription\| <span style="color:red">Backwards Promotion and Read-Through Transcription</span>]] \| [[Davidson Missouri W/Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>

	<hr>		<hr>

← Older revision		Revision as of 16:11, 25 July 2007
Line 2:		Line 2:

	<hr>		<hr>
		+
		+	Although our current project is to develop a bacterial computer that solves Hamiltonian path problems, in the future we would like to tackle the Traveling Salesman problem using similar methods. Given a directed graph where each edge has a cost associated with it, what is the cheapest, or shortest, path to take such that you end at your starting point and visit every node exactly once?
		+

	[[Image:TSP 4N graph.jpg\|300px]]		[[Image:TSP 4N graph.jpg\|300px]]

← Older revision		Revision as of 19:42, 11 July 2007
Line 1:		Line 1:
−	<center>[[Davidson/Missouri W\| <span style="color:red">Home</span>]] \| [[Background Information\| <span style="color:red">Background Information</span>]] \| [[Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Backwards promotion and read-through transcription\| <span style="color:red">Backwards ~~promotion~~ and Read-Through Transcription</span>]] \| [[Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>	+	<center>[[Davidson Missouri W\| <span style="color:red">Home</span>]] \| [[Davidson Missouri W/Background Information\| <span style="color:red">Background Information</span>]] \| [[Davidson Missouri W/Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Davidson Missouri W/Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Davidson Missouri W/Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Davidson Missouri W/Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Davidson Missouri W/Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Davidson Missouri W/Backwards promotion and read-through transcription\| <span style="color:red">Backwards Promotion and Read-Through Transcription</span>]] \| [[Davidson Missouri W/Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>

	<hr>		<hr>

← Older revision		Revision as of 19:29, 11 July 2007
Line 1:		Line 1:
−	<center>[[Davidson/Missouri ~~Western iGEM 2007~~\| <span style="color:red">Home</span>]] \| [[Background Information\| <span style="color:red">Background Information</span>]] \| [[Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Backwards promotion and read-through transcription\| <span style="color:red">Backwards promotion and Read-Through Transcription</span>]] \| [[Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>	+	<center>[[Davidson/Missouri W\| <span style="color:red">Home</span>]] \| [[Background Information\| <span style="color:red">Background Information</span>]] \| [[Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Backwards promotion and read-through transcription\| <span style="color:red">Backwards promotion and Read-Through Transcription</span>]] \| [[Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>

	<hr>		<hr>

← Older revision		Revision as of 18:20, 9 July 2007
Line 1:		Line 1:
−	<center>[[Davidson/Missouri Western iGEM 2007\| <span style="color:red">Home</span>]] \| [[Background Information\| <span style="color:red">Background Information</span>]] \| [[Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Traveling Salesperson Problem\| <span style="color:~~red~~">Traveling Salesperson Problem</span> ]] \| [[Backwards promotion and read-through transcription\| <span style="color:red">Backwards promotion and Read-Through Transcription</span>]] \| [[Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>	+	<center>[[Davidson/Missouri Western iGEM 2007\| <span style="color:red">Home</span>]] \| [[Background Information\| <span style="color:red">Background Information</span>]] \| [[Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Traveling Salesperson Problem\| <span style="color:black">Traveling Salesperson Problem</span> ]] \| [[Backwards promotion and read-through transcription\| <span style="color:red">Backwards promotion and Read-Through Transcription</span>]] \| [[Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>

	<hr>		<hr>

← Older revision	Revision as of 19:36, 11 July 2007
(No difference)

← Older revision		Revision as of 18:14, 9 July 2007
Line 1:		Line 1:
		+	<center>[[Davidson/Missouri Western iGEM 2007\| <span style="color:red">Home</span>]] \| [[Background Information\| <span style="color:red">Background Information</span>]] \| [[Solving the HPP in vivo\| <span style="color:red">Current Project: Solving the Hamiltonian Path Problem ''in vivo''</span>]] \| [[Probability and Statistics\| <span style="color:red">Probability and Statistics</span>]] \| [[Gene splitting\| <span style="color:red"> Gene Splitting </span>]] \| [[Controlling Expression\| <span style="color:red"> Controlling Expression </span>]] \| [[Traveling Salesperson Problem\| <span style="color:red">Traveling Salesperson Problem</span> ]] \| [[Backwards promotion and read-through transcription\| <span style="color:red">Backwards promotion and Read-Through Transcription</span>]] \| [[Resources and Citations\|<span style="color:red">Resources and Citations</span>]]</center>
		+
		+	<hr>
		+
	[[Image:TSP 4N graph.jpg\|300px]]		[[Image:TSP 4N graph.jpg\|300px]]