13.1 Introduction
417
meilleurs algorithmes. En mˆ eme temps, le parall´ elisme des ordinateurs augmente, ce qui
permet de faire plusieurs op´ erations simultan´ ement au lieu de les faire en s´ erie, et qui
diminue d’autant le temps de calcul. En 2005, le plus gros ordinateur de la plan` ete avait
131 072 processeurs en parall` ele. Le nombre de processeurs en parall` ele risque de rester
toujours limit´ e, car de tels ordinateurs coˆ utent une fortune et deviennent vite obsol` etes.
L’ordinateur `
a ADN est n´ e en 1994. C’est Leonard Adleman, un informaticien
th´ eoricien d´ ej` a cr´ eateur du code RSA en cryptographie (voir le chapitre 7), qui a observ´ e
que les op´ erations biologiques effectu´ ees sur l’ADN `
a l’int´ erieur des cellules pouvaient
avoir un potentiel informatique, car elles s’apparentent `
a des op´ erations logiques. La
mol´ ecule d’ADN est une tr` es grande mol´ ecule form´ ee de deux brins enroul´ es en double
h´ elice, que l’on peut s´ eparer en deux brins simples comme on ouvre une fermeture-´ eclair.
Chacun des brins simples est une suite de bases azot´ ees de quatre types : A (ad´ enine),
C (cytosine), G (guanine) et T (thymine). On peut assembler deux brins simples en un
brin double si les deux brins sont compl´ ementaires : les A ne peuvent se lier qu’avec des
T , et les C, qu’avec des G. Certains enzymes permettent de couper les brins d’ADN `
a
des endroits pr´ ecis appel´ es « loci ». On peut enlever un morceau d’ADN bien d´ etermin´ e
s’il se trouve entre deux loci pr´ ed´ etermin´ es (d´ el´ etion) ou encore, ins´ erer un morceau
d’ADN ´ egalement bien d´ etermin´ e ` a un endroit tr` es pr´ ecis (insertion). De plus, l’ADN
polym´ erase (un autre enzyme) permet de dupliquer les mol´ ecules d’ADN et donc, de
cloner des mol´ ecules d’ADN identiques. Adleman a vu dans ces op´ erations l’´ equivalent
des circuits ´ electriques ou des transistors `
a la base des ordinateurs classiques (voir, par
exemple, la section 15.7 du chapitre 15). L’ordinateur `
a ADN ´ etait n´ e. . . Pour d´ emontrer
le fait, Adleman a construit, ` a l’aide de manipulations de chaˆ ınes d’ADN en laboratoire,
la solution d’un chemin hamiltonien `
a sept villes. Cette prouesse d’Adleman a lanc´ e la
recherche sur le sujet. Comme pour l’ordinateur classique, la recherche s’est d´ evelopp´ ee
dans plusieurs directions. Sur le plan th´ eorique, elle est tr` es avanc´ ee. Kari et Thierrin [5]
ont montr´ e que toute fonction calculable par une machine de Turing est calculable avec
des chaˆ ınes d’ADN sur lesquelles on effectue des op´ erations de d´ el´ etion et d’insertion.
Nous d´ emontrerons ce th´ eor` eme ` a la section 13.4. De mˆ eme que dans le cas des machines
de Turing, les algorithmes th´ eoriques utilis´ es dans la preuve ne seront pas n´ ecessairement
les algorithmes rapides requis pour r´ esoudre de gros probl` emes num´ eriques. La recherche
se poursuit aussi du cˆ ot´ e pratique. Pour r´ esoudre son probl` eme de chemin hamiltonien
` a sept villes, Adleman a eu besoin de sept jours en laboratoire, alors que n’importe qui
peut trouver la solution `
a la main en quelques minutes. On ne sait pas encore si on
pourra, en laboratoire, r´ esoudre de gros probl` emes avec un ordinateur `
a ADN. Dans le
cas du chemin hamiltonien, on voit rapidement que la m´ ethode d’Adleman ne pourrait
pas fonctionner pour un grand nombre de villes. Mais comme le parall´ elisme des ordinateurs classiques demeurera limit´ e ce qui int´ eresse les chercheurs, c’est de d´ eterminer
le potentiel de parall´ elisme d’un ordinateur ` a ADN. A priori, on peut cloner de tr` es
grandes quantit´ es de mol´ ecules d’ADN de quelques types donn´ es. En les m´ elangeant
dans une ´ eprouvette avec des enzymes donn´ es, on peut esp´ erer faire un grand nombre
d’insertions et de d´ el´ etions en parall` ele. Peut-on utiliser ces propri´ et´ es pour construire
un ordinateur dot´ e d’un grand parall´ elisme ? La recherche se poursuit. . .
417
meilleurs algorithmes. En mˆ eme temps, le parall´ elisme des ordinateurs augmente, ce qui
permet de faire plusieurs op´ erations simultan´ ement au lieu de les faire en s´ erie, et qui
diminue d’autant le temps de calcul. En 2005, le plus gros ordinateur de la plan` ete avait
131 072 processeurs en parall` ele. Le nombre de processeurs en parall` ele risque de rester
toujours limit´ e, car de tels ordinateurs coˆ utent une fortune et deviennent vite obsol` etes.
L’ordinateur `
a ADN est n´ e en 1994. C’est Leonard Adleman, un informaticien
th´ eoricien d´ ej` a cr´ eateur du code RSA en cryptographie (voir le chapitre 7), qui a observ´ e
que les op´ erations biologiques effectu´ ees sur l’ADN `
a l’int´ erieur des cellules pouvaient
avoir un potentiel informatique, car elles s’apparentent `
a des op´ erations logiques. La
mol´ ecule d’ADN est une tr` es grande mol´ ecule form´ ee de deux brins enroul´ es en double
h´ elice, que l’on peut s´ eparer en deux brins simples comme on ouvre une fermeture-´ eclair.
Chacun des brins simples est une suite de bases azot´ ees de quatre types : A (ad´ enine),
C (cytosine), G (guanine) et T (thymine). On peut assembler deux brins simples en un
brin double si les deux brins sont compl´ ementaires : les A ne peuvent se lier qu’avec des
T , et les C, qu’avec des G. Certains enzymes permettent de couper les brins d’ADN `
a
des endroits pr´ ecis appel´ es « loci ». On peut enlever un morceau d’ADN bien d´ etermin´ e
s’il se trouve entre deux loci pr´ ed´ etermin´ es (d´ el´ etion) ou encore, ins´ erer un morceau
d’ADN ´ egalement bien d´ etermin´ e ` a un endroit tr` es pr´ ecis (insertion). De plus, l’ADN
polym´ erase (un autre enzyme) permet de dupliquer les mol´ ecules d’ADN et donc, de
cloner des mol´ ecules d’ADN identiques. Adleman a vu dans ces op´ erations l’´ equivalent
des circuits ´ electriques ou des transistors `
a la base des ordinateurs classiques (voir, par
exemple, la section 15.7 du chapitre 15). L’ordinateur `
a ADN ´ etait n´ e. . . Pour d´ emontrer
le fait, Adleman a construit, ` a l’aide de manipulations de chaˆ ınes d’ADN en laboratoire,
la solution d’un chemin hamiltonien `
a sept villes. Cette prouesse d’Adleman a lanc´ e la
recherche sur le sujet. Comme pour l’ordinateur classique, la recherche s’est d´ evelopp´ ee
dans plusieurs directions. Sur le plan th´ eorique, elle est tr` es avanc´ ee. Kari et Thierrin [5]
ont montr´ e que toute fonction calculable par une machine de Turing est calculable avec
des chaˆ ınes d’ADN sur lesquelles on effectue des op´ erations de d´ el´ etion et d’insertion.
Nous d´ emontrerons ce th´ eor` eme ` a la section 13.4. De mˆ eme que dans le cas des machines
de Turing, les algorithmes th´ eoriques utilis´ es dans la preuve ne seront pas n´ ecessairement
les algorithmes rapides requis pour r´ esoudre de gros probl` emes num´ eriques. La recherche
se poursuit aussi du cˆ ot´ e pratique. Pour r´ esoudre son probl` eme de chemin hamiltonien
` a sept villes, Adleman a eu besoin de sept jours en laboratoire, alors que n’importe qui
peut trouver la solution `
a la main en quelques minutes. On ne sait pas encore si on
pourra, en laboratoire, r´ esoudre de gros probl` emes avec un ordinateur `
a ADN. Dans le
cas du chemin hamiltonien, on voit rapidement que la m´ ethode d’Adleman ne pourrait
pas fonctionner pour un grand nombre de villes. Mais comme le parall´ elisme des ordinateurs classiques demeurera limit´ e ce qui int´ eresse les chercheurs, c’est de d´ eterminer
le potentiel de parall´ elisme d’un ordinateur ` a ADN. A priori, on peut cloner de tr` es
grandes quantit´ es de mol´ ecules d’ADN de quelques types donn´ es. En les m´ elangeant
dans une ´ eprouvette avec des enzymes donn´ es, on peut esp´ erer faire un grand nombre
d’insertions et de d´ el´ etions en parall` ele. Peut-on utiliser ces propri´ et´ es pour construire
un ordinateur dot´ e d’un grand parall´ elisme ? La recherche se poursuit. . .