CCINP Informatique Commune TSI 2020Sujet, corrigé et rapport du jury

ÉPREUVE SPÉCIFIQUE - FILIÈRE TSI

INFORMATIQUE

Mercredi 6 mai : 8 h-11 h

RAPPEL DES CONSIGNES

• Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
• Ne pas utiliser de correcteur.
• Écrire le mot FIN à la fin de votre composition.

Les calculatrices sont interdites

Le sujet est composé de trois parties, toutes indépendantes.

Seul le document réponse est à rendre.

• le texte du sujet et une annexe, 7 pages,
• le Document Réponse (DR) à rendre en fin d'épreuve, 12 pages.

Autour du séquençage du génome

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

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

• si on obtient un 1, alors on ajoute un 'A' à notre chaîne de caractères;
• si on obtient un 2, alors on ajoute un 'C' à notre chaîne de caractères;
• si on obtient un 3, alors on ajoute un 'G' à notre chaîne de caractères;
• si on obtient un 4, alors on ajoute un 'T' à notre chaîne de caractères.

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

Partie II - Recherche d'un motif

II. 1 - Algorithme naïf

Principe de l'algorithme naïf

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

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

II.2.a Préfixe et suffixe

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

II. 3 - Algorithme utilisant la structure de liste

II. 4 - Fonction de hachage et évaluation de polynôme

II.4.a Fonction de hachage, algorithme de Karp-Rabin

• à chaque caractère de l'alphabet, on associe une valeur. Ici, on va associer à 'A' la valeur 0 , à 'C' la valeur 1, à 'G' la valeur 2 et à 'T' la valeur 3. Pour un motif de taille n, on obtient donc une suite de chiffre a_(n − 1)…a_1 a_0. Par exemple, à la chaîne 'TAGC', on lui associe la suite de chiffre 3021;
• cette suite de chiffre est considérée comme l'écriture d'un entier en base b, où b est le nombre de caractères présents dans l'alphabet. On a donc ici b = 4;
• on calcule ensuite cet entier en base 10 (on calcule donc a_(n − 1)b^(n − 1) + … + a_1 b^1 + a_0 b^0 );
• puis on calcule le reste de la division euclidienne de ce nombre par 13.

II.4.b Évaluation de polynôme, Algorithme de Hörner

Partie III - Collection Française de Bactéries Phytopathogènes

• l'une, appelée Echantillon, qui permet de stocker les différents échantillons d'ADN;
• l'autre, appelée Sequence, qui permet de mémoriser quelle personne est responsable de l'obtention de la séquence (i.e. de l'extraction d'un gène particulier dans les différents échantillons d'ADN).
  Des extraits des tables Echantillon et Sequence sont données par les tableaux 1 et 2.

ANNEXE - Librairie numpy

FIN

J. 201173

Autour du séquençage du génome

Document Réponse

Q1

seq='ATCGTACGTACG'
seq[3]

seq='ATCGTACGTACG'
seq[2:6]

NE RIEN ÉCRIRE DANS CE CADRE

Q2

def mystere(seq):
    $a, b, c, d=0,0,0,0$
    i = len(seq)-1
    while $\mathrm{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 $\left[a_{*} 100 / l e n(s e q), b_{*} 100 / l e n(s e q), c_{*} 100 / l e n(s e q), d_{*} 100 / l e n(s e q)\right]$
Réponse :

Q4

Q5

Q6

Q7

Est-ce intéressant d'utiliser cette méthode?

J. 201173

Q8

Q9

Q10

Q11

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

Q12

def KMP(M,T):
    F=fonctionannexe(M)
    i=0
    j=0
    while i < len(T) :
        if T[i]==M[j]:
            if j==len(M)-1:
                return(i-j)
            else:
                i=i+1
                j=j+1
        else:
            if j > 0:
                j=F[j-1]
            else:
                i=i+1
    return -1

Q15

J. 201173

Q21