Ordinateur à ADN

Je voulus d'abord concevoir un ordinateur à ADN analogue à une machine de Turing, où le contrôleur à états finis serait remplacé par une enzyme. Une idée identique avait déjà été proposée dix ans plus tôt par des chercheurs de la Société IBM. Malheureusement, si une enzyme (l'ADN polymérase) permet de créer des ADN complémentaires, où trouverait-on les molécules qui assureraient d'autres calculs importants, telle la factorisation des nombres? Les biologistes moléculaires ont la chance inouïe de pouvoir utiliser le contenu des cellules. Nous sommes très loin de savoir créer ex nihilo des machines moléculaires aussi perfectionnées que l'ADN polymérase, mais trois ou quatre milliards d'années d'évolution ont engendré des cellules pleines de petites merveilles. La biotechnologie moderne emploie certaines de ces molécules, mais l'évolution n'a jamais produit de cellules qui jouent aux échecs. Aussi, pour construire des machines cellulaires aux capacités de calcul intéressantes, je devais utiliser les outils disponibles. Ces outils sont essentiellement les suivants:

1. L'appariement des bases. A chaque brin d'ADN correspond une molécule complémentaire. Dans une solution, lorsqu'un brin d'ADN rencontre l'ADN complémentaire, les deux brins s'apparient, c'est-à-dire qu'ils s'enroulent l'un autour de l'autre pour former une double hélice. Les brins ne réagissent pas chimiquement, mais se lient parce que des forces faibles, des "liaisons hydrogène", s'établissent entre les bases complémentaires. Quand un brin d'ADN rencontre un autre brin d'ADN qui ne lui est pas complémentaire ou qui ne possède pas de longues parties complémentaires, alors les deux brins ne se lient pas.
2. Des polymérases dupliquent l'information d'une molécule en créant une molécule complémentaire. Par exemple, l'ADN polymérase fabrique un brin d'ADN complémentaire à partir de n'importe quelle molécule d'ADN. ADN polymérase commence cette copie quand elle a rencontré un signal de départ qui lui indique le début de la séquence à copier. Ce signal est fourni par une amorce, une séquence d'ADN particulière et souvent courte. Dès que l'ADN polymérase trouve une amorce appariée au modèle, elle commence à ajouter des bases à l'amorce pour créer une copie complémentaire du modèle.
3. Des enzymes nommées ligases raboutent les molécules d'ADN. Lorsque deux molécules d'ADN sont proches, la ligase fait réagir une extrémité d'une molécule avec une extrémité de l'autre molécule : grâce à la liaison covalente ainsi établie, la ligase lie les deux molécules. Les cellules utilisent les ligases pour réparer les molécules d'ADN coupées par les rayonnements ultraviolets ou par d'autres rayonnements ionisants.
4. Des enzymes nommées nucléases coupent les molécules d'ADN. Par exemple, les enzymes de restriction cherchent une succession spécifique de bases dans un brin d'ADN et, quand elles l'ont trouvée, elles coupent l'ADN en deux parties. L'enzyme EcoRI, par exemple, est une enzyme de restriction qui coupe l'ADN de la bactérie Escherichia coli après le G de la séquence GAATRC; elle ne coupe jamais à un autre endroit. On a supposé que ces enzymes de restriction défendaient la bactérie contre les virus bactériophages, qui injectent leur ADN parasite dans la cellule bactérienne. La bactérie Escherichia coli protège son propre ADN de l'action de l'enzyme EcoRI par des méthylations (l'addition de groupes méthyle), lors de la réplication, mais tout virus qui posséderait la séquence GAATTC est inactivé, parce que son ADN est découpé en morceaux. Mon ordinateur à ADN n'utilise pas d'enzymes de restriction, mais celles-ci ont été utilisées, dans de nombreuses expériences, par d'autres équipes de recherche.
5. Des gels pour électrophorèse. Ceux-ci ne sont pas des constituants des cellules. On sépare des molécules d'ADN placées dans une solution en déposant une petite quantité de la solution sur un gel et en appliquant une différence de potentiel entre les deux extrémités du gel. Les molécules d'ADN négativement chargées migrent alors vers l'anode en se frayant un chemin à travers la structure réticulée du gel, à une vitesse qui dépend de leur longueur, les molécules les plus courtes se déplaÁant plus vite que les molécules plus longues. Ainsi, les biologistes séparent les brins d'ADN selon leur longueur : l'ajout d'une substance fluorescente qui se lie à l'ADN révèle la répartition finale des molécules d'ADN en fonction de leur longueur.
6. La synthèse de l'ADN. Aujourd'hui, on peut écrire une séquence d'ADN sur un bout de papier, l'envoyer à un laboratoire de synthèse, et recevoir quelques jours plus tard, un tube à essai qui contient approximativement 1018 molécules d'ADN, dont la plupart possèdent exactement la séquence demandée. On atteint facilement des longueurs de 100 bases et, pour des molécules dont la longueur est de 20 bases, le coût n'est que de 150 francs. Les molécules sont fournies déshydratées dans un tube à essai ; elles forment un petit grain, blanc et amorphe.

Comment ces divers ingrédients aident-ils à factoriser les nombres ou à jouer aux échecs ? Dans les années 1930, les mathématiciens ont démontré que deux ingrédients seulement sont indispensables pour construire un ordinateur: un moyen de stocker de l'information et un système pour effectuer quelques opérations simples. La machine de Turing stocke l'information au moyen de lettres écrites sur une bande et la manipule gr ce aux instructions simples que possède le contrïleur à états finis. Un ordinateur électronique stocke l'information dans sa mémoire sous la forme de séquences de 0 et de 1, et il la manipule gr ce à l'unité de calcul. N'importe quelle faÁon de stocker l'information et n'importe quel jeu d'instruction suffisent.

Suffisent à quoi? À effectuer n'importe quel calcul. Pour synthétiser un ADN complémentaire ou pour déterminer des coups aux échecs, il suffit de stocker la bonne information et d'appliquer la bonne séquence d'opérations, c'est-à-dire d'exécuter un programme. Or, l'ADN est un excellent système de stockage de l'information: les cellules l'utilisent depuis des milliards d'années pour stocker le modèle de la vie. Les enzymes telles que les polymérases et les ligases agissent sur cette information. Etait-ce suffisant pour construire une machine à calculer universelle? Gr ce aux mathématiciens des années 1930, je savais que oui.

Le problème du chemin hamiltonien

Quel problème résoudre? Il ne devait pas 'tre inventé spécialement pour la machine, et il devait démontrer les possibilités de cette nouvelle manière de calculer. J'ai choisi de résoudre le problème du chemin hamiltonien, une variante du problème du voyageur de commerce.

Les chemins hamiltoniens sont dus à William Rowan Hamilton, qui était astronome royal en Irlande, au milieu du XIX Siècle. Le problème qui porte son nom est décrit dans l'encadré de la page 58: soit une carte (graphe) oï figurent des villes reliées par des vols sans escale (chemins orientés). Par exemple, on peut aller de Grenoble à Rennes, mais pas de Rennes à Grenoble. On cherche le chemin qui part de Toulouse (le sommet de départ) et se termine à Lille (le sommet d'arrivée) en passant une fois et une seule par chacune des autres villes (Grenoble et Rennes). Un tel trajet est un chemin hamiltonien. Dans cet exemple, on voit rapidement qu'un seul chemin hamiltonien relie Toulouse à Lille ; c'est : Toulouse, Grenoble, Rennes, puis Lille. Entre Lille et Toulouse, il n'existe pas de chemin hamiltonien. Plus généralement, étant donné un graphe orienté, un sommet de départ et un sommet d'arrivée, alors il existe un chemin hamiltonien si et seulement s'il existe un chemin qui passe par tous les sommets exactement une fois. Le problème du chemin hamiltonien est la recherche de ce chemin.

Ce problème a été très étudié par les informaticiens, mais aucun algorithme efficace (c'est-à-dire rapide) n'a été trouvé. On connaÓt des graphes de moins de 100 sommets pour lesquels, m'me en utilisant le meilleur algorithme et le meilleur ordinateur, la résolution du problème du chemin hamiltonien prendrait des centaines d'années.<

Au début des années 1970, les informaticiens ont démontré que ce problème était " NP-complet" : la plupart pensent qu'on ne trouvera jamais d'algorithme rapide pour résoudre ce problème, bien que la preuve de cette supposition reste à fournir (voir Les lois du tout ou rien, par Jean-Paul Delahaye, Pour la Science, juillet 1995). Le problème du chemin hamiltonien n'est pas insoluble, mais le temps de calcul risque d''tre excessivement long.

Considérons par exemple l'algorithme suivant:

1. Engendrer un ensemble de chemins aléatoires.
2. Pour chaque chemin de l'ensemble:
1. Vérifier si le chemin part du sommet de départ et se termine au sommet d'arrivée. Sinon, le retirer de l'ensemble.
2. Vérifier si ce chemin passe exactement par n sommets. Sinon, le retirer de l'ensemble.
3. Pour chaque sommet, vérifier que ce chemin y passe. Sinon, retirer ce chemin de l'ensemble.
3. Si l'ensemble n'est pas vide, alors il existe un chemin hamiltonien. Si l'en semble est vide, alors il n'existe pas de chemin hamiltonien.

Cet algorithme est imparfait, mais si l'ensemble des chemins est engendré de manière suffisamment aléatoire et si l'ensemble résultant est suffisamment grand, alors cet algorithme donnera probablement la solution.

C'est cet algorithme que j'ai mis en oeuvre dans la première expérience de calcul avec l'ADN.

Sept jours dans un laboratoire

Pour cette première expérience, j'ai cherché un problème suffisamment simple pour qu'un prototype d'ordinateur à ADN le résolve, mais suffisamment important pour constituer une preuve indubitable de l'intér't de ces nouvelles machines. J'ai choisi un graphe comportant sept villes et 14 vols, représenté page 58. A la main, on met en moyenne une minute pour trouver l'unique chemin hamiltonien de ce graphe (vous pouvez commencer maintenant ... ).

Pour examiner la technique utilisée, considérons le graphe qui contient quatre villes seulement : Toulouse, Grenoble, Rennes et Lille, reliées par six vols. On cherche un chemin hamiltonien qui part de Toulouse et qui finit à Lille.

J'ai commencé par attribuer une séquence aléatoire d'ADN à chacune des villes: à Toulouse, j'ai associé ACTT GCAG, et à Grenoble TCGGACTG. J'ai alors imaginé que la première moitié des séquences était le prénom des villes et la seconde moitié leur nom propre. Ainsi le nom propre de Toulouse est GCAG, et le prénom de Grenoble TCGG. J'ai ensuite codé chaque vol en mettant bout à bout le nom propre de la ville d'origine avec le prénom de la ville d'arrivée. Dans notre exemple, le code du vol reliant Toulouse à Grenoble est GCAGTCGG. Comme on peut former un ADN complémentaire de tout brin d'ADN, chaque ville possède un nom complémentaire. Le nom complémentaire de Toulouse est TGAACGTC.

Après avoir effectué ces codages, j'ai synthétisé les séquences d'ADN complémentaires des noms de ville et les séquences des codes des vols. J'ai ensuite pris une pincée de chaque séquence, environ 1014 molécules que j'ai placées dans un tube à essai. Pour que le calcul commence, j'ai simplement ajouté de l'eau, de la ligase, du sel et quelques autres composants qui reproduisent les conditions qui règnent à l'intérieur d'une cellule. En tout, j'ai utilisé un cinquième de cuillerée à café de solution et, une seconde plus tard, j'avais la solution du problème du chemin hamiltonien.

Afin de comprendre le déroulement du calcul, examinons les réactions dans le tube. Le numéro du vol reliant Toulouse à Grenoble (GCAGTCGG), par exemple, et le nom complémentaire de Grenoble (ACCCTGAC) peuvent se rencontrer par hasard. Or, par construction, la première séquence se termine par TCGG, et la deuxième commence par AGCC. Ces séquences étant complémentaires, elles s'associent. La molécule complexe ainsi formée peut ensuite rencontrer la molécule associée au vol Grenoble - Rennes (ACTGGGCT), qui se liera à son tour au complexe, parce que la fin de celui-ci (TGAC) est complémentaire du début du code du vol (ACTG). Les molécules s'allongent ainsi à mesure que les codes des vols s'associent aux noms complémentaires des villes. Les ligases du mélange relient en permanence les chaines d'ADN codant les vols. Dans le tube, les molécules restantes représentent des chemins aléatoires passant par les différentes villes. La première étape de notre algorithme est terminée.

Comme on introduit initialement un très grand nombre de molécules et que le problème ne fait intervenir qu'un petit nombre de villes, on obtient très vraisemblablement au moins une molécule qui code le chemin hamiltonien cherché. Ainsi la solution d'un problème mathématique est stockée dans une simple molécule! Remarquons aussi que tous les chemins sont créés en m'me temps gr ce aux interactions simultanées de centaines de milliers de milliards de molécules. Cette réaction biochimique est un gigantesque calcul parallèle : tous les chemins possibles sont explorés en même temps. Pour la carte de la page 58, le seul chemin hamiltonien entre Toulouse et Lille de molécules qui codent des chemins qui ne sont pas hamiltoniens. Comment les éliminer? Pour enlever les molécules qui ne commencent pas par la ville de départ et qui ne se terminent pas par la ville d'arrivée, je me suis servi de la technique d'amplification des gènes (PCR). Cette technique utilise de nombreux exemplaires de deux séquences "amorces" complémentaires des deux extrémités de la séquence d'ADN que l'on désire amplifier. Ainsi, l'ADN polymérase effectue plusieurs cycles de réplication, alternativement sur chacun des brins. Les amorces utilisées sont, d'une part, le nom propre de la ville de départ (GCAG pour Toulouse) et, d'autre part, le complémentaire du prénom de la ville d'arrivée (GGCT pour Lille). Ces deux amorces agissent simultanément : la première prévient l'ADN polymérase de copier les séquences qui possèdent la bonne ville de départ, la seconde déclenche la duplication de molécules qui codent la bonne ville d'arrivée.

Pour amplifier l'ADN, on effectue des cycles à haute et à basse température. À haute température, on dissocie les complexes double brin pour libérer les séquences complémentaires des amorces. À basse température, on apparie les amorces, et l'ADN polymérase effectue la réplication, recréant une molécule double brin.

Ainsi, les molécules qui possèdent les bonnes villes de départ et d'arrivée se multiplient à une vitesse très élevée (exponentielle). En revanche, les molécules qui possèdent la bonne ville de départ, mais pas la bonne ville d'arrivée, ou réciproquement, se multiplient à une vitesse inférieure (linéaire). Les séquences d'ADN qui ne possèdent ni la bonne ville de départ ni la bonne ville d'arrivée ne se reproduisent pas du tout. Après la réaction, le tube à essai contient beaucoup de molécules dont les villes de départ et d'arrivée sont les bonnes, et peu de molécules ne satisfaisant pas ces deux critères. 2a de l'algorithme est alors terminé.

J'utilise ensuite un gel d'électrophorèse pour identifier les molécules qui possèdent la bonne longueur, 24 dans notre exemple; toutes les autres molécules sont éliminées. C'est l'étape 2b de notre algorithme.

Afin de vérifier que les séquences qui restent codent bien des chemins qui passent par les villes intermédiaires, j'utilise la complémentarité des séquences d'ADN dans une procédure nommée séparation par affinité. On utilise des sondes d'ADN qui codent le complémentaire du nom d'une ville particulière, par exemple Grenoble. Ces sondes sont fixées à de microscopiques sphères de fer d'un micromètre de diamètre environ. Quand on met ces billes en suspension dans le tube contenant les molécules restantes, seules les molécules contenant le nom de la ville désirée (Grenoble) se fixent sur les sondes. On place ensuite un aimant contre la paroi du tube à essai pour attirer et maintenir les boules métalliques. Puis on jette le liquide qui ne contient plus que des molécules ne possédant pas le nom désiré.

On ajoute alors un autre solvant et l'on retire l'aimant, afin de remettre les billes en suspension. Une augmentation de la température du mélange permet aux molécules de se séparer des sondes et de se dissoudre à nouveau dans le liquide. À l'aide de l'aimant, on attire les billes contre la paroi du tube à essai, mais, cette fois, aucune molécule n'y est fixée. Le liquide contient alors les brins d'ADN désirés: ceux qui codent des chemins passant par Grenoble. Il peut 'tre versé dans un autre tube pour un autre examen. On répète la procédure pour les autres villes intermédiaires, Rennes dans notre exemple. Après une journée complète de travail au laboratoire, je terminais cette procédure itérative ; c'était la partie la plus fastidieuse de l'expérience.

L'étape 2c de l'algorithme se termine avec la fin de la séparation par affinité: dans le tube se trouvent alors les molécules d'ADN qui codent le chemin hamiltonien. Ainsi, si le tube contenait un seul type de molécule, je pouvais en conclure qu'un chemin hamiltonien existait dans le graphe sinon, un tel chemin n'existait pas. Comment le savoir? En utilisant une nouvelle amplification des gènes, puis une autre électrophorèse. Cette analyse finale montra que les molécules restantes codaient effectivement le chemin désiré. Après sept jours de laboratoire, le premier calcul utilisant de l'ADN était terminé.

Dossier Vie Artificielle