Class notes

Page 20

Computing with DNA?

1. The problem to be solved is the "Hamiltonian Path" problem ... how to get from from A to B in a graph touching on all nodes along the way. The version of the problem considered is for directed graphs.
2. The problem is NP-hard (the article only says "hard", but we know better).
3. Cities are coded as 6-letter sequences (really 20, but 6 in the example in the article).
4. The 6-letter pieces for city X really consists of two meaningful parts. The first 3 letters mean "arriving at X", the second 3 "leaving from X". Flights from X to Y are represented by the 6-letter sequence "leaving from X, arriving at Y".
5. The "soup" supports the random formation of all DNA strands with cities being spliced together by flights. For this, one of them (cities in the article) need to be coded in their DNA complements.
6. Solutions have certain chemical properties and can be extracted.

What do we have here?

1. In what sense is the TSP a "simplified version" of the Hamiltonian Path problem, as stated on page 114 of the article?
2. Is the 10 raised to the 147th power that is mentioned on page 115 justified? If so, how?
3. Does this DNA computer solve a problem that is beyond the reach of current electronic computers?

Last edited (or copied to this place) at 9:03 AM, Wednesday, October 11, 1995.