📜Chemin hamiltonien dans un graphe orienté⚗️

I/ position du problème

1) Graphe d'Adleman

Comme exemple de graphe orienté, Adleman propose celui-ci, à 7 sommets (numérotés de 0 à 6) :

%3 0 0 1 1 0->1 3 3 0->3 6 6 0->6 2 2 1->2 1->3 2->1 2->3 3->2 4 4 3->4 4->1 5 5 4->5 5->2 5->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.

2) Définitions

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)]

a) Chemin

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.

b) Départ et arrivée

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).

c) Chemin hamiltonien

Un chemin est hamiltonien si

II/ Algorithme de recherche d'un chemin hamiltonien

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 :

  1. On engendre des chemins aléatoires dans le graphe.
  2. On ne garde que les chemins commençant par 0 et finissant par 6.
  3. Parmi ceux-ci, on ne garde que les chemins de longueur 7 (nombre de sommets du graphe).
  4. Parmi ceux-ci, on ne garde que les chemins contenant tous les sommets du graphe.

On se propose de simuler ces étapes en Python, mais ce n'est pas le langage choisi par Adleman (voir plus bas).

1) Génération de chemins

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 :

%3 3 3 2 2 3->2 2->3 1 1 2->1 1->3 1->2 0 0 0->3 0->1 6 6 0->6 5 5 5->6 4 4 4->5

Le graphe ci-dessus n'est d'ailleurs même pas un chemin.

2) Chemins d'un sommet à un autre

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 :

2567891011121314151617181920

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.

3) Chemins de la bonne longueur

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

4) Chemins passant par tous les sommets

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.

III/ Réalisation biochimique de l'algorithme

1) Chaînes de caractères

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).

a) Sommets du graphe

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')

b) Arêtes du graphe

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

c) Complément d'une chaîne

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

2) Mise en œuvre de l'algorithme

a) Étape 1 : création de chemins

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.

b) Étape 2 : choix des sommets initial et final

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.

c) Étape 3 : sélection par longueur

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.

d) Étape 4 : sélection des chemins hamiltoniens

On commence par séparer les molécules d'ADN restant après l'étape précédente (et amplifiées à nouveau par PCR)

  1. On effectue une amplification PCR avec comme amorce la chaîne représentant le sommet 1 : ne restent alors que des chemins passant effectivement par le sommet 1.
  2. On sélectionne ces chemins puis on effectue sur la sélection, une nouvelle amplification PCR, mais avec la molécule représentant le sommet 2 comme amorce.
  3. On sélectionne les molécules obtenues ainsi (et qui représentent les chemins passant par les sommets 1 et 2) puis on les amplifie avec un test PCR amorcé par CGATAAGCTCGAATTTCGAT qui représente le sommet 3, comme on l'a vu plus haut.
  4. On effectue sur la sélection précédente, un test PCR amorcé sur le complément de GGCTAGGTACCAGCATGCTT qui représente le sommet 4.
  5. On sélectionne les molécules restantes (qui représentent des chemins passant par les sommets 1, 2, 3 et 4) et on effectue un dernier test PCR, amorcé par le représentant du sommet 5.

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).

3) Science-fiction ?

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.😜