DNA Computing, 2001 version (solutions)

Feel free to work on the homework in groups. The work you hand in, however, should reflect your understanding of the material and be in your own words. Students who turn in identical (or close to identical) homework assignments will be asked to explain their answers orally to the TA or prof. A student who cannot explain how he or she arrived at a given answer will be charged with academic dishonesty.

You should justify all of your answers for full credit.

Dr. Giaever spoke about the traveling salesman problem and the related but simpler Hamiltonian path problem. The questions below should be answerable with only the information in the problem and/or the handout with the Scientific American article.

1. What is the difference between the two problems?
The Hamiltonian path problem is concerned with finding a route which passes through each of a set of points (cities) and does so only once. The travelling salesman problem is a special case of this which requires that the shortest of all such paths be found.

2. For the 10-city problem, assume each city is connected to only 5 other cities, how many possible routes go through 10 and only 10 (not necessarily different) cities? (Hint: the first city can be any one of 10 cities, and each successive connection could take you to any one of 5 cities)
Example: If you had only 5 cities with 3 possible connections from each city, the number of possible routes would be found as follows:

The first city could be any of the 5 cities: 5 possibilities

The next leg could be any of the 3 connected cities: 5*3 = 15 possiblities

From each of those possible second cities, you could travel to one of 3 cities: 15*3 = 45 possiblities

Ditto for the fourth city: 45*3 = 135 possible paths to 4 cities

And for the fifth and final city: 135*5 = 675 total possible paths stopping in 5 cities

To summarize, we took the number of cities (5) and multiplied by the number of connections from each city (3) four (5-1) times: Total = 5 * 3⁴. For 10 interconnected cities there are 10 possible starting points. After a starting points is chosen, there are 9 possible options for the second city, and so forth. This forms a geometric series 10*9*8*7*6*5*4*3*2*1 = 10! The number of possible paths is equal to the product of this series,
number of paths = 10! = 3.6 x 10⁶

3. If I double the number of cities to 20 cities, while keeping the number of connections per city at 5, how many possible routes go through 20 cities? How many times bigger is this number than the answer for 10 cities (what is the ratio of routes for 20 cities to routes for 10 cities)?
For 20 cities the number of paths increases to 20! = 2.4 x 10¹⁸ which is 6.7 x 10¹¹ larger than 10!

4. Assume for simplicity that a traditional computer makes 10 calculations/steps for each route. How long will it take to calculate all possible routes for the 10-city case using a computer that performs 1 billion calculations per second (1E9 Hz)? How long for the 20-city case?
For the 10 city case: 3.6 x 10⁶ routes * 10 calculations / route* (1 / 10⁸ calculation / second) = .36 s For the 20 city case:
2.4 x 10¹⁸ routes * 10 calculations / route* (1 / 10⁸ calculation / second) = 2.4 x 10¹¹s

5. Assume for simplicity that solving this problem with DNA requires 100 strands of DNA per possible route. In addition, assume that each one of these strands of DNA occupy a cylindrical volume with radius 10^-8 m and length 10^-7 m, giving a volume of p*10^-23 m³. What volume container would be needed to hold all of the DNA used to solve the 10-city case? The 20-city case?
For the 10 city case: 3.6 x 10⁶ routes * 10 strands / route* (p x 10²³ m³ / strand) = 1.1 x 10-^-14 m³ For the 20 city case:
2.4 x 10¹⁸ routes * 10 strands / route* (p x 10²³ m³/ strand) = 7.5 x 10^-3 m³

6. Solving the Hamiltonian path problem with DNA takes on the order of 2 hours. Use your answers to the previous question to argue the relative merits and limitations of DNA computing vs. using a traditional computer.
For the 10 city case the DNA process is slower, 2 hours as opposed to .36 seconds. However, for the 20 city case a DNA computation is many times faster, 2 hours relative to 7631 years.

7. Dr. Giaever discussed several techniques used in solving the Hamiltonian Path problem with DNA. Pick one of the techniques listed below and explain (a) how it works, and (b) how it is used in solving the Hamiltonian Path problem.

Polymer Chain Reaction

Electrophoresis

Using magnetic balls with strings of DNA attached

1.	What is the difference between the two problems? The Hamiltonian path problem is concerned with finding a route which passes through each of a set of points (cities) and does so only once. The travelling salesman problem is a special case of this which requires that the shortest of all such paths be found.
2.	For the 10-city problem, assume each city is connected to only 5 other cities, how many possible routes go through 10 and only 10 (not necessarily different) cities? (Hint: the first city can be any one of 10 cities, and each successive connection could take you to any one of 5 cities) Example: If you had only 5 cities with 3 possible connections from each city, the number of possible routes would be found as follows: The first city could be any of the 5 cities: 5 possibilities The next leg could be any of the 3 connected cities: 53 = 15 possiblities From each of those possible second cities, you could travel to one of 3 cities: 153 = 45 possiblities Ditto for the fourth city: 453 = 135 possible paths to 4 cities And for the fifth and final city: 1355 = 675 total possible paths stopping in 5 cities To summarize, we took the number of cities (5) and multiplied by the number of connections from each city (3) four (5-1) times: Total = 5 * 3⁴. For 10 interconnected cities there are 10 possible starting points. After a starting points is chosen, there are 9 possible options for the second city, and so forth. This forms a geometric series 10987654321 = 10!* The number of possible paths is equal to the product of this series, number of paths = 10! = 3.6 x 10⁶
3.	If I double the number of cities to 20 cities, while keeping the number of connections per city at 5, how many possible routes go through 20 cities? How many times bigger is this number than the answer for 10 cities (what is the ratio of routes for 20 cities to routes for 10 cities)? For 20 cities the number of paths increases to 20! = 2.4 x 10¹⁸ which is 6.7 x 10¹¹ larger than 10!
4.	Assume for simplicity that a traditional computer makes 10 calculations/steps for each route. How long will it take to calculate all possible routes for the 10-city case using a computer that performs 1 billion calculations per second (1E9 Hz)? How long for the 20-city case? For the 10 city case: 3.6 x 10⁶ routes 10 calculations / route* (1 / 10⁸ calculation / second) = .36 s* For the 20 city case: 2.4 x 10¹⁸ routes 10 calculations / route* (1 / 10⁸ calculation / second) = 2.4 x 10¹¹s*
5.	Assume for simplicity that solving this problem with DNA requires 100 strands of DNA per possible route. In addition, assume that each one of these strands of DNA occupy a cylindrical volume with radius 10^-8 m and length 10^-7 m, giving a volume of p10^-23 m³. What volume container would be needed to hold all of the DNA used to solve the 10-city case? The 20-city case? For the 10 city case:* 3.6 x 10⁶ routes 10 strands / route* (p x 10²³ m³ / strand) = 1.1 x 10-^-14 m³* For the 20 city case: 2.4 x 10¹⁸ routes 10 strands / route* (p x 10²³ m³/ strand) = 7.5 x 10^-3 m³*
6.	Solving the Hamiltonian path problem with DNA takes on the order of 2 hours. Use your answers to the previous question to argue the relative merits and limitations of DNA computing vs. using a traditional computer. For the 10 city case the DNA process is slower, 2 hours as opposed to .36 seconds. However, for the 20 city case a DNA computation is many times faster, 2 hours relative to 7631 years.
7.	Dr. Giaever discussed several techniques used in solving the Hamiltonian Path problem with DNA. Pick one of the techniques listed below and explain (a) how it works, and (b) how it is used in solving the Hamiltonian Path problem. Polymer Chain Reaction Electrophoresis Using magnetic balls with strings of DNA attached