Calcolare con il DNA

Raffaella Franci

Bollettino dell'Unione Matematica Italiana (2006)

  • Volume: 9-A, Issue: 1, page 41-63
  • ISSN: 0392-4033

Abstract

top
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.

How to cite

top

Franci, Raffaella. "Calcolare con il DNA." Bollettino dell'Unione Matematica Italiana 9-A.1 (2006): 41-63. <http://eudml.org/doc/289554>.

@article{Franci2006,
abstract = {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.},
author = {Franci, Raffaella},
journal = {Bollettino dell'Unione Matematica Italiana},
language = {ita},
month = {4},
number = {1},
pages = {41-63},
publisher = {Unione Matematica Italiana},
title = {Calcolare con il DNA},
url = {http://eudml.org/doc/289554},
volume = {9-A},
year = {2006},
}

TY - JOUR
AU - Franci, Raffaella
TI - Calcolare con il DNA
JO - Bollettino dell'Unione Matematica Italiana
DA - 2006/4//
PB - Unione Matematica Italiana
VL - 9-A
IS - 1
SP - 41
EP - 63
AB - 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.
LA - ita
UR - http://eudml.org/doc/289554
ER -

References

top
  1. ADLEMAN, L. A., Molecular Computations of Solutions to Combinatorial Problems, Science, 18 april 1994, 1021-1024. 
  2. ADLEMAN, L. A., Computing with DNA, Scientific American, August 1998, 54-61, Trad. It. In «Le Scienze», Ott. 1998. 
  3. BENENSON, Y. - ADAR, R. - PAZ-ELIZUR, T. - LIVNEH, Z. - SHAPIRO, E., DNA molecule provides a computing machine with both data and fuel, Proc. Nat. Acad. Sci. USA, 2003. 
  4. BRAICH, R. S. - CHELYAPOV, N. - JOHNSON, C. - ROTHEMUND, P. W. - ADLEMAN, L., Solution of a 20-variables 3-SAT Problem on a DNA computer, Science, 28 April 2002, 499-502. 
  5. CAPITELLI, F. - IOZZI, F., DNA, ultima frontiera del calcolo?, Lettera Matematica, 27-28, 1998, 14-19. 
  6. FALLIS, D., Mathematical proof and the reliability of DNA evidence, Am. Math. Monthly, 103 (6) (1996), 491-497. Zbl0856.05064MR1390578DOI10.2307/2974716
  7. FAULHAMMER, D. - CUKRAS, A. R. - LIPTON, R. J. - LANDWEBER, L. F., Molecular computation: RNA solution to chess problem, Proc. Nat. Acad. Sci. USA, 97 (2000), 1369-1395. 
  8. GIFFORD, D. K., On the Path to Computation with DNA, Science, 266, 11 nov. 1994, 993-994. 
  9. KARI, L., DNA Computing: Arrival of Biological Mathematics, Mathematical Intelligencer, 19 (2) (1997), 9-22. MR1457444DOI10.1007/BF03024425
  10. LIPTON, R. J., DNA Solution of hard Computational Problems, Science, 28 April 1995, 542-545. 
  11. LIU, Q. - WANG, L. - FRUTOS, A. G. - CONDON, A. E. - CORN, R. M. - SMITH, L. M., DNA computing on surfaces, Nature, 403, 2000. 
  12. REIF, J. H., Success and Challenges, Science, 19 April 2002, 478-479. 
  13. SAKAMOTO, K. - GOUNZU, H. - KOMIYA, K. - KIGA, D. - YOKOYAMA, S. - YOKOMORI, T. - HAGIYA, M., Molecular computation by DNA hairpin formation, Science, May 19, 2000, 1223-1226. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.