Il calcolo con il Dna è un nuovo paradigma di calcolo che impiega manipolazioni biomolecolari per risolvere problemi computazionali. Nel 1994 Leonard Adleman sorprese la comunità scientifica usando gli strumenti della biologia molecolare per risolvere un’istanza del problema del percorso hamiltoniano su un grafo orientato (PPHO). Questa è stata la prima volta che un problema matematico è stato risolto con la biologia. Negli anni successivi molti altri problemi sono stati affrontati usando manipolazioni con il DNA. Numerosi studi teorici hanno suggerito algoritmi con il DNA per la soluzione di vari problemi come: il problema della soddisfacibilità di una formula booleana, la decifrazione del DES, il calcolo di determinanti etc..Per dare un’idea di questo nuovo tipo di calcolo si descrive il primo esperimento di Adleman e la soluzione teorica al problema della soddisfacibilità fornita da Richard Lipton, che è stata successivamente implementata da numerosi ricercatori. Il miglior risultato sperimentale a questo proposito è quello ottenuto nel 2002 da un gruppo di studiosi coordinati da Adleman e riguarda una formula con 20 variabili.
Referenze Bibliografiche
[1] L. A. ADLEMAN, Molecular Computations of Solutions to Combinatorial Problems, Science, 18 april 1994, 1021-1024.
[2] L. A. ADLEMAN, Computing with DNA, Scientific American, August 1998, 54-61, Trad. It. In «Le Scienze», Ott. 1998.
[3] Y. BENENSON - R. ADAR - T. PAZ-ELIZUR - Z. LIVNEH - E. SHAPIRO, DNA molecule provides a computing machine with both data and fuel, Proc. Nat. Acad. Sci. USA, 2003.
[4] R. S. BRAICH - N. CHELYAPOV - C. JOHNSON - P. W. ROTHEMUND - L. ADLEMAN, Solution of a 20-variables 3-SAT Problem on a DNA computer, Science, 28 April 2002, 499-502.
[5] F. CAPITELLI - F. IOZZI, DNA, ultima frontiera del calcolo?, Lettera Matematica, 27-28, 1998, 14-19.
[7] D. FAULHAMMER - A. R. CUKRAS - R. J. LIPTON - L. F. LANDWEBER, Molecular computation: RNA solution to chess problem, Proc. Nat. Acad. Sci. USA, 97 (2000), 1369-1395.
[8] D. K. GIFFORD, On the Path to Computation with DNA, Science, 266, 11 nov. 1994, 993-994.
[9]
L. KARI,
DNA Computing: Arrival of Biological Mathematics,
Mathematical Intelligencer,
19 (2) (
1997), 9-22. |
fulltext (doi) |
MR 1457444[10] R. J. LIPTON, DNA Solution of hard Computational Problems, Science, 28 April 1995, 542-545.
[11] Q. LIU - L. WANG - A. G. FRUTOS - A. E. CONDON - R. M. CORN - L. M. SMITH, DNA computing on surfaces, Nature, 403, 2000.
[12] J. H. REIF, Success and Challenges, Science, 19 April 2002, 478-479.
[13] K. SAKAMOTO - H. GOUNZU - K. KOMIYA - D. KIGA - S. YOKOYAMA - T. YOKOMORI - M. HAGIYA, Molecular computation by DNA hairpin formation, Science, May 19, 2000, 1223-1226.