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.
DNA computing is a new computational paradigm that employs biomolecular manipulation to solve computational problems. In 1994 Leonard Adleman surprised the scientific community by using the tools of molecular biology to solve an istance of the Directed Hamiltonian Path Problem (DHPP). This marked the first solution of a mathematical problem by use of biology.In the next years other problems had been tackled by using DNA manipulation. Theorical studies have supplemented experimental research of DNA algorithms by suggesting potential strategies for solving various problems by means of DNA computation as: SAT-problem, breaking DES, expansion of symbolic determinants. To give an idea of this new kind of computing we describe the first Adleman’s experiment and the theorical solution of SAT-problem by Richard Lipton. The latter was then implemented by many researchers. The best experimental result concerns a 20 variable instance of 3-SAT problem obtained in 2002 by a group of scientists directed by Adleman.
@article{BUMI_2006_8_9A_1_41_0,
author = {Raffaella Franci},
title = {Calcolare con il DNA},
journal = {Bollettino dell'Unione Matematica Italiana},
volume = {9-A},
year = {2006},
pages = {41-63},
zbl = {1200.94044},
mrnumber = {2228776},
language = {it},
url = {http://dml.mathdoc.fr/item/BUMI_2006_8_9A_1_41_0}
}
Franci, Raffaella. Calcolare con il DNA. Bollettino dell'Unione Matematica Italiana, Tome 9-A (2006) pp. 41-63. http://gdmltest.u-ga.fr/item/BUMI_2006_8_9A_1_41_0/
[1] , Molecular Computations of Solutions to Combinatorial Problems, Science, 18 april 1994, 1021-1024.
[2] , Computing with DNA, Scientific American, August 1998, 54-61, Trad. It. In «Le Scienze», Ott. 1998.
[3] - - - - , DNA molecule provides a computing machine with both data and fuel, Proc. Nat. Acad. Sci. USA, 2003.
[4] - - - - , Solution of a 20-variables 3-SAT Problem on a DNA computer, Science, 28 April 2002, 499-502.
[5] - , DNA, ultima frontiera del calcolo?, Lettera Matematica, 27-28, 1998, 14-19.
[6] , Mathematical proof and the reliability of DNA evidence, Am. Math. Monthly, 103 (6) (1996), 491-497. | MR 1390578 | Zbl 0856.05064
[7] - - - , Molecular computation: RNA solution to chess problem, Proc. Nat. Acad. Sci. USA, 97 (2000), 1369-1395.
[8] , On the Path to Computation with DNA, Science, 266, 11 nov. 1994, 993-994.
[9] , DNA Computing: Arrival of Biological Mathematics, Mathematical Intelligencer, 19 (2) (1997), 9-22. | MR 1457444
[10] , DNA Solution of hard Computational Problems, Science, 28 April 1995, 542-545.
[11] - - - - - , DNA computing on surfaces, Nature, 403, 2000.
[12] , Success and Challenges, Science, 19 April 2002, 478-479.
[13] - - - - - - , Molecular computation by DNA hairpin formation, Science, May 19, 2000, 1223-1226.