Comme exemple de graphe orienté, Adleman propose celui-ci, à 7 sommets (numérotés de 0 à 6) :
On peut représenter ce graphe ainsi, en Python :
from graphviz import Digraph dg = [[1,3,6],[2,3],[1,3],[2,4],[1,5],[2,6],[]] G = Digraph(format='svg') for n in range(7): G.node(str(n),shape='circle',style='filled') for i in range(len(dg)): for j in dg[i]: G.edge(str(i),str(j),color='brown')
Généralement, un tableau associatif est plus adapté, mais comme Adleman a choisi de nommer les sommets du graphe par des entiers consécutifs, cela permet de prendre un tableau (indexé par les numéros des sommets) de listes d'adjacence.
Adleman choisit (pour les besoins de son algorithme) de représenter le graphe comme une collection de couples, comme ceci :
aretes = [(0, 1), (0, 3), (0, 6), \ (1, 2), (1, 3), (2, 1), (2, 3), \ (3, 2), (3, 4), (4, 1), (4, 5), \ (5, 2), (5, 6)]
Un chemin est une suite d'arêtes du graphe (donc de couples de sommets) telle que chaque arête a pour origine l'extrémité de l'arête suivante.
On ne cherche pas que des chemins dans le graphe d'Adleman, mais on veut des chemins partant du sommet 0 (on ne peut y aller par la suite) et aboutissant au sommet 6 (on ne peut plus en partir).
Un chemin est hamiltonien si
2345
est un chemin mais ne part pas de 0).032345
ne finit pas en 6).06
ne passe pas par 1).01213234523456
passe plusieurs fois par le sommet 2).La recherche d'un chemin hamiltonien dans un graphe est un problème NP complet donc réputé difficile. Len Adleman propose alors cet algorithme aléatoire :
On se propose de simuler ces étapes en Python, mais ce n'est pas le langage choisi par Adleman (voir plus bas).
Comme Adleman a choisi de représenter chaque
arête par un couple, il s'agit de relier entre elles
deux arêtes si l'une commence là où finit la
précédente. La méthode edge
de l'objet
Digraph()
permet cela. On rappelle
que si t
est un couple, son premier
élément (origine) est t[0]
et son
second élément (extrémité) est t[1]
.
from random import choice aretes = [(0, 1), (0, 3), (0, 6), \ (1, 2), (1, 3), (2, 1), (2, 3), \ (3, 2), (3, 4), (4, 1), (4, 5), \ (5, 2), (5, 6)] g = Digraph(format='svg',engine='neato',strict=True) for n in range(20): arete = choice(aretes) g.edge(str(arete[0]),str(arete[1]))
Bien entendu, un chemin obtenu en accouplant au hasard des arêtes n'est pas nécessairement hamiltonien :
Le graphe ci-dessus n'est d'ailleurs même pas un chemin.
On revient à la représentation du graphe par listes d'adjacences. On effectue alors un parcours du graphe à partir de 0, et on s'arrête lorsqu'on a atteint 6 :
from random import * dg = [[1,3,6],[2,3],[1,3],[2,4],[1,5],[2,6],[]] def ok1(): s = '0' t = 'x' while t is not '6': t = s[-1] vs = dg[int(t)] if len(vs): n = choice(vs) s += str(n) return s
En répétant de nombreuses fois la génération d'un chemin au hasard (mais allant de 0 à 6), on obtient une sorte de spectre en effectuant une étude statistique sur les longueurs des chemins construits :
On constate que même s'il y a relativement peu de chemins de longueur 7, il y en a, ce qui laisse la possibilité de l'existence d'un chemin hamiltonien.
On répète l'expérience d'engendrer un chemin aléatoire
allant de 0 à 6 avec la fonction ok1()
jusqu'à ce que la longueur du chemin soit 7 :
def ok2(): path = '' while len(path) != len(dg): path = ok1() return path
On effectue un dernier filtrage. En transformant
(avec la fonction set
) la liste des
sommets parcourus, on ne garde qu'une fois chacun,
car un ensemble (set en anglais) ne contient
qu'une seule fois chacun de ses éléments. Alors
len(set(list(path)))
donne le nombre de
sommets visités. Ce nombre doit être égal à 7 :
def ok3(): path='' while len(set(list(path))) != len(dg): path = ok2() return path
Le simple fait qu'il y ait une sortie, prouve l'existence
d'un chemin hamiltonien. Ici on n'en trouve
qu'un : 0123456
.
Adleman dispose d'un synthétiseur à ADN lui permettant de représenter des chaînes de caractères écrites dans l'alphabet {A,C,G,T}. Chaque sommet du graphe est associé à une chaîne de 20 caractères pris au hasard parmi A, C, G et T. Cela rend négligeable le risque que deux sommets soient associés à la même chaîne de caractères (ou molécule d'ADN).
De plus, chaque chaîne de caractère est obtenue par concaténation de deux chaînes aléatoires de longueur 10. Par exemple les sommets 2, 3 et 4 sont associés à ces chaînes :
TATCGGATCGGTATATCCGA GCTATTCGAGCTTAAAGCTA GGCTAGGTACCAGCATGCTT
calculées à partir de
from Bio.Seq import * o2 = Seq('TATCGGATCG'+'GTATATCCGA') o3 = Seq('GCTATTCGAG'+'CTTAAAGCTA') o4 = Seq('GGCTAGGTAC'+'CAGCATGCTT')
Adleman code chaque arête par concaténation entre
Les arêtes 2→3, 3→2 et 3→4 sont codées ainsi :
from Bio.Seq import * o23 = Seq('GTATATCCGA'+'GCTATTCGAG') o32 = Seq('CTTAAAGCTA'+'TATCGGATCG') o34 = Seq('CTTAAAGCTA'+'GGCTAGGTAC')
On constate (comparaison entre les deux premières lignes) que le graphe est orienté, puisque les arêtes (ou arcs puisque le graphe est orienté) 2→3 et 3→2 ne sont pas représentés de la même manière.
GTATATCCGAGCTATTCGAG CTTAAAGCTATATCGGATCG CTTAAAGCTAGGCTAGGTAC
En fait, les sommets ne sont pas représentés par les chaînes auxquelles ils sont associés, mais à leur complément. Le complément d'une chaîne s'obtient en échangeant les lettres A et T, ainsi que les lettres C et G (cela correspond à un procédé cryptographique appelé atbash par référence au début et à la fin de l'alphabet ; en effet on inverse les positions alphabétique des lettres).
print(o3) print('|'*20) print(o3.complement())
L'intérêt du complément est qu'il permet des liaisons chimiques fortes entre les molécules :
GCTATTCGAGCTTAAAGCTA |||||||||||||||||||| CGATAAGCTCGAATTTCGAT
Des molécules telles que décrites ci-dessus sont construites en grande quantité dans un synthétiseur à ADN🧬, puis mélangées dans une éprouvette 🧪. C'est le mélange qui introduit du hasard. Par exemple la molécule qui représente le sommet 3 (le complément) s'associe facilement à celle qui représente l'arête 2→3.
print(o23) print(' '*10+'|'*10) print(' '*10+o3.complement())
GTATATCCGAGCTATTCGAG |||||||||| CGATAAGCTCGAATTTCGAT
Mais elle s'associe aussi à la molécule représentant l'arête 3→4 :
print(' '*10+o34) print(' '*10+'|'*10) print(o3.complement())
CTTAAAGCTAGGCTAGGTAC |||||||||| CGATAAGCTCGAATTTCGAT
Comme elle ne s'attache pas à ces deux molécules par le même bout, les deux réactions chimiques sont parfaitement compatibles :
print(o23+o34) print(' '*10+'|'*20) print(' '*10+o3.complement())
GTATATCCGAGCTATTCGAGCTTAAAGCTAGGCTAGGTAC |||||||||||||||||||| CGATAAGCTCGAATTTCGAT
Cette nouvelle molécule produite représente la concaténation des arêtes 2→3 et 3→4 par leur sommet commun 3, donc le chemin 2→3→4. La réaction chimique se poursuivant durant plusieurs heures⏳, le chemin peut s'allonger considérablement et la soupe d'ADN qui se crée dans l'éprouvette contient, comme souhaité, une grande quantité de chemins, qu'il ne reste plus qu'à trier pour voir s'il y en a un qui est hamiltonien.
Adleman réalise une amplification PCR en mettant les représentants du sommet 0 et du sommet 6 comme amorce. Ne seront alors amplifiées 💧 que les molécules d'ADN représentant des chemins allant du sommet 0 au sommet 6.
Comme chaque paire A-T ou C-G a la même masse, en bio-informatique, les longueurs 📏 se pèsent ⚖️. Comme Adleman a choisi de représenter chaque sommet par une chaîne de 20 caractères, les chemins recherchés pèsent 140 fois plus qu'une paire de bases. Une électrophorèse permet de séparer géométriquement les molécules selon leur masse, et donc d'isoler les chemins de longueur 7.
On commence par séparer les molécules d'ADN restant après l'étape précédente (et amplifiées à nouveau par PCR)
CGATAAGCTCGAATTTCGAT
qui représente le sommet 3, comme on l'a vu plus
haut.GGCTAGGTACCAGCATGCTT
qui représente le sommet 4.Les molécules restant représentent les chemins hamiltoniens recherchés. Pour connaître un chemin, on peut effectuer un séquençage ADN ou des tests PCR sur des morceaux (qui révèlent que dans les chemins trouvés, le sommet 1 vient juste après le sommet 0 etc).
La technologie utilisée par Adleman est très présente dans les sciences forensiques, mais c'est la Covid-19 qui les a fait connaître :
Et si on synthétisait de l'ADN (ou de l'ARN) dans le but de faire des calculs massivement parallèles ? Et si on s'en servait pour résoudre des problèmes complexes comme 3-SAT ou la recherche d'un chemin hamiltonien ? Et si ensuite on injectait cet ARN de synthèse pour que le calcul, sous forme de réaction chimique, se faisait dans le corps des cobayes ? Et si pour mener le calcul, on prenait des cobayes humains ?
Impossible ! Il faudrait pour cela
Cela est inimaginable à l'heure actuelle.😜