Ordinateur à ADN
Un article de Wikipédia, l'encyclopédie libre.
L'ordinateur à ADN est une des voies non-booléenne[1] actuellement explorées pour résoudre des problèmes combinatoires. Il ne prétend pas à la généralité et à la flexibilité d'un ordinateur général. Il s'agit plutôt d'un dispositif spécialisé comme peut l'être un processeur graphique, une carte son ou un convolveur.
Sommaire |
[modifier] Principe
En utilisant des fragments de brins d'ADN, on peut coder les contraintes d'une recherche sous forme d'enzymes (diastases). Dans un processus d'assemblage et de duplication de bases désoxyribonucléiques, les fragments ne répondant pas aux contraintes du problème sont éliminés par ces enzymes. En fin de processus, il ne reste plus que des chaînes ADN contenant la solution au problème cherché.
Un système de calcul utilisant de l'ADN s’appuie pourtant sur des mécanismes de codage fondamentalement différents de ceux de l’ordinateur conventionnel : Dans nos machines classiques, c’est la manipulation de charges électriques portés par des électrons au sein de dispositifs de commutation électroniques (transistors) qui matérialise l’information codée sous une forme binaire. Avec les ordinateurs à base d'ADN, l'information est traduite en termes d'unités chimiques de l'ADN.
Le principe du calcul avec un ordinateur à base d'ADN, consiste à synthétiser des séquences d'ADN particulières et de les laisser réagir dans un tube à essai. Le connecteur logique « ET » peut être obtenu par l’opération de séparation des brins d'ADN selon leurs séquences et le connecteur « OU » est réalisable en versant ensemble des solutions d'ADN contenant des séquences spécifiques.
Pour résoudre des problèmes comme le célèbre chemin hamiltonien du voyageur de commerce, on élabore une solution d’ADN dans laquelle les molécules d’ADN encodent par convention chacun des chemins possibles entre deux points. Par un procédé alternant les étapes de séparation et d’amplification, on élimine alors les chemins impossibles tels que ceux qui contenaient par exemple des points qu’ils n’étaient pas supposés contenir jusqu’à isoler la bonne solution.[2]
[modifier] Avantages et inconvénients
L'extrême lenteur de ce système (dont les temps de réponse se comptent en minutes, heures ou jours, et non en microsecondes) est compensée par son côté massivement parallèle : ce sont plusieurs millions ou milliards de molécules qui interagissent entre elles. En revanche, les entrées/sorties sont loin d'avoir la commodité de nos interfaces d'ordinateur actuelles.
Des premiers résultats ont été obtenus par Leonard Adleman (NASA, JPL)
- sur un exemple simple de problème du voyageur de commerce évoqué ci-dessus, à 7 villes en 1994
- sur un problème également NP-complet d'une vingtaine de nœuds en 2002.
Rappelons que les problèmes NP-complets ne peuvent être résolus qu'en examinant toutes les combinaisons possibles, ce qui rend le calcul à ADN parfaitement adéquat pour ces tâches. À la différence d'un ordinateur classique, l'explosion combinatoire est évitée.
[modifier] Références
[modifier] Liens externes
- DNA computer solves a complex problem (18 mars 2002)
- DNA Computer Puts Microbes to Work as Number Crunchers (Scientific American, 30 mai 2008)
