DM

Autour du séquençage du génome

Dans ce sujet, on s’intéresse à la recherche d’un motif dans une molécule d’ADN.

Une molécule d’ADN est constituée de deux brins complémentaires, qui sont un long enchaînement de nucléotides de quatre types différents désignés par les lettres A, T, C et G. Les deux brins sont complémentaires : "en face" d’un ’A’, il y a toujours un ’T’ et "en face" d’un ’C’, il y a toujours un ’G’. Pour simplifier le sujet, on va considérer qu’une molécule d’ADN est une chaîne de caractères sur l’alphabet {A,C,G,T} (on s’intéresse donc seulement à un des deux brins). On parlera de séquence d’ADN.

Partie I - Génération d’une séquence d’ADN

On considère la chaîne de caractère seq=’ATCGTACGTACG’.

Q1. Que renvoie la commande seq[3] ? Que renvoie la commande seq[2:6] ?

Les fonctions que nous allons construire par la suite devront prendre en paramètre une chaîne de caractères ne contenant que des ’A’, ’C’, ’G’ et ’T’ (ceci correspond à une séquence d’ADN). Nous allons commencer par construire aléatoirement une séquence d’ADN.

Pour générer aléatoirement une séquence d’ADN composée de n caractères, on utilisera le principe suivant.

1. On commence par créer une chaîne de caractères vide.

2. Puis on tire aléatoirement n chiffres compris entre 1 et 4 et

3. si on obtient un 1, alors on ajoute un ’A’ à notre chaîne de caractères ;

4. si on obtient un 2, alors on ajoute un ’C’ à notre chaîne de caractères ;

5. si on obtient un 3, alors on ajoute un ’G’ à notre chaîne de caractères ;

6. si on obtient un 4, alors on ajoute un ’T’ à notre chaîne de caractères.

7. On renvoie la chaîne de caractères ainsi construite.

Q2. Écrire une fonction generation() qui prend en paramètre un entier n et qui renvoie une chaîne de caractères aléatoires de longueur n ne contenant que des ’A’, ’C’, ’G’ et ’T’.

On pourra utiliser la fonctions randint() de random.

Q3. Que fait la fonction mystere(seq) qui prend en argument une séquence d’ADN ’seq’ (une chaîne de caractères ne contenant que des ’A’, ’C’, ’G’ et ’T’) ?

Python

def mystere(seq):
    a,b,c,d = 0,0,0,0
    i = len(seq)−1
    while i>= 0:
        if seq[i]=='A':
            a += 1
            i −= 1
        elif seq[i]=='C':
            b += 1
            i −= 1
        elif seq[i]=='G':
            c += 1
            i −= 1
        else:
            d += 1
            i −= 1
        return [a*100/len(seq),b*100/len(seq),c*100/len(seq),d*100/len(seq)]

Q4. Quelle est la complexité de la fonction mystere() ?

Donner le nom de la variable permettant de montrer la terminaison de l’algorithme.

Partie II - Recherche d’un motif

Soit une chaîne de caractères S=’ACTGGTCACT’, on appelle sous-chaîne de caractères de S unesuite de caractères incluse dans S. Par exemple, ’TGG’ est une sous-chaîne de S mais ’TAG’ n’est pas une sous-chaîne de S. Objectif

Rechercher une sous-chaîne de caractères M de longueur m appelée motif dans une chaîne de caractères S de longueur n.

Il s’agit d’une problématique classique en informatique, qui répond aux besoins de nombreuses applications.

On trouve plus de 100 algorithmes différents pour cette même tâche, les plus célèbres datant des années 1970, mais plus de la moitié ont moins de 10 ans. Dans cette partie, nous allons d’abord nous intéresser à l’algorithme naïf , puis à deux autres algorithmes : l’algorithme de Knuth-Morris-Pratt, et un algorithme utilisant une structure de liste .

Les différentes sous-parties sont indépendantes.

II.1 - Algorithme naïf

Principe de l’algorithme naïf

On parcourt la chaîne. À chaque étape, on regarde si on a trouvé le bon motif. Si ce n’est pas le cas, on recommence avec l’élément suivant de la chaîne de caractères. Cet algorithme a une complexité en O(nm) avec n, la taille de la chaîne de caractère et m, la taille du motif.

Q5. Écrire une fonction recherche() qui à une sous-chaîne de caractères M et une chaîne de caractères S renvoie -1 si M n’est pas dans S, et la position de la première lettre de la chaîne de caractères M si M est présente dans S. Cet algorithme doit correspondre à l’algorithme naïf.

Q6. Combien faut-il d’opérations pour chercher un motif de 50 caractères dans une séquence d’ADN en utilisant l’algorithme naïf ? On supposera qu’une séquence d’ADN est composée de \(3 · 10^9\) caractères. En combien de temps un ordinateur réalisant \(10^{12}\) opérations par seconde fait-il ce calcul ?

En génétique, on utilise des algorithmes de recherche pour identifier les similarités entre deux séquences d’ADN. Pour cela, on procède de la manière suivante :

• découper la première séquence d’ADN en morceaux de taille 50 ;

• rechercher chaque morceau dans la deuxième séquence d’ADN.

Q7. En utilisant les calculs précédents, combien de temps faut-il pour un ordinateur réalisant \(10^{12}\) opérations par seconde pour comparer deux séquences d’ADN avec l’algorithme naïf ?

Vous semble-t-il intéressant d’utiliser l’algorithme de recherche naïf ?

II.2 - Algorithme de Knuth-Morris-Pratt (1970)

Lorsqu’un échec a lieu dans l’algorithme naïf, c’est-à-dire lorsqu’un caractère du motif est différent du caractère correspondant dans la séquence d’ADN, la recherche reprend à la position suivante en repartant au début du motif. Si le caractère qui a provoqué l’échec n’est pas au début du motif, cette recherche commence par comparer une partie du motif avec une partie de la séquence d’ADN qui a déjà été comparée avec le motif. L’idée de départ de l’algorithme de Knuth-Morris-Pratt est d’éviter ces comparaisons inutiles. Pour cela, une fonction annexe qui recherche le plus long préfixe d’un motif qui soit aussi un suffixe de ce motif est utilisée.

Avant d’étudier l’algorithme de Knuth-Morris-Pratt nous allons définir les notions de préfixe et suffixe.

II.2.a Préfixe et suffixe

Un préfixe d’un motif M est un motif u, différent de M, qui est un début de M. Par exemple, ’mo’ et ’m’ sont des préfixes de ’mot’, mais ’o’ n’est pas un préfixe de ’mot’ .

Un suffixe d’un motif M est un motif u, différent de M, qui est une fin de M.

Par exemple, ’ot’ et ’t’ sont des suffixes de ’mot’, mais ’mot’ n’est pas un suffixe de ’mot’.

Q8. Donner tous les préfixes et les suffixes du motif ’ACGTAC’.

Q9. Quel est le plus grand préfixe de ’ACGTAC’ qui soit aussi un suffixe ?

Quel est le plus grand préfixe de ’ACAACA’ qui soit aussi un suffixe ?

II.2.b Algorithme de Knuth-Morris-Pratt

Nous rappelons que l’algorithme de Knuth-Morris-Pratt (KMP) est une fonction de recherche qui utilise une fonction annexe prenant en argument une chaîne de caractères M dont on notera la longueur m.

Cette fonction annexe, appelée fonctionannexe(), doit permettre, pour chaque lettre à la position i, de trouver le plus grand sous-mot de M qui finit par la lettre M[i] (c’est donc le plus grand suffixe de M[ :i+1]) qui soit aussi un préfixe de M. Le code de fonctionannexe() se trouve à la question Q11 du DR 6.

Python

    def fonctionannexe(M):
        F=[0]
        i=1
        j=0
        while i < m :
            if M[i]=M[j] :
                F.append(j+1)
                i=i+1
                j=j+1
            else
                if j>0 :
                    j=F[j−1]
            else:
                F.append(0)
                i=i+1
        return F

Q10. Quel est le type de la sortie de la fonction fonctionannexe() ?

Q11. Une ou des erreurs de syntaxe s’est (se sont) glissée(s) dans la fonction fonctionannexe().

Identifier la ou les erreur(s) et corriger la fonction pour qu’il n’y ait plus de message d’erreur quand on exécute la fonction.

Q12. Décrire l’exécution de la fonction fonctionannexe() lorsque M=’ACAACA’ en précisant sur le pour les six premiers tours dans la boucle while, à la sortie de la boucle, le contenu des variables : i, j et F.

Q13. L’algorithme KMP.

Python

1   def KMP(M,T):
2       F=fonctionannexe(M)
3       i=0
4       j=0
5       while i < len(T) :
6           if T[i]==M[j]:
7               if j==len(M)−1:
8                   return(i−j)
9               else:
10                  i=i+1
11                  j=j+1
12          else:
13              if j > 0:
14                  j=F[j−1]
15              else:
16                  i=i+1
17      return −1

Expliquer la ligne 2, expliquer les lignes 3 et 4.

Quelles lignes correspondent au cas où on a trouvé le mot ?

Que fait le programme dans ce cas ?

II.3 - Algorithme utilisant la structure de liste

Une autre possibilité pour chercher un motif dans une chaîne de caractères (ou séquence d’ADN) est de construire une liste contenant tous les sous-motifs de notre chaîne, triés par ordre alphabétique, puis de faire la recherche dans cette liste. Par exemple, à la chaîne ’CATCG’, on peut lui associer la liste :

[’C’,’A’,’T’,’G’,’CA’,’AT’,’TC’,’CG’,’CAT’,’ATC’,’TCG’,’CATC’,’ATCG’,’CATCG’] que l’on peut ensuite trier pour obtenir la liste :

[’A’,’AT’,’ATC’,’ATCG’,’C’,’CA’,’CAT’,’CATC’,’CATCG’,’CG’,’G’,’T’,’TC’,’TCG’].

La première étape de cette méthode est donc de trier une liste.

Q14. Écrire une fonction triinsertion() de tri par insertion d’une liste de nombres.

Q15. Comment peut-on adapter la fonction triinsertion() à une liste de chaîne de caractères ?

Après avoir obtenu une liste triée, on peut faire une recherche dichotomique dans cette nouvelle liste.

Q16. Écrire une fonction recherchedichotomique() de recherche dichotomique dans une liste de nombres triés.

Quel est l’intérêt de ce type d’algorithme (on parlera de complexité) ?

Correction

télécharger la correction