418
13 L’ordinateur ` a ADN
13.2 Le probl` eme du chemin hamiltonien r´ esolu par Adleman
Mˆ eme si on ne sait pas encore si on pourra un jour bˆ atir un ordinateur `
a ADN viable,
certains calculs simples ont d´ ej` a ´ et´ e effectu´ es sur des chaˆ ınes d’ADN. Comme on l’a dit
plus haut, Leonard Adleman a r´ eussi en 1994 ` a r´ esoudre un probl` eme concret de petite
taille en utilisant ce nouvel outil.
Le probl` eme avait pour point de d´ epart le graphe dirig´ e (ou graphe orient´ e)
repr´ esent´ e dans la figure 13.1. Un graphe dirig´ e est un ensemble de sommets (ici
num´ erot´ es de 0 ` a 6) et un ensemble d’arˆ etes dirig´ ees reliant deux sommets et repr´ esent´ ees
par des fl` eches partant du sommet de d´ epart et pointant vers le sommet d’arriv´ ee.
Le probl` eme du chemin hamiltonien consiste ` a trouver un chemin qui part du premier
sommet (sommet 0) et se rend jusqu’au dernier (sommet 6), en passant par chaque
sommet du graphe une et une seule fois, tout en suivant les directions indiqu´ ees par
les fl` eches des arˆ etes. Ceci est un probl` eme math´ ematique classique portant le nom de
recherche d’un chemin hamiltonien.
Fig. 13.1. Le graphe hamiltonien r´ esolu par Adleman
La solution d’Adleman Il a commenc´ e par associer ` a chaque sommet une chaˆ ıne
d’ADN simple constitu´ ee de huit bases azot´ ees. Par exemple, on pourrait donner au
sommet 0 le code
AGT T AGCA
et au sommet 1,
GAAACT AG.
Nous appellerons « pr´ enom » d’un sommet les quatre premi` eres bases de son code
et « nom », les quatre derni` eres. Les codes des arˆ etes sont compos´ es des bases compl´ ementaires du nom du sommet de d´ epart, suivies des compl´ ements du pr´ enom du sommet
d’arriv´ ee. Rappelons que A est le compl´ ement de T et C, celui de G. Par exemple,
l’arˆ ete allant du sommet 0 au sommet 1 porte le code T CGT CT T T puisque les bases
« T CGT » sont les compl´ ements du nom du sommet 0, AGT T AGCA, et « CT T T »,
celles du pr´ enom du sommet 1, GAAACT AG.
13 L’ordinateur ` a ADN
13.2 Le probl` eme du chemin hamiltonien r´ esolu par Adleman
Mˆ eme si on ne sait pas encore si on pourra un jour bˆ atir un ordinateur `
a ADN viable,
certains calculs simples ont d´ ej` a ´ et´ e effectu´ es sur des chaˆ ınes d’ADN. Comme on l’a dit
plus haut, Leonard Adleman a r´ eussi en 1994 ` a r´ esoudre un probl` eme concret de petite
taille en utilisant ce nouvel outil.
Le probl` eme avait pour point de d´ epart le graphe dirig´ e (ou graphe orient´ e)
repr´ esent´ e dans la figure 13.1. Un graphe dirig´ e est un ensemble de sommets (ici
num´ erot´ es de 0 ` a 6) et un ensemble d’arˆ etes dirig´ ees reliant deux sommets et repr´ esent´ ees
par des fl` eches partant du sommet de d´ epart et pointant vers le sommet d’arriv´ ee.
Le probl` eme du chemin hamiltonien consiste ` a trouver un chemin qui part du premier
sommet (sommet 0) et se rend jusqu’au dernier (sommet 6), en passant par chaque
sommet du graphe une et une seule fois, tout en suivant les directions indiqu´ ees par
les fl` eches des arˆ etes. Ceci est un probl` eme math´ ematique classique portant le nom de
recherche d’un chemin hamiltonien.
Fig. 13.1. Le graphe hamiltonien r´ esolu par Adleman
La solution d’Adleman Il a commenc´ e par associer ` a chaque sommet une chaˆ ıne
d’ADN simple constitu´ ee de huit bases azot´ ees. Par exemple, on pourrait donner au
sommet 0 le code
AGT T AGCA
et au sommet 1,
GAAACT AG.
Nous appellerons « pr´ enom » d’un sommet les quatre premi` eres bases de son code
et « nom », les quatre derni` eres. Les codes des arˆ etes sont compos´ es des bases compl´ ementaires du nom du sommet de d´ epart, suivies des compl´ ements du pr´ enom du sommet
d’arriv´ ee. Rappelons que A est le compl´ ement de T et C, celui de G. Par exemple,
l’arˆ ete allant du sommet 0 au sommet 1 porte le code T CGT CT T T puisque les bases
« T CGT » sont les compl´ ements du nom du sommet 0, AGT T AGCA, et « CT T T »,
celles du pr´ enom du sommet 1, GAAACT AG.