Seminar: DNA Computing

Voraussetzungen:
Vordiplom

Literatur:

1. L. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266:1021-1024, Nov. 1994.
2. N. Pisanti. A survey on DNA computing. EATCS Bulletin Nr.64, 188-216, Feb. 1998.
3. S. Kurtz, S. Mahaney, J. Royer, J. Simon. Biological computing. In Complexity Theory and Retroperspective. L. Hemaspaandra, A. Selman. 179-196 Springer 1997.

Beschreibung:
Im Jahre 1994 gelang es L. Adleman erstmals in einem Experiment Molekularbiologie zu einer Berechnung einzusetzten, indem er Instanzen eines NP-vollständigen Problems in ein DNA-Molekül codierte. Seither wurde in vielen Arbeiten untersucht, inwieweit sich molekularbiologische Methoden zur Lösung von schwierigen bis hin zu PSPACE-vollständigen Problemen verwenden lassen. In diesem Hauptseminar sollen einige dieser Arbeiten vorgestellt werden.

Themen:

1. J. Whatson, N. Hopkins,... Molecular biology of the gene. Benjamin/Cummings, third edition, 1987.
   Vortragender: Michael Dom 4.11.98
2. L. Adleman. Molecular Computation of Solutions to Combinatorial Problems. Science, 266:1021-1024, November 1994.
   Vortragender: Wolfgang Westje 18.11.
3. L. Adleman. On Constructing a Molecular Computer. In American Mathematical Scociety, Preceedings of the Second Annual Meeting on DNA Based Computer, June 1996.
   Vortragender: Elias Volanakis
4. R. Lipton. Speeding Up Computations via Molecular Biology. 1994. http://www.cs.priceton.edu/~rjl/bio.ps.
   R. Lipton. Using DNA to solve SAT. 1995. http://www.cs.priceton.edu/~dabo/bio-comp/sat.ps.
5. R. Karp, V. Kenyon, O. Waarts. Error resilient DNA Computation . In 7th ACM-SIAM Symposium on Discrete Algorithms, P 458-467, 1995.
   D. Boneh, R. Lipton. Making DNA Computers Error Resitant. In Proceeding of the Second Annual Meeting on DNA Based Computer, June 1996.
6. S. Kurtz, S. Mahaney, J. Royer, J. Simon. Biological computing. In Complexity Theory and Retroperspective. L. Hemaspaandra, A. Selman. 179-196 Springer 1997.
7. L. Adleman, P. Rothemund, S. Roweis, E. Winfree. On Applying Molecular Computation to the Data Encryption Standard. Proceedings of the Second Annual Meeting on DNA Based Computer, June 1996.
   D. Boneh, C. Dunworth, R. Lipton. Breaking DES Using a Molekular computer. Technical Report TR-499-95, Princeton University, 1995.
8. L. Landweber, R. Lipton. DNA2DNA Computations: A Potential 'Killer App'?. In LNCS269, Proceedings of the 24th ICALP 97, p 82-92, July 1997.
9. P. Rothemund. A DNA and restriction enzyme implementation of Turing Machine.. In American Mathematical Society, Proceedings of the Second Annual Meeting on DNA Based Computer, June 1996.
10. D. Ross , K. Wagner. On the Power of DNA-Computers. Information and Computation, 131:95-109, 1996.
11. A. Gibbons, M. Amos, D. Hodgson Models of DNA Computation. Proceedings of MFCS 96 p. 18-36.
12. S. Rotweis, E. Winfree,... A Sticker Based Architecture of DNA Computation.. Proceedings of the Second Annual Meeting on DNA Based Computer, June 1996.
13. R. Kosaraju, A. Delcher. Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees. Proceedings of STOC 95 p. 169-177.