13.6 Retour sur les ordinateurs ` a ADN
449
avait beaucoup de contaminants (solutions passant par plus de six arˆ etes ou moins de
six arˆ etes). Le gel utilis´ e pour l’´ electrophor` ese avait beaucoup d’imperfections, et, de
plus, les mol´ ecules d’ADN ´ etaient parfois trop repli´ ees sur elles-mˆ emes pour que leur
vitesse de migration soit proportionnelle `
a leur longueur. D’ailleurs, Adleman a avou´ e
qu’il avait dˆ u r´ ep´ eter l’´ electrophor` ese plusieurs fois pour qu’elle fonctionne.
De plus, dans l’exp´ erience d’Adleman, il y a toujours le risque que la solution ne soit
pas g´ en´ er´ ee. Regardons le graphe de la figure 13.1. Il existe des chemins, appel´ es cycles,
dont les sommets de d´ epart et d’arriv´ ee co¨ ıncident, par exemple le chemin 12351. Rien
n’empˆ eche a priori qu’il existe un chemin infini r´ ep´ etant cette boucle. Donc, le nombre
de chemins possibles est infini, alors que la quantit´ e d’ADN dans l’´ eprouvette est finie.
On doit s’arranger pour que cette quantit´ e soit suffisante pour permettre, avec une tr` es
grande probabilit´ e, que tous les chemins de longueur ≤ N , pour un certain N plus
grand que le nombre de sommets, soient g´ en´ er´ es. Bien sˆ ur, rien ne peut nous garantir `
a
100 % qu’ils seront tous pr´ esents. Il se peut bien que la solution du probl` eme du chemin
hamiltonien ne s’y trouve pas, mˆ eme si elle existe.
Dans ce type de calcul, si on trouve une solution, on peut conclure avec certitude,
mais si on n’en trouve pas, l’algorithme ne permet pas d’affirmer hors de tout doute
que la solution n’existe pas. Tout ce qu’on peut dire, c’est qu’il est tr` es probable qu’il
n’y ait pas de solution. C’est donc un algorithme probabiliste.
Le mod` ele th´ eorique de l’insertion–d´ el´ etion pose ´ egalement probl` eme. En effet,
nous avons suppos´ e qu’il ´ etait possible de faire n’importe quelle insertion et n’importe
quelle d´ el´ etion. Cela suppose qu’il existe un nombre infini d’enzymes ayant des actions diff´ erentes et qu’on puisse en placer un nombre aussi grand qu’on veut dans une
´ eprouvette, o` u ils agiront sans interf´ erence les uns avec les autres. Or, dans la r´ ealit´ e,
notre maˆ ıtrise de la biochimie est imparfaite, et nous ne comprenons pas assez bien
l’action des enzymes pour pouvoir op´ erer n’importe quelle insertion ou d´ el´ etion permise
par la th´ eorie.
Peut-on programmer un ordinateur ` a ADN ? Nos ordinateurs actuels ne sont
pas construits pour effectuer un seul programme. On peut, au contraire, leur apprendre
` a ex´ ecuter n’importe quel programme. Les ordinateurs `
a ADN, en revanche pourraient
sembler impossibles ` a programmer. En effet, les calculs faits par Adleman sont peu reproductibles, au sens que la m´ ethode de r´ esolution est faite sur mesure pour le probl` eme du
chemin hamiltonien (bien qu’une m´ ethode similaire puisse ˆ etre utilis´ ee pour r´ esoudre le
probl` eme de satisfaisabilit´ e). Mais nous avons vu qu’avec le mod` ele d’insertion–d´ el´ etion,
on peut reproduire tout ce que fait une machine de Turing. Or, il existe une machine
de Turing universelle [8], c’est-` a-dire une machine de Turing qui prend pour entr´ ee le
programme d’une machine de Turing M et l’entr´ ee ω sur laquelle on veut que la machine de Turing M travaille, et qui donne la sortie de la machine M lorsqu’elle re¸ coit
ω comme entr´ ee. Cette machine de Turing est donc programmable. Le th´ eor` eme 13.43
permet de conclure qu’un ordinateur `
a ADN pourrait th´ eoriquement l’ˆ etre.
Pour que ces id´ ees deviennent une technologie, il faudra relever des d´ efis ´ enormes,
mais elles sont fort s´ eduisantes.
449
avait beaucoup de contaminants (solutions passant par plus de six arˆ etes ou moins de
six arˆ etes). Le gel utilis´ e pour l’´ electrophor` ese avait beaucoup d’imperfections, et, de
plus, les mol´ ecules d’ADN ´ etaient parfois trop repli´ ees sur elles-mˆ emes pour que leur
vitesse de migration soit proportionnelle `
a leur longueur. D’ailleurs, Adleman a avou´ e
qu’il avait dˆ u r´ ep´ eter l’´ electrophor` ese plusieurs fois pour qu’elle fonctionne.
De plus, dans l’exp´ erience d’Adleman, il y a toujours le risque que la solution ne soit
pas g´ en´ er´ ee. Regardons le graphe de la figure 13.1. Il existe des chemins, appel´ es cycles,
dont les sommets de d´ epart et d’arriv´ ee co¨ ıncident, par exemple le chemin 12351. Rien
n’empˆ eche a priori qu’il existe un chemin infini r´ ep´ etant cette boucle. Donc, le nombre
de chemins possibles est infini, alors que la quantit´ e d’ADN dans l’´ eprouvette est finie.
On doit s’arranger pour que cette quantit´ e soit suffisante pour permettre, avec une tr` es
grande probabilit´ e, que tous les chemins de longueur ≤ N , pour un certain N plus
grand que le nombre de sommets, soient g´ en´ er´ es. Bien sˆ ur, rien ne peut nous garantir `
a
100 % qu’ils seront tous pr´ esents. Il se peut bien que la solution du probl` eme du chemin
hamiltonien ne s’y trouve pas, mˆ eme si elle existe.
Dans ce type de calcul, si on trouve une solution, on peut conclure avec certitude,
mais si on n’en trouve pas, l’algorithme ne permet pas d’affirmer hors de tout doute
que la solution n’existe pas. Tout ce qu’on peut dire, c’est qu’il est tr` es probable qu’il
n’y ait pas de solution. C’est donc un algorithme probabiliste.
Le mod` ele th´ eorique de l’insertion–d´ el´ etion pose ´ egalement probl` eme. En effet,
nous avons suppos´ e qu’il ´ etait possible de faire n’importe quelle insertion et n’importe
quelle d´ el´ etion. Cela suppose qu’il existe un nombre infini d’enzymes ayant des actions diff´ erentes et qu’on puisse en placer un nombre aussi grand qu’on veut dans une
´ eprouvette, o` u ils agiront sans interf´ erence les uns avec les autres. Or, dans la r´ ealit´ e,
notre maˆ ıtrise de la biochimie est imparfaite, et nous ne comprenons pas assez bien
l’action des enzymes pour pouvoir op´ erer n’importe quelle insertion ou d´ el´ etion permise
par la th´ eorie.
Peut-on programmer un ordinateur ` a ADN ? Nos ordinateurs actuels ne sont
pas construits pour effectuer un seul programme. On peut, au contraire, leur apprendre
` a ex´ ecuter n’importe quel programme. Les ordinateurs `
a ADN, en revanche pourraient
sembler impossibles ` a programmer. En effet, les calculs faits par Adleman sont peu reproductibles, au sens que la m´ ethode de r´ esolution est faite sur mesure pour le probl` eme du
chemin hamiltonien (bien qu’une m´ ethode similaire puisse ˆ etre utilis´ ee pour r´ esoudre le
probl` eme de satisfaisabilit´ e). Mais nous avons vu qu’avec le mod` ele d’insertion–d´ el´ etion,
on peut reproduire tout ce que fait une machine de Turing. Or, il existe une machine
de Turing universelle [8], c’est-` a-dire une machine de Turing qui prend pour entr´ ee le
programme d’une machine de Turing M et l’entr´ ee ω sur laquelle on veut que la machine de Turing M travaille, et qui donne la sortie de la machine M lorsqu’elle re¸ coit
ω comme entr´ ee. Cette machine de Turing est donc programmable. Le th´ eor` eme 13.43
permet de conclure qu’un ordinateur `
a ADN pourrait th´ eoriquement l’ˆ etre.
Pour que ces id´ ees deviennent une technologie, il faudra relever des d´ efis ´ enormes,
mais elles sont fort s´ eduisantes.