13.2 Le probl` eme du chemin hamiltonien r´ esolu par Adleman
419
Adleman a ensuite d´ epos´ e un grand nombre d’exemplaires, environ 10
14 mol´ ecules,
de chaque brin d’ADN codant un sommet ou une arˆ ete dans une ´ eprouvette. On sait que
les brins d’ADN ont une forte tendance ` a s’unir avec leurs compl´ ements. Par exemple,
si les brins des sommets 0 et 1 et celui de l’arˆ ete allant de 0 `
a 1 se trouvent ` a proximit´ e,
ils ont une forte chance de s’unir pour former le double brin
T C G T C T T T
| |
| | | | | |
A G T T A G C A G A A A C T A G
o` u le trait vertical indique un lien chimique stable entre bases compl´ ementaires. Le brin
inf´ erieur poss` ede encore des bases non appari´ ees. Celles-ci peuvent alors attirer d’autres
arˆ etes qui, `
a leur tour, attireront d’autres sommets. C’est donc un grand calcul en
parall` ele o` u tous les chemins possibles sont test´ es au mˆ eme moment. Ce parall´ elisme ne
serait pas possible avec un ordinateur classique, qui explore seulement un petit nombre
de possibilit´ es ` a chaque ´ etape.
En chauffant le m´ elange, on s´ epare les doubles brins en brins simples. On obtient
alors de longs « brins sommet » et de longs « brins arˆ ete ». Adleman a choisi de se limiter
aux brins sommet qu’on appellera « chemins » puisqu’ils mod´ elisent de vrais chemins
dans le graphe.
En principe, on s’attend `
a ce que tous les chemins possibles d’une longueur inf´ erieure
ou ´ egale `
a un certain N soient g´ en´ er´ es. Si le probl` eme comporte une solution, il est pratiquement certain qu’elle se retrouve dans l’´ eprouvette. Le probl` eme est alors d’isoler et
de lire cette solution. Parmi toutes ces chaˆ ınes d’ADN, comment reconnaˆ ıtre la bonne ?
Pour r´ eussir cet exploit, Adleman a dˆ u recourir ` a plusieurs techniques biologiques ou
chimiques relativement complexes. En effet, cette partie est (et de beaucoup) la plus
longue et la plus on´ ereuse de toutes les ´ etapes de la solution. L’algorithme de base
est assez facile ` a comprendre sous sa forme th´ eorique. En effet, Adleman a utilis´ e la
« m´ ethode brute » qui consiste `
a examiner chacun des chemins possibles pour ensuite
s´ electionner le bon.
Pour isoler la solution, Adleman a proc´ ed´ e en cinq ´ etapes.
´
Etape 1 Il faut s´ electionner tous les chemins qui commencent par le sommet 0 et qui
finissent par le sommet 6. L’id´ ee est de multiplier ces chemins pour qu’ils dominent en
nombre tous les autres. Les d´ etails de cette ´ etape requi` erent des notions de chimie. Nous
en parlerons ` a la section 13.6.3.
´
Etape 2 Parmi les chemins multipli´ es ` a l’´ etape 1, il faut s´ electionner tous ceux qui
contiennent une suite de sept sommets (donc six arˆ etes). La longueur de ces chemins
sera de 56 bases azot´ ees, contre 48 bases azot´ ees pour le brin simple qui contient les
arˆ etes (voir la figure 13.2). Pour ce faire, Adleman a utilis´ e l’´ electrophor` ese, qui est un
proc´ ed´ e d´ ej` a bien connu en biologie. L’id´ ee est d’induire une charge n´ egative sur un
´ echantillon de la solution de mol´ ecules d’ADN et de d´ eposer cet ´ echantillon d’un cˆ ot´ e
d’une plaque de gel. Ensuite, on applique une diff´ erence de potentiel entre les deux cˆ ot´ es
de la plaque (voir la figure 13.3).
419
Adleman a ensuite d´ epos´ e un grand nombre d’exemplaires, environ 10
14 mol´ ecules,
de chaque brin d’ADN codant un sommet ou une arˆ ete dans une ´ eprouvette. On sait que
les brins d’ADN ont une forte tendance ` a s’unir avec leurs compl´ ements. Par exemple,
si les brins des sommets 0 et 1 et celui de l’arˆ ete allant de 0 `
a 1 se trouvent ` a proximit´ e,
ils ont une forte chance de s’unir pour former le double brin
T C G T C T T T
| |
| | | | | |
A G T T A G C A G A A A C T A G
o` u le trait vertical indique un lien chimique stable entre bases compl´ ementaires. Le brin
inf´ erieur poss` ede encore des bases non appari´ ees. Celles-ci peuvent alors attirer d’autres
arˆ etes qui, `
a leur tour, attireront d’autres sommets. C’est donc un grand calcul en
parall` ele o` u tous les chemins possibles sont test´ es au mˆ eme moment. Ce parall´ elisme ne
serait pas possible avec un ordinateur classique, qui explore seulement un petit nombre
de possibilit´ es ` a chaque ´ etape.
En chauffant le m´ elange, on s´ epare les doubles brins en brins simples. On obtient
alors de longs « brins sommet » et de longs « brins arˆ ete ». Adleman a choisi de se limiter
aux brins sommet qu’on appellera « chemins » puisqu’ils mod´ elisent de vrais chemins
dans le graphe.
En principe, on s’attend `
a ce que tous les chemins possibles d’une longueur inf´ erieure
ou ´ egale `
a un certain N soient g´ en´ er´ es. Si le probl` eme comporte une solution, il est pratiquement certain qu’elle se retrouve dans l’´ eprouvette. Le probl` eme est alors d’isoler et
de lire cette solution. Parmi toutes ces chaˆ ınes d’ADN, comment reconnaˆ ıtre la bonne ?
Pour r´ eussir cet exploit, Adleman a dˆ u recourir ` a plusieurs techniques biologiques ou
chimiques relativement complexes. En effet, cette partie est (et de beaucoup) la plus
longue et la plus on´ ereuse de toutes les ´ etapes de la solution. L’algorithme de base
est assez facile ` a comprendre sous sa forme th´ eorique. En effet, Adleman a utilis´ e la
« m´ ethode brute » qui consiste `
a examiner chacun des chemins possibles pour ensuite
s´ electionner le bon.
Pour isoler la solution, Adleman a proc´ ed´ e en cinq ´ etapes.
´
Etape 1 Il faut s´ electionner tous les chemins qui commencent par le sommet 0 et qui
finissent par le sommet 6. L’id´ ee est de multiplier ces chemins pour qu’ils dominent en
nombre tous les autres. Les d´ etails de cette ´ etape requi` erent des notions de chimie. Nous
en parlerons ` a la section 13.6.3.
´
Etape 2 Parmi les chemins multipli´ es ` a l’´ etape 1, il faut s´ electionner tous ceux qui
contiennent une suite de sept sommets (donc six arˆ etes). La longueur de ces chemins
sera de 56 bases azot´ ees, contre 48 bases azot´ ees pour le brin simple qui contient les
arˆ etes (voir la figure 13.2). Pour ce faire, Adleman a utilis´ e l’´ electrophor` ese, qui est un
proc´ ed´ e d´ ej` a bien connu en biologie. L’id´ ee est d’induire une charge n´ egative sur un
´ echantillon de la solution de mol´ ecules d’ADN et de d´ eposer cet ´ echantillon d’un cˆ ot´ e
d’une plaque de gel. Ensuite, on applique une diff´ erence de potentiel entre les deux cˆ ot´ es
de la plaque (voir la figure 13.3).