History


Help on query formulation
DNA computing. (Calcolare con il DNA.) (Italian)
Boll. Unione Mat. Ital., Sez. A, Mat. Soc. Cult. (8) 9, No. 1, 41-63 (2006).
Sommario: 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. (orig.)
Abstract: 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 instance 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. (orig.)
Classification: N90 M60
Valid XHTML 1.0 Transitional Valid CSS!