Cet article est une traduction automatique ; la version originale en anglais fait foi. Lire l'original
Trente-neuf villes nécessitent plus d'ADN que la Terre
Une recherche d'itinéraire par force brute, à raison d'un brin d'ADN par ordre candidat, nécessite un demi-gramme d'ADN pour vingt villes. Pour trente-neuf, il en faut plus que la masse de la Terre.
En 1994, Leonard Adleman a dissous un problème combinatoire dans un tube à essai. Il a encodé un réseau routier de sept villes sous forme de courts brins d'ADN, les a laissés s'hybrider pour former tous les parcours autorisés par le réseau, puis a filtré la soupe pour ne retenir que les parcours visitant chaque ville exactement une fois. La réponse a précipité au fond d'un flacon. Il a fallu environ une semaine de travail en laboratoire pour résoudre un problème qu'un étudiant résout sur papier en une minute, et là n'était absolument pas la question : quelque 10¹⁴ brins avaient chacun testé un parcours simultanément, dans un volume qui tiendrait entre deux doigts.
La promesse était évidente et immense. La recherche exponentielle est difficile parce que le nombre de candidats explose ; on avait là une machine capable d'examiner tous les candidats à la fois. Trente ans plus tard, aucun appareil dans votre poche ne fonctionne à l'ADN, et la raison n'est pas une question d'ingénierie. C'est une arithmétique que l'on peut faire au dos d'une enveloppe.
Compter les brins, puis les peser
Le parallélisme moléculaire s'achète une molécule à la fois. Chaque candidat exige son propre brin physique ; la quantité d'ADN requise est donc le nombre de candidats multiplié par la masse d'un brin.
Le second facteur est très petit. L'ADN simple brin pèse environ 330 grammes par mole de bases ; ainsi, à raison de vingt bases par ville, un brin pour vingt villes pèse approximativement 2 × 10⁻¹⁹ grammes. Le premier facteur est une factorielle, et une factorielle n'a que faire de la petitesse du second.
Vingt villes : 0,53 gramme. Une pincée de poudre.
Trente villes : 8,7 × 10¹³ grammes. Soit 87 millions de tonnes, environ un cinquième de la masse cumulée de tous les êtres humains vivants.
Trente-neuf villes : plus que la masse de la Terre.
Dix-neuf villes séparent « une pincée » de « la planète », raison pour laquelle DNA Computing Scale se présente sous la forme d'un curseur plutôt que d'un paragraphe. Faites-le progresser d'une ville à la fois, et l'échelle de comparaison grimpe de « moins d'un gramme » aux kilogrammes et aux tonnes, jusqu'à « au moins une masse terrestre ». Voir cette évolution sous ses yeux produit un effet que la simple lecture de l'exposant ne procure pas.
L'objection évidente est que personne n'énumérerait l'ensemble des n! ordres. Fixez la ville de départ et refusez de compter séparément une tournée et son image miroir, et le décompte est divisé par 2n. Faites-le : le point de bascule passe de trente-neuf villes à quarante et une. Voilà tout le gain apporté par l'ensemble du groupe de symétrie — deux villes.
Voilà ce que signifie concrètement l'affirmation « le parallélisme ne modifie pas la classe de complexité ». Le tube d'Adleman a permis un gain de vitesse d'environ 10¹⁴, ce qui est un nombre prodigieux, mais reste une constante. Une factorielle engloutit 10¹⁴ et réclame le plat suivant. Doubler le volume du tube ne fait gagner qu'une fraction de ville.
Le même mur, heurté de l'autre côté
La biologie est parvenue à cet argument la première et s'en est servie pour démontrer la thèse inverse.
En 1969, Cyrus Levinthal s'est demandé comment une protéine trouve sa forme. Prenez une chaîne de cent résidus et n'accordez à chaque jonction que trois orientations, ce qui est une sous-estimation flagrante. Cela donne 3¹⁰⁰, soit environ 5 × 10⁴⁷ conformations. Supposons que la chaîne en essaie une toutes les 10⁻¹³ secondes, ce qui correspond à peu près à une vibration moléculaire et à la vitesse maximale permise par la physique. Les explorer toutes prendrait 1,6 × 10²⁷ années : 10¹⁷ fois l'âge actuel de l'univers.
Les protéines se replient en quelques millisecondes.
Le paradoxe de Levinthal n'est pas une énigme sur la rapidité du repliement. C'est la preuve que le repliement n'est pas une recherche. Le paysage énergétique n'est pas une loterie plate de conformations, mais un entonnoir ; et une chaîne dans un entonnoir n'a jamais à choisir parmi 10⁴⁷ options. Elle tombe. Zwanzig, Szabo et Bagchi ont calculé en 1992 à quel point l'inclinaison nécessaire à cet entonnoir est faible. À partir d'un modèle simple, ils ont montré qu'un biais énergétique de l'ordre de quelques kT à l'encontre des configurations localement défavorables suffit à réduire le temps de Levinthal à une échelle biologiquement raisonnable. Non pas un algorithme astucieux. Une pente.
Faites varier le nombre de résidus et le nombre d'états par résidu dans le Levinthal Paradox Explorer, et observez avec quelle force ce nombre résiste à toute tentative de le rendre raisonnable. Réduire le nombre d'états par résidu de trois à deux fait gagner un facteur de 10¹⁷·⁶, et laisse encore une chaîne de cent résidus nécessiter une fraction substantielle de l'âge de l'univers. La base ne fait l'objet que d'un seul versement ; l'exposant, lui, facture à nouveau chaque résidu.
Mettez à présent les deux arguments côte à côte, car il s'agit de la même arithmétique. Une protéine ne peut pas énumérer ses conformations. Un tube à essai ne peut pas énumérer ses parcours. La réponse de la nature a été de renoncer à l'énumération pour bâtir un paysage en entonnoir. La réponse du calcul sur ADN a été d'énumérer plus intensément, en parallèle, avec davantage de molécules — ce qui est précisément la démarche que le dénombrement interdit.
Ce qui subsiste
Rien de tout cela ne fait du calcul moléculaire une impasse. Cela rend simplement son argumentaire trompeur, ce qui est très différent, et l'argumentaire honnête se révèle bien meilleur.
Commençons par l'énergie. Landauer a montré en 1961 qu'effacer un bit de manière irréversible doit dissiper au moins kT ln 2 : à la température du corps, 3,0 × 10⁻²¹ joules. C'est une limite inférieure fixée par la thermodynamique, non par la fabrication. Une seule hydrolyse d'ATP, la monnaie que dépense réellement la biologie, libère environ vingt kT : 8,6 × 10⁻²⁰ joules, soit 29 fois ce plancher. Une opération logique dans un bon circuit CMOS coûte près d'un femtojoule, ce qui représente 337,000 fois ce plancher.
événement moléculaire ≈ 29 × kT ln 2 · logique silicium ≈ 337,000 × kT ln 2
Quatre ordres de grandeur, et ils jouent en défaveur du silicium. Une cellule calcule lentement et pratiquement au minimum thermodynamique, à quelques dizaines de kT d'un plancher dont un transistor s'éloigne de plusieurs centaines de milliers de fois. Réglez la température et l'énergie par opération dans Energy per Operation, et cet écart devient difficile à ignorer.
Vient ensuite le stockage. Encodez les données dans les bases plutôt que dans les parcours, et la densité qui rendait la force brute absurde devient l'argument majeur : environ 3 × 10²⁰ octets par gramme. L'intégralité des films jamais sortis, dans un volume inférieur à celui d'un morceau de sucre, stable pendant des siècles dans l'obscurité et ne consommant aucune énergie au repos. DNA Data Storage intègre les surcoûts réels — indexation, sites de liaison des amorces, codes évitant les longues répétitions d'une même base — et la densité y résiste sans difficulté.
Ainsi, l'exponentielle qui condamne l'ADN en tant que moteur de recherche est la même qui en fait une archive extraordinaire. La recherche nécessite une molécule par candidat, et les candidats croissent de façon factorielle. L'archivage nécessite une molécule par donnée, et les données croissent de façon linéaire. Même chimie, même densité, verdicts opposés : la seule différence réside dans la grandeur dont on a exigé le changement d'échelle.
La structure de l'argument
Lorsque l'on vous propose un parallélisme massif, demandez-vous ce que ce parallélisme multiplie. Face à une exponentielle, la grandeur de la constante importe peu : 10¹⁴ et 10²³ sont un seul et même nombre quand l'adversaire est une factorielle. L'expérience d'Adleman était une démonstration magistralement exécutée d'un facteur constant, et la discipline l'a interprétée comme une pente.
Levinthal a mené le même décompte et en a tiré d'emblée la bonne conclusion, car il n'avait rien à vendre : si le dénombrement est impossible, c'est que le mécanisme n'est pas celui supposé. Ce qui subsiste une fois dissipé le récit de la recherche — une énergie quasi optimale par événement, une densité vertigineuse par gramme — constitue un jeu d'atouts remarquable, auquel nul n'aurait prêté un second regard tant que la recherche restait sur la table.