Recherche de motifs exacts

Julien Velcin

dans le cadre du DIU EIL (2019-2020)

Implémentation personnelle des algorithmes naïfs et des deux heuristiques de l'algorithme de Boyer-Moore.

Algorithme naïf

In [19]:
T = "GCATCGCAGAGAGTATACAGTACG"
#T = "GCATCGCAGAGATATACAGTACG"
M = "GCAGAGAG"
#M = "CCGGTGAA"
#M = "TATATA"
#T = "AAAAAAAAAAAAAAAAAAAA"
#M = "AAAAAA"
#T = "AAAAAAAAAAAAAAAAAAAA"
#M = "ACGT"
#M = "ACGCA"
#T = "CBABABA"
#M = "ABABA"

n = len(T)
m = len(M)

Première implémentation avec des boucles for (pas le plus propre).

In [20]:
for i in range(n-m+1):
    for j in range(m):
        if T[i+j] != M[j]: # on s'arrête dès qu'on voit une différence (mismatch)
            break
        if (j == (m-1)): # critère d'arrêt à (j == (m-1)) car j n'est pas incrémenté à la fin
            print("motif trouvé en " + str(i))

motif trouvé en 5

Seconde implémentation avec des boucles while (mieux). En plus, on tient un compte du nombre total de comparaisons effectuées.

In [21]:
nb_comp = 0 # nombre total de comparaisons
i = 0
while (i <= (n-m)):
    j = 0
    while (j < m) and (T[i+j] == M[j]): # on incrémente tant que c'est identique
        nb_comp += 1
        j = j + 1
    if (j == m): # on remarque que le critère d'arrêt est (j == m) ici
        print("motif trouvé en " + str(i))
    else:
        nb_comp += 1 # pour ne pas oublier de compter les échecs de comparaison (mismatch)
    i = i + 1
print("Nombre total de comparaisons : " + str(nb_comp))

motif trouvé en 5
Nombre total de comparaisons : 30

Heuristique du Mauvais Caractère (MC)

In [22]:
symboles = ["A", "C", "G", "T"] # c'est l'alphabet
    
# calcul préalable de MC
MC = {}
for s in symboles: # on initialise à m par défaut (caractère introuvable dans le motif)
    MC[s] = m
for i in range(m-1): 
    MC[M[i]] = m-i-1
In [23]:
MC
Out[23]:
{'A': 1, 'C': 6, 'G': 2, 'T': 8}
In [24]:
import numpy as np

nb_comp = 0 # nombre total de comparaisons
i = 0
while (i <= (n-m)):
    print("Position : " + str(i))    
    j = m - 1 # on commence par la fin du motif
    while (j >= 0) and (T[i+j] == M[j]): # on incrémente tant que c'est identique
        #print("comp de " + str(i+j) + " et " + str(j))
        nb_comp += 1
        j = j - 1
    if (j >= 0):
        nb_comp += 1
        i = i + np.max([1, MC[T[i+j]] + j - m + 1])
    else: # on remarque que le critère d'arrêt est à présent (j < 0)
        print("motif trouvé en " + str(i))
        i = i + 1
        
print("Nombre total de comparaisons : " + str(nb_comp))

Position : 0
Position : 1
Position : 5
motif trouvé en 5
Position : 6
Position : 14
Position : 15
Nombre total de comparaisons : 15

Heuristique du Bon Suffixe (BS)

In [25]:
# calcul préalable de BS
# (attention, il s'agit probablement de l'implémentation la moins efficace
# mais peut-être la plus claire)

# calcul du plus grand préfixe qui est également suffixe (mais pas M tout entier)
pref_suff = m
for i in range(m-1):
    # on vérifie que la fin (entre m-(i+1) et m est identique au début (entre 0 et i+1)
    if M[0:i+1] == M[m-(i+1):m]:
        pref_suff = m-(i+1)
    
BS = [pref_suff] * m
BS[m-1] = 1 # cas particulier pour le dernier symbole de M
# recherche du prochain motif le plus à droite
i = m - 2
while (i >= 0):
    # motif à rechercher
    MM = M[i+1:m]
    l_MM = len(MM)
    k = i
    # on cherche le motif "à rebours"
    while (k>=0):
        if (M[k:k+l_MM] == MM) and ((k==0) or (M[k-1]!=M[i])):
            print("à l'index " + str(i) + " : sous-motif " + MM + " trouvé en " + str(k))
            BS[i] = i - k + 1
            break;
        k = k - 1
    i = i - 1

à l'index 6 : sous-motif G trouvé en 0
à l'index 5 : sous-motif AG trouvé en 2
à l'index 3 : sous-motif AGAG trouvé en 2
In [26]:
BS
Out[26]:
[7, 7, 7, 2, 7, 4, 7, 1]
In [27]:
import numpy as np

nb_comp = 0 # nombre total de comparaisons
i = 0
while (i <= (n-m)):
    print("Position : " + str(i))
    j = m - 1 # on commence par la fin du motif
    while (j >= 0) and (T[i+j] == M[j]): # on incrémente tant que c'est identique
        nb_comp += 1
        j = j - 1
    if (j >= 0):
        nb_comp += 1        
        i = i + BS[j]
    else:
        print("motif trouvé en " + str(i))
        i = i + BS[0]

print("Nombre total de comparaisons : " + str(nb_comp))

Position : 0
Position : 1
Position : 5
motif trouvé en 5
Position : 12
Position : 16
Nombre total de comparaisons : 17

Boyer-Moore : mettre tout ça ensemble

In [28]:
import numpy as np

nb_comp = 0 # nombre total de comparaisons
i = 0
while (i <= (n-m)):
    print("Position : " + str(i))
    j = m - 1 # on commence par la fin du motif
    while (j >= 0) and (T[i+j] == M[j]): # on incrémente tant que c'est identique
        nb_comp += 1
        j = j - 1
    if (j >= 0):
        nb_comp += 1 
        i = i + np.max([BS[j], MC[T[i+j]] + j - m + 1])        
    else: 
        print("motif trouvé en " + str(i))
        i = i + BS[0]
print("Nombre total de comparaisons : " + str(nb_comp))

Position : 0
Position : 1
Position : 5
motif trouvé en 5
Position : 12
Position : 16
Nombre total de comparaisons : 17
In [ ]: