S’abonner – offre de Noël
Dans le monde vivant, les structures simples sont plus fréquemment observées que les structures plus complexes comportant les mêmes éléments. La théorie mathématique de la complexité explique pourquoi.
Comme la majorité des animaux, les abeilles présentent un plan de symétrie et des parties répétées. Et si l’abondance de structures relativement simples chez les organismes vivants était une conséquence de la nature algorithmique de l’évolution ?
En substance, dans sa plus simple expression, le mécanisme à la base de la théorie moderne de l’évolution s’apparente à un algorithme : des mutations génétiques apparaissent aléatoirement et produisent des variations des caractères des organismes vivants. La sélection naturelle agit alors sur ces variations en favorisant certains phénotypes (ensembles de caractères) par rapport à d’autres. On peut voir ce mécanisme comme un algorithme de type {génération par variations aléatoires} + {sélection} que rien ne dirige et qui produit les formes variées des organismes vivants. Or nous allons voir que cette vision algorithmique de l’évolution fournit à elle seule une explication d’une curiosité de la nature : la surreprésentation des structures simples dans le monde vivant.
Observez une voiture. Globalement, elle comporte un plan de symétrie, quatre roues identiques, une multitude de vis et d’écrous similaires, etc. Rien de surprenant : de façon générale, les objets techniques présentent presque toujours des symétries et des sous-parties répétées qui accroissent leur robustesse tout en facilitant leur fabrication et les modifications qu’on opère pour les perfectionner.
Ces régularités structurelles simplifient la description des objets : on parle de « faible complexité descriptive » – une propriété synonyme de concision : ainsi, en mathématiques, pour décrire la suite de mille termes 0101010101010…, au lieu d’écrire tous les termes, il suffit de la présenter comme « la suite composée de 500 fois 01 ». La recherche de cette concision tire parti des répétitions, des symétries ou des régularités récurrentes.
Plus étonnant en revanche, les structures biologiques comportent aussi de nombreuses symétries et sous-parties répétées : la majorité des animaux ont par exemple un plan approximatif de symétrie, et leurs cellules se regroupent en catégories comprenant chacune un grand nombre d’exemplaires quasi identiques.
On pourrait tenter d’expliquer ce parallèle par l’idée que la symétrie et la répétition de sous-structures résultent de la sélection naturelle. Cependant, l’évolution, contrairement aux ingénieurs, ne planifie pas les formes et structures qu’elle produit. Il faudrait donc supposer que ces traits offrent un avantage compétitif immédiat, ce qui n’est pas patent : selon la théorie moderne de l’évolution, la plupart des mutations sont « neutres », ce qui signifie qu’elles ne donnent pas prise à la sélection naturelle ! Aussi semble-t-il impossible de justifier la fréquence avec laquelle on observe la faible complexité descriptive en biologie par les avantages qu’elle procure. L’encadré ci-dessous propose un exemple où la fréquence observée des formes simples de protéines exige une explication particulière.
Or il se trouve que la conception de l’évolution comme un algorithme, associée à certains résultats de la théorie de la complexité, suggère une explication mathématique nouvelle du mystère. Divers chercheurs ont montré numériquement qu’il y a réellement surabondance, dans le monde vivant, des symétries et répétitions, et que cette explication non adaptative est nécessaire pour en rendre compte. En particulier, une équipe réunie autour de Iain Johnston, de l’université de Bergen, en Norvège, vient de publier un article où elle défend cette vision mathématique qui enrichit la théorie moderne de l’évolution. Elle y fait jouer un rôle inattendu à des explications théoriques d’un type nouveau. Le titre de l’article énonce clairement sa thèse : « Les symétries et la simplicité émergent spontanément de la nature algorithmique de l’évolution ».
Dit en termes simples, si la complexité descriptive faible apparaît préférentiellement chez les organismes vivants, ce n’est pas seulement en raison de la sélection naturelle, mais aussi parce que les structures exigeant moins d’informations pour être décrites sont plus susceptibles d’apparaître comme variation phénotypique quand se produisent des mutations aléatoires.
Le point principal de cette thèse repose sur la théorie algorithmique de l’information, ou théorie de la complexité de Kolmogorov, et sur un de ses résultats les plus profonds : le théorème du codage de Leonid Levin.
La théorie algorithmique de l’information est née dans les années 1960 des travaux de Ray Solomonoff, Andrei Kolmogorov, Gregory Chaitin et Leonid Levin. On y mesure la complexité – dénommée alors « complexité de Kolmogorov » – d’un objet numérique Ob, par exemple une image, par la taille en nombre de caractères du plus petit programme qui l’engendre. Le programme le plus court joue le rôle d’un codage optimal pour Ob. Une image toute blanche a une faible complexité, car un programme très court peut l’engendrer. L’image d’un arbre avec un grand nombre de branches et de feuilles, ou la photo d’une ville vue d’avion auront une complexité plus grande. Les objets les plus complexes sont ceux engendrés par le hasard, par exemple un million de pixels noirs ou blancs produits par un tirage à pile ou face avec une pièce de monnaie. Cette complexité de Kolmogorov est la version mathématique du concept un peu vague de complexité descriptive.
L’idée de produire des objets numériques par des programmes tirés au hasard a conduit Leonid Levin à découvrir et démontrer un résultat étonnant et profond : la probabilité qu’un objet numérique soit produit par un programme tiré au hasard, dénommée « probabilité algorithmique », est inversement liée à sa complexité de Kolmogorov : plus la complexité d’un objet numérique est grande, plus est petite la probabilité de voir cet objet produit par un programme choisi au hasard.
En mettant en valeur la probabilité algorithmique (parfois dénommée « distribution de Levin »), les récents résultats sur l’importance du biais en faveur de la simplicité confirment l’idée que cette probabilité qualifiée de miraculeuse doit être envisagée quand on cherche à modéliser des tirages aléatoires de la manière la plus neutre possible. Bien sûr, la probabilité uniforme est ce qui convient le plus souvent, par exemple pour attribuer des probabilités aux faces d’un dé. Cependant, lorsque des processus de calcul sont concernés, par exemple si on considère les suites de bits présents dans une mémoire informatique, alors la probabilité algorithmique sera mieux adaptée (consulter dans la bibliographie l’article de 2011 d’Hector Zenil et son récent livre). Dans un monde où le calcul prend de plus en plus d’importance, il est certain que la probabilité algorithmique verra son rôle s’accroître.
La formule liant la complexité de Kolmogorov d’un objet Ob, notée K(Ob), et sa probabilité algorithmique, notée Pr(Ob), est donnée par le théorème du codage de Léonid Levin : Pr(Ob) ≈ 1/2K(Ob).
Des vérifications expérimentales de ce résultat sont possibles et nous allons en présenter une pour montrer les conséquences de ce lien entre complexité et probabilité. Nous verrons aussi que cette vérification rend envisageable de faire intervenir le théorème du codage de Leonid Levin en biologie pour expliquer le biais constaté en faveur des faibles complexités descriptives.
Les plus élémentaires des programmes sont ceux qui font fonctionner les machines de Turing, le modèle théorique d’ordinateur proposé par le mathématicien britannique Alan Turing en 1936. Ces programmes peuvent ne comporter que quelques instructions et malgré tout engendrer des objets intéressants. Surtout, on peut énumérer en totalité les plus simples des programmes pour machines de Turing, les faire tous fonctionner et, en analysant la distribution statistique des objets numériques produits, avoir une idée de la probabilité Pr(Ob) des objets les plus simples.
Les programmes pour machines de Turing à cinq états (le nombre d’états est une caractéristique de ces machines) et utilisant les deux symboles 0 et 1 pour calculer et écrire leurs résultats sont très nombreux. On en dénombre environ 26 000 milliards et, en exploitant des symétries entre certains programmes, on connaît la totalité des résultats qu’ils produisent en ne faisant fonctionner que 9 000 milliards d’entre eux. Dans ce but, en 2013, Fernando Soler Toscano, au centre d’informatique scientifique d’Andalousie, a mené un gigantesque calcul durant dix-huit jours. La distribution de probabilité obtenue a permis de classer 99 608 suites finies de 0 et de 1 par probabilité décroissante. Comme le théorème du codage l’indiquait, les suites de 0 et de 1 les plus fréquemment produites par les machines de Turing considérées sont les plus régulières. Par exemple, les suites de longueur 7 par ordre de fréquences décroissantes dans les résultats de l’immense calcul sont 0000000 et 1111111 à égalité, suivies de 0111111, 1000000, 1111110 et 0000001 à égalité, suivies de 0101010 et 1010101 à égalité (une liste plus complète est proposée dans l’encadré ci-dessous). Plus une suite est simple, plus fréquemment elle résulte du calcul d’une machine de Turing.
Si on accepte de modéliser l’évolution biologique comme un algorithme qui engendre des séquences au hasard, les génotypes, lesquels se traduisent ensuite en formes réelles, les phénotypes, par un procédé de traduction assimilable à l’exécution d’un calcul, alors on se retrouve exactement dans la situation que décrit le théorème du codage mis à l’épreuve dans le calcul avec les milliers de milliards de machines de Turing. En conséquence, les génotypes conduiront plus fréquemment à des phénotypes plus simples. Et cela avant même qu’opère la sélection naturelle.
En effet, les formes produites par le hasard de l’évolution dans la phase {génération par variations aléatoires} de l’algorithme sont soumises à un processus de sélection qui ne retient que celles les mieux adaptées ou coadaptées. Cependant, si au départ ce qui produit ces formes favorise les plus simples (de faible complexité descriptive), alors il faut s’attendre à ce qu’une fois la sélection opérée ce qu’on observe montre encore un biais en faveur des faibles complexités. La préférence observée dans les structures des organismes vivants pour les formes simples n’est alors plus une surprise mais ce à quoi il faut s’attendre indépendamment de toute autre considération.
Il est délicat d’affirmer que le biais en faveur des structures à faible complexité provient uniquement du théorème du codage, car les avantages des structures simples sur les structures complexes sont aussi susceptibles de les favoriser dans la phase de sélection. Cependant l’effet du théorème du codage ne doit pas être oublié, car il intervient au cœur du mécanisme de l’évolution biologique.
L’idée que des programmes ou algorithmes choisis au hasard engendrent plus fréquemment des structures simples que des structures complexes n’est, à bien y réfléchir, pas contraire à l’intuition. Pour la comprendre et amener à la juger naturelle, on utilise parfois l’image de singes tapant au hasard sur des machines à écrire. On distingue la version (a) où les singes tapent simplement des textes, et la version (b) où les singes tapent des programmes qui ensuite produisent des textes.
Dans la version (a), obtenir que le texte engendré soit les mille premiers caractères du début du roman Les Misérables, de Victor Hugo, a la même très faible probabilité qu’obtenir mille fois 0, et c’est la même probabilité pour tout texte de mille caractères.
En revanche, on comprend que dans la version (b), le texte de mille fois 0 sera produit avec une plus grande fréquence, car il y a un grand nombre de programmes courts qui produisent mille 0 et l’on peut artificiellement les allonger jusqu’à mille caractères sans que cela change leur résultat (on peut toujours allonger un programme en lui ajoutant des lignes qui ne seront pas exécutées). En considérant tous les programmes de mille caractères écrits au hasard par les singes, on aura donc un plus grand nombre de fois le résultat mille fois 0 que le début des Misérables. Ce qui est simple est plus souvent produit par des singes tapant des programmes au hasard que ce qui est complexe.
On peut juger simpliste d’assimiler la transformation génotype-phénotype à une transformation programme-résultat. Et en effet, si l’on veut appliquer le théorème du codage à des systèmes biologiques, il est souhaitable de disposer de versions du résultat de Leonid Levin étendues à des situations plus proches du monde réel, qui ne remplissent donc pas exactement toutes les conditions requises par la théorie algorithmique de l’information. C’est le cas maintenant grâce aux trois chercheurs Kamaludin Dingle, Chico Camargo et Louis Ard, qui, en 2018, ont construit une telle version et montré que, bien qu’elle soit moins restrictive que le théorème du codage d’origine, elle décrit aussi un biais de simplicité dans des situations aussi variées que la génération d’une matrice circulante aléatoire, un modèle financier ou la production de molécules d’ARN structurées tridimensionnellement à partir de leur séquence. Ces nouvelles formes du résultat de Leonid Levin renforcent le bien-fondé de la théorie de la complexité de Kolmogorov pour décrire des versions abstraites de l’évolution biologique, et donc l’intérêt de l’explication qu’elle fournit du biais de simplicité.
Pour bien comprendre le biais en faveur de la simplicité, interrogeons-nous sur ce qu’est un hasard neutre : le théorème du codage de Leonid Levin nous invite à revoir cette notion.
Quand on ne sait pas comment est opéré un choix au hasard, l’hypothèse par défaut qui semble s’imposer est celle du hasard uniforme. C’est ainsi que si l’on parle d’une séquence génétique de longueur n, prise au hasard, l’idée qui vient à l’esprit en l’absence de précisions complémentaires est de considérer que la séquence génétique est l’une de 4n séquences possibles de longueur n, chacune ayant la même probabilité d’être trouvée : 1/4n (une séquence génétique est une suite de « lettres » prises parmi quatre : A, T, G, C). De même, si l’on imagine une suite de n bits consécutifs lue dans la mémoire d’un ordinateur, on sera tenté de considérer qu’elle est l’une des 2n suites possibles de n fois 0 ou 1, chacune ayant la même probabilité d’être retenue : 1/2n.
Dans le cas de structures topologiques de molécules (comme dans le premier encadré ci-dessus) ou de formes plus complexes on cherchera à les énumérer d’une façon aussi uniforme que possible et on attribuera la probabilité 1/k de tomber sur l’une, où k est le nombre d’objets énumérés. En clair, en l’absence d’information, l’attitude qui semble la plus neutre est celle consistant à adopter la probabilité uniforme.
Ce que nous venons de voir et qui est au cœur de l’explication du biais en faveur de la simplicité dans l’évolution est que dans certaines situations, il est souhaitable d’adopter un autre point de vue. Si les k objets auxquels on veut attribuer une probabilité sont le résultat d’un processus assimilable à une forme de calcul, alors il vaut mieux considérer que la probabilité de chaque objet n’est pas uniformément 1/k, mais plus ou moins proportionnelle à Pr(Ob) ≈ 1/2K(Ob), et donc dépend de l’objet Ob. Dans le cas d’une suite de bits prise dans la mémoire d’un ordinateur, il est évident que la suite de bits provient beaucoup plus de résultats de calculs que de choix aléatoires faits par un tirage uniforme à pile ou face. Il est clair alors qu’on risquera moins de se tromper avec la probabilité algorithmique qu’avec la probabilité uniforme.
Pour les séquences génétiques, il est sans doute vrai aussi que la probabilité uniforme n’est pas le choix le plus judicieux. Divers expérimentations et calculs dont ceux menés par Hector Zenil en 2011 (cf la bibliographie) confirment ce point de vue : adopter une conception aussi neutre que possible doit parfois conduire à penser à la probabilité algorithmique plutôt qu’à la probabilité uniforme.
En 2018, Santiago Hernández-Orozco, Narsis Kiani et Hector Zenil ont poussé l’idée encore un peu plus loin. Ils se sont demandé ce qui changerait si on considérait que les mutations aléatoires qu’on évoque quand on modélise l’évolution biologique suivent non pas une probabilité uniforme (ce qu’on suppose souvent sans le préciser), mais la probabilité algorithmique. Leurs résultats en opérant cette substitution dans leurs expériences confirment des résultats préliminaires de Gregory Chaitin et montrent en particulier un accroissement de la vitesse d’évolution.
Les chercheurs résument leurs travaux : « L’usage de la probabilité algorithmique peut faire évoluer la modularité et la mémoire génétique en favorisant la préservation des structures lorsqu’elles apparaissent pour la première fois. Cela conduit parfois à une production accélérée de diversité, mais aussi à des extinctions de population. Ce serait peut-être un élément d’explication pour des phénomènes naturels tels que les explosions de diversité (par exemple au Cambrien) et les extinctions massives (par exemple à la fin du Trias) dont les causes sont objet de débats. L’approche introduite semble produire une meilleure approximation de l’évolution biologique que les modèles fondés exclusivement sur des mutations uniformes aléatoires. […] Ces résultats valident certaines suggestions appuyant l’idée que le calcul pourrait être un moteur important de l’évolution. »
Bien sûr les explications algorithmiques du biais en faveur de la simplicité ou les modèles de l’évolution à base de probabilités algorithmiques ne sont pas acceptés unanimement par les biologistes, et il faudra sans doute un long moment pour les voir entrer de manière définitive dans le champ de la théorie de l’évolution… si ces travaux, somme toute assez spéculatifs, se voient confirmés par les études, les calculs et les observations futures.
Trouver les théories mathématiques pertinentes pour la biologie se révèle finalement bien plus difficile que pour la physique, même s’il ne semble cependant guère faire de doute que la théorie du calcul et la théorie algorithmique de l’information sont de bons candidats pour tenir ces rôles.
Nombre de comportements inconscients ont été façonnés par la sélection naturelle, par gradations, indépendamment les uns des autres le plus souvent, pendant des millions d’années. Et aujourd’hui, ils se heurtent à la modernité du monde.
Des chercheurs ont utilisé des algorithmes d’apprentissage profond pour identifier des séquences génétiques modelées par la pression de sélection évolutive.
Molécules, cellules, organismes, sociétés, aucun élément biologique n’agit seul, tous interagissent. L’affirmation paraît banale, mais, développée, elle invite à élargir notre vision de l’évolution. Telle est la thèse qu’Éric Bapteste défend dans son dernier livre, Tous entrelacés !
En simulant une forêt soumise à la sélection naturelle, des chercheurs en physique, en biomécanique et en écophysiologie végétale ont mis en évidence le rôle crucial de la compétition pour l’accès à la lumière et la résistance au vent dans l’évolution de la structure des arbres.
Une nouvelle technique pour mesurer la complexité d’une suite de chiffres a permis de montrer que réussir à produire une suite aléatoire complexe reflète les performances cognitives du cerveau.
Les notions de complexité et de compression de l’information nous dévoilent une partie des mécanismes de l’humour.
Jean-Paul Delahaye est professeur émérite à l'Université de Lille et chercheur au centre de recherche en informatique, signal et automatique de Lille (CRISTAL). Il est l'auteur de la rubrique Logique et calcul dans Pour la Science et du blog Complexités.
I. Johnston, et al., Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution, PNAS, 2022.
H. Zenil et al., Methods and Applications of Algorithmic Complexity : Beyond Statistical Lossless Compression, Springer Nature, 2022.
K. Dingle et al., Generic predictions of output probability based on complexities of inputs and outputs, Scientific reports, 2020.
K. Dingle et al., Input-output maps are strongly biased towards simple outputs, Nature Communication, 2018.
S. Hernández-Orozco et al., Algorithmically probable mutations reproduce aspects of evolution, such as convergence rate, genetic memory and modularity, R. Soc. open sci., 2018.
F. Soler Toscano et al., Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines, Plos One, 2014.
H. Zenil et J.-P. Delahaye, On the algorithmic nature of the world, dans G. Dodig-Crnkovic et M. Burgin, Information and Computation : Essays on Scientific and Philosophical Understanding of Foundations of Information and Computation, World Scientific, 2011.
W. Kirchherr et al., The miraculous universal distribution, The Mathematical Intelligencer, 1997.
– Suivez l'actualité des découvertes scientifiques
– Découvrez les réponses de la science aux grandes questions d'aujourd'hui, expliquées par les meilleurs spécialistes dans chaque domaine
– Explorez les archives de Pour la Science depuis 1996.
– Accédez à tous les articles réservés aux abonnés sur le site www.pourlascience.fr
Je m'abonne
Retrouvez nous sur les réseaux sociaux :
170 bis Boulevard du Montparnasse, 75014 Paris 06
N° CPPAP : 0922 W 91526