Systèmes de Head et applications à la bio-informatique

Tout est nombre. En reprenant cette ancienne idée pythagoricienne et en la recombinant avec le fait qu’un nombre est le résultat d’un calcul, nous pouvons reformuler la phrase ci-dessus en disant que tout est calcul. Nous pouvons retrouver des exemples de calcul dans de nombreux domaines, mais I’exemple le plus fascinant est celui de la vie. Il n’est pas facile de donner une définition exacte à ce phénomène complexe, mais à I’heure actuelle on suppose que I’ingrédient le plus important de la vie est I’acide désoxyribonucléique, I’ADN, qui est parfois remplacé par I’acide ribonucléique, ou ARN. En effet, tous les êtres vivants que I’on connaît possèdent cette molécule et la nature utilise des opérations simples de type copier, coller, insérer, effacer etc. pour Ia manipuler. On voit que I’on a besoin seulement de petites briques, I’ADN, et de règles simples pour exprimer certains aspects structuraux des êtres vivants et peut-être même la diversité de la nature. On peut remarquer un parallèle avec la théorie de la calculabilité, où on utilise aussi des éléments très simples pour construire des fonctions qui calculent des choses complexes. Cette analogie nous conduit à la réflexion que la nature calcule, mais peut-être d’une manière différente que nous ne comprenons pas encore complètement. Du chaos à la matière inorganique, de la matière morte à la matière vivante, de l’inconscient à I’intelligence, peut-être toute l’évolution de I’univers est elle une histoire de calculs qui deviennent de plus en plus compliqués. Tout cela paraît une spéculation métaphysique, mais, qui sait, peut-être notre conception actuelle des calculs est-elle liée à l’évolution de l’humanité, comme I’utilisation de la base dix pour compter est liée au fait que I’on a dix doigts. De même que les hommes ont commencé à utiliser d’autres bases pour compter, il est peut-être temps de trouver de nouvelles conceptions du calcul qui seront différentes de celles utilisées auparavant.

Un premier pas a été fait par L. Adleman en 1994 qui a montré pour la première fois comment il est possible d’utiliser ces nouvelles opérations et structures de données pour résoudre des problèmes concrets. Son expérience montre comment résoudre une instance du problème d’un chemin hamiltonien dans un graphe à I’aide de moyens biologiques uniquement. C’est incroyable, mais en utilisant des molécules d’ADN, des enzymes et d’autres substances chimiques et en manipulant des éprouvettes, il est possible de trouver une solution à un problème mathématique concret. L’expérience d’Adleman, publiée dans << Science >>, voir [1], a stimulé I’étude des nouveaux modèles de calcul fondés sur la biologie en provoquant une explosion d’articles liés à ce sujet. Divers aspects des mécanismes biologiques ont été étudiés d’un point de vue de la calculabilité et les résultats sont très prometteurs, car les modèles obtenus permettent, bien sûr thêoriquement, de dépasser la puissance de calcul des ordinateurs existants. La structure compacte des données, le parallélisme massif et la consommation modeste d’énergie, sont les atouts importants qui affirment la supériorité, au moins théorique, d’un ordinateur fondé sur des principes biologiques.

L’ADN n’est pas la seule source d’inspiration pour trouver de nouveaux paradigmes de calcul. Nous pouvons changer d’optique et nous placer au niveau cellulaire. En effet, la cellule vivante est une machine étonnante que la nature perfectionne de plus en plus. Tout est présent ici : la communication avec I’environnement, la reconnaissance des signaux, la recherche dans la base de données de I’ADN, la réaction, Ia production et Ia consommation d’énergie… En bref, la compréhension du comportement de la cellule est peut-être la clef qui nous permettra de comprendre les secrets de la vie. Mais, si on peut imaginer des calculs avec I’ADN, on peut aussi imaginer des calculs avec des cellules. Dans ce cas I’aspect structurel devient de plus en plus important, car Ia cellule peut être vue comme un ensemble de membranes imbriquées les unes dans les autres. Le premier modèle de calcul fondé sur la structure de la cellule et sur les processus cellulaires a été proposé en l-998 par Gh. Pàun qui est considéré comme père de ce domaine : le calcul à membranes. Depuis, plus d’une centaine de variantes ont été proposées et leur nombre croît constamment. Vu le niveau technologique actuel, il n’y a pas encore d’implantation pratique in vivo ou in vitro, mais comme nous I’avons dit auparavant, une des raisons pour lesquelles on étudie les modèles issus de la biologie est de trouver de nouvelles possibilités de calcul différentes de celles que nous avons utilisées jusqu’à présent.

L’expérience d’Adleman, voir [1], a lancé l’étude des différentes opération biologiques d’un point de vue de la calculabilité. Les opérations qu’il a utilisé : synthèse, amplification, séparation, extraction et détection, ainsi que des opérations similaires ont été reprises par des divers auteurs qui ont montré comment il est possible de résoudre plusieurs problèmes mathématiques à I’aide de ces opérations. Par exemple, des solutions polynomiales pour SAT, DES et d’autres problèmes ont été proposées, voir [19]. Une caractéristique importante de toutes ces opérations est qu’elles correspondent à de vraies opérations biologiques, par conséquent, il est possible de les implanter réellement. D’autre part, leur formalisation est difficile, car beaucoup de paramètres quantitatifs d’origine physique doivent être pris en compte. C’est pourquoi certains auteurs ont choisi une autre approche en formalisant des opérations biologiques, mais en idéalisant les contraintes d’origine physique. Les opérations obtenus, comme insertion, effacement, recombinaison etc. présentent de nombreux avantages théoriques, mais leur réalisation en pratique reste difficile. Nous remarquons que les deux approches sont intéressantes, mais nous nous concentrons surtout sur la deuxième. Plus précisément, nous étudions l’opération de la recombinaison et des divers systèmes fondés sur cette opération.