1A - Enoncé 2024¶

Toutes les questions valent deux points.

Exercice 1 : recherches de motifs¶

On suppose qu’on a une séquence d’ADN "ttcagttgtg aatgaatgga cgtgccaaat agacgtgccg ccgccgctcg attcgcactt cgtgccaaat". Les caractères a, t, g, c sont appelés bases (nucléiques) et le fragment d’ADN est donc une séquence de bases.

On s’intéresse dans ce sujet à la recherche d’un motif, c’est-à-dire d’une sous-séquence de bases, par exemple ccaa.

On pourra écrire text = "ttcagttgtg aatgaatgga cgtgccaaat agacgtgccg ccgccgctcg attcgcactt cgtgccaaat".replace(" ", "").

Q1: Ecrire une fonction qui retourne la première position du motif en utilisant une boucle et sans la méthode `index`¶

La fonction retourne la longueur du texte cherché si le motif n’est pas trouvé.

def recherche_motif(text, motif):

[1]:

def recherche_motif(text, motif):
    d = len(motif)
    for i in range(len(text) - d + 1):
        if text[i : i + d] == motif:
            return i
    return len(text)


text = "ttcagttgtg aatgaatgga cgtgccaaat agacgtgccg ccgccgctcg attcgcactt cgtgccaaat".replace(
    " ", ""
)
motif = "ccaa"

print(recherche_motif(text, motif))
print(recherche_motif(text, "aaaaaa"))

24
70

Q2 : quel est, dans le pire des cas, le coût de l’algorithme ?¶

Q3 : On souhaite maintenant écrire une fonction qui retourne toutes les positions d’un motif au sein d’un texte.¶

def positions_motif(text, motif):

[2]:

def positions_motif(text, motif):
    pos = []
    p = recherche_motif(text, motif)
    while p < len(text) and len(pos) < 5:
        pos.append(p)
        p += len(motif) + recherche_motif(text[p + len(motif) :], motif)
    return pos


text = "ttcagttgtg aatgaatgga cgtgccaaat agacgtgccg ccgccgctcg attcgcactt cgtgccaaat".replace(
    " ", ""
)
motif = "ccaa"

print(positions_motif(text, motif))
print(positions_motif(text, "aaaaaaaaaa"))

[24, 64]
[]

Q4 : quel est, dans le pire des cas, le coût de l’algorithme ?¶

[ ]:

Q5 : comment modifier (ou pas) votre fonction pour cet exemple ?¶

text = "cgtgccaaaccaaacc"
motif = "ccaaac"
assert positions_motif(text, motif) == [4, 9]

[3]:

def positions_motif_chevauchement(text, motif):
    pos = []
    p = recherche_motif(text, motif)
    while p < len(text) and len(pos) < 5:
        pos.append(p)
        p += 1 + recherche_motif(text[p + 1 :], motif)
    return pos


text = "cgtgccaaaccaaacc"
motif = "ccaaac"

print(positions_motif(text, motif))
print(positions_motif_chevauchement(text, motif))

[4]
[4, 9]

Q6 : On veut accélérer le processus. On considère un couple de bases et non plus une seule base.¶

Ecrire une fonction une fonction qui construit tous les couples de bases à partir des bases a,c,g,t.

[4]:

def couple_base():
    res = []
    for a in "acgt":
        for b in "acgt":
            res.append(a + b)
    return res


print(couple_base())

['aa', 'ac', 'ag', 'at', 'ca', 'cc', 'cg', 'ct', 'ga', 'gc', 'gg', 'gt', 'ta', 'tc', 'tg', 'tt']

Q7 : Transformer cette liste en dictionnaire.¶

Le dictionnaire devra avoir pour clé un couple, pour valeur un nombre entier unique.

[5]:

res = couple_base()
dico = {couple: i for i, couple in enumerate(res)}
print(dico)

{'aa': 0, 'ac': 1, 'ag': 2, 'at': 3, 'ca': 4, 'cc': 5, 'cg': 6, 'ct': 7, 'ga': 8, 'gc': 9, 'gg': 10, 'gt': 11, 'ta': 12, 'tc': 13, 'tg': 14, 'tt': 15}

Q8 : Ecrire une fonction qui découpe une séquence de bases en séquence de couples de bases.¶

Chaque gène sera représenté par le nombre entier défini à la question précédente. On supposera que la séquence est de longueur paire. On fera de même pour le motif.

[6]:

def decoupe_sequence(text, dico):
    return [dico[text[i : i + 2]] for i in range(0, len(text), 2)]


text = "ttcagttgtg aatgaatgga cgtgccaaat agacgtgccg ccgccgctcg attcgcactt cgtgccaaat".replace(
    " ", ""
)
motif = "ccaa"
text_couple = decoupe_sequence(text, dico)
print(text_couple)
motif_couple = decoupe_sequence(motif, dico)
print(motif_couple)

[15, 4, 11, 14, 14, 0, 14, 0, 14, 8, 6, 14, 5, 0, 3, 2, 1, 11, 9, 6, 5, 9, 6, 7, 6, 3, 13, 9, 1, 15, 6, 14, 5, 0, 3]
[5, 0]

Q9 : appliquer l’une de vos précédente fonction de recherche avec ces deux séquences pour trouver les positions.¶

[7]:

def positions_motif_couple(text_couple, motif_couple):
    position = positions_motif(text_couple, motif_couple)
    return [p * 2 for p in position]


positions_motif_couple(text_couple, motif_couple)

[7]:

[24, 64]

Q10 : coût de la recherche et résultats équivalents¶

Quelle recherche est plus rapide ? Combien de fois plus rapide ?
Pourquoi ces deux recherches ne sont pas équivalentes ?

Notebook on github