Discussion :

[cyrille_b]

Bonjour, j'ai une string contenant une séquence de lettres. Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'

Je dois rechercher dans cette séquence la premiere occurrence parmi 3 motifs : TAA ou TAG ou TGA


Je voudrais récupérer la position de la première de ces occurrences parmi les trois

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if 'TAA'  in sequence:
     print('matched TAA' , sequence.find('TAA'))
else:
    print('TAA not matched')
 
if 'TAG'  in sequence:
     print('matched TAG' , sequence.find('TAG'))
else:
    print('TAG not matched')
 
 
if 'TGA'  in sequence:
     print('matched TGA' , sequence.find('TGA'))
else:
    print('TGA not matched')

Il trouve donc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
TAA not matched
matched TAG 27
matched TGA 18

Ce que je voudrais c'est arrêter dès que la première occurrence apparaît donc ici en 18 avec le motif TGA


Auriez vous une piste pour réaliser ceci ?

D'avance merci !

[wiztricks]

Auriez vous une piste pour réaliser ceci ?

La liste des séquences TAA, TAG, TGA.
Une boucle qui, pour chaque séquence, récupère la position retournée par .find.
*et* si cette séquence est plus près du début, on la mémorise, en attendant mieux (ou la sortie de la boucle).

note: dans les tuto. on fait des exercices genre trouver le minimum d'une liste d'entier (non ordonnés).... Et comme vous avez ouvert un tuto. avant de demander de l'aide, qu'est ce qui est compliqué?

- W

[cyrille_b]

Merci pour la réponse

.. Et comme vous avez ouvert un tuto. avant de demander de l'aide, qu'est ce qui est compliqué?

Oui j'ai lu la doc, mais je pensais que le code pouvait être optimisé.

[wiztricks]

Oui j'ai lu la doc, mais je pensais que le code pouvait être optimisé.

Je ne parle pas de doc, je parle de cours pour apprendre à programmer.... car si vous ne voyez pas comment réécrire vos répétitions de presque la même chose en une boucle (telle que je l'ai décrite).
Vous pouvez aussi écrire un automate qui cherchera la présence de N séquences en parcourant une seule fois la chaine de caractères (c'est ce que je considère "optimisé" mais c'est une question d'algo. à poser dans le bon forum).

- W

[papajoker]

bonjour

Ne pas confondre optimisation et un code "propre".
l'optimisation c'est pour la vitesse ou cpu ou ram, c'est quelque chose que nous avons besoin que dans de rares cas.

Pour ton problème, il aurait fallu que tu essayes, ici tu ne donnes que le problème
Tu peux essayer par exemple d'écrire une fonction du type (si ton niveau le permet?)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'
 
def cherche_le_premier( texte, mots):
    """ on  va retourner un tuple de la forme index, mot """
    ...
    for mot in mots:
        ...
    return -1, None    # oops, on a rien trouvé
 
index, mot = cherche_le_premier(sequence, ('GA', 'TA', 'AT'))
if mot:
    print("trouvé", mot, "a l'indice:", index)

Après, qu'elle fonctionne, si tu l'utilises des milliers de fois dans ton application trop lente à cause d'elle, tu peux penser à réécrire ta fonction avec un autre algorithme.

je voudrais c'est arrêter dès que la première occurrence apparaît

cela est le résultat de ta fonction, mais en interne, tu n'es pas obligé d'arrêter dès que...

[Sve@r]

Bonjour

mais je pensais que le code pouvait être optimisé.

Déjà éviter if <string> in sequence puisque le find() te le dira lui-même directement s'il trouve et/ou s'il ne trouve pas.
Pour le reste, tu ne pourras pas te passer de traiter toutes les strings puisque si tu ne vas pas jusqu'à la dernière, tu ne sauras jamais si cette dernière n'est pas plus proche que les autres....

[wiztricks]

Salut,

Et pour ce qui est d'optimiser, on n'utilise pas vraiment Python mais les automates des expressions régulières:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
>>> import re
>>> sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'
>>> re.search("(TGA|TAA|TAG)", sequence)
<re.Match object; span=(18, 21), match='TGA'>
>>>

(a défaut de coder soi même cet automate).
- W

[tyrtamos]

Bonjour

Chacun a sa méthode, , voilà la mienne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'
motifs = ['TAA', 'TAG', 'TGA']
 
# liste des index des motifs trouvés dans sequence
inds = [sequence.find(motif) for motif in motifs]
print('liste des index des motifs:', inds)
 
# trouver le motif le plus proche du début de sequence
ind0, motif0 = max(inds), ''
for i in range(0, len(motifs)):
    if inds[i]>-1 and inds[i]<ind0:
        ind0, motif0 = inds[i], motifs[i]
print('Premier motif trouvé avec son index:', motif0, ind0)

Affichage:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
liste des index des motifs: [-1, 27, 18]
Premier motif trouvé avec son index: TGA 18

[ypcman]

Bonjour.
Peut-être plus Pythonesque :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'
res =sorted( [(m,sequence.find(m)) for m in ['TAA', 'TAG', 'TGA'] if sequence.find(m) !=-1], key= lambda t:t[1])[0]
print(res[0],'en',res[1])

[ypcman]

En stressant un peu plus les fcts avec, à la fois, une séquence plus longue et un nb de motifs plus grand :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#!/usr/bin/env python3
# coding: utf-8
 
import random
import timeit
from functools import partial
import re
 
# Initialisation random
random.seed()
 
 
def svear(sequence, motifs):
    for i in range(len(sequence)):
        for m in motifs:
            if sequence[i:i + len(m)] == m:
                return (i, m)
    # for
 
 
# for
# svear()
 
def tyrtamos(sequence, motifs):
    # liste des index des motifs trouvés dans sequence
    inds = [sequence.find(motif) for motif in motifs]
 
    # trouver le motif le plus proche du début de sequence
    ind0, motif0 = max(inds), ''
    for i in range(0, len(motifs)):
        if inds[i] > -1 and inds[i] < ind0:
            ind0, motif0 = inds[i], motifs[i]
    return (ind0, motif0)
 
 
# tyrtamos()
 
def wiztricks(sequence, motifs):
    res = re.search("(%s)" % "|".join(motifs), sequence)
    return (res.span()[0], res.group())
 
 
# wiztricks()
 
def ypcman(sequence, motifs):
    res = sorted(
        [(m, sequence.find(m)) for m in motifs if sequence.find(m) != -1], key=lambda t: t[1]
    )[0]
    return (res[1], res[0])
 
 
# ypcman()
 
# Les fonctions à tester
fct = {
    "svear": svear,
    "tyrtamos": tyrtamos,
    "wiztricks": wiztricks,
    "ypcman": ypcman,
}
 
# Les données à traiter
sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTAT\
TGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTTTATATATTATATATTTATGA\
TGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATT\
ATATATTTATGATGGGGTTTTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATA\
ATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTTTATATATTATATATT\
TATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTAT\
ATATTATATATTTATGATGGGGTTTTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATA\
TTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTTTATATATTA\
TATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTAGATGGGATTGAA\
AATTATATATTATATATTTATGATGGGGTTTTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAAT\
TATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTTTAT\
ATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTAGATGGG\
ATTGAAAATTATATATTATATATTTATGATGGGGTTTTATATATTATATATTTATGATGGGGTTAGATGGGATT\
GAAAATTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGG\
TTTTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTA\
GATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTTTATATATTATATATTTATGATGGGGTTAGAT\
GGGATTGAAAATTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATG\
ATGGGGTTTTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATG\
GGGTTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTTTATATATTATATATTTATGATGGGG\
TTAGATGGGATTGAAAATTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATA\
TTTATGATGGGGTTTTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAATTATATATTATATATTT'
 
motifs = ['TAA', 'TAG', 'TGA','GAA','TTA','GTA','ATT','GTT']
 
# Vérifications fonctions donnent toutes un même résultat
assert (len(set(tuple(f(sequence, motifs)) for f in fct.values())) == 1)
print("Vérification fonctions ok")
 
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat = 20
 
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("taille data=(%d, %d), repeat=%d" % (len(sequence), len(motifs), repeat))
for (k, v) in random.sample(tuple(fct.items()), len(fct)):
    t = timeit.Timer(partial(v, sequence, motifs)).repeat(repeat=repeat, number=100000)
    print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t) / len(t)))
# for

j'obtiens des résultats tout à fait différents :
Vérification fonctions ok
taille data=(1542, 8), repeat=20
svear: min=0.067157, max=0.073709, avg=0.068750
tyrtamos: min=0.270485, max=0.281702, avg=0.272974
ypcman: min=0.350316, max=0.360437, avg=0.357782
wiztricks: min=0.079544, max=0.081941, avg=0.080867

L'algo de Sve@r, bon dernier précédemment, prend alors sa revanche ...
test relancé 5-6 fois avec toujours l'algo de Sve@r en tête

Et ça s’aggrave en rajoutant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for _ in range(5):
    sequence += sequence

Vérification fonctions ok
taille data=(49344, 8), repeat=20
tyrtamos: min=3.113240, max=3.161914, avg=3.133876
svear: min=0.070914, max=0.072838, avg=0.072211
wiztricks: min=0.089092, max=0.091594, avg=0.089473
ypcman: min=3.201967, max=3.906027, avg=3.258431

Manifestement str.find(substr) est très sensible à la longueur de la string puisque Tyrtamos et moi sommes les seuls à l'utiliser et nos algos sont pénalisés par cette augmentation de longueur de la séquence. Le bon algo est donc celui qui, partant du 1° caractère de la séquence, teste chaque motif puis décale de un caractère et recommence, sauf s'il a trouvé un motif possible.

[tyrtamos]

Comme quoi, avant de choisir un algorithme, il vaut mieux savoir sur quelles données (type, taille, etc...) il va s'appliquer, et avec quelle fréquence...

[CosmoKnacki]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import re
import timeit
 
n = 100_000
noise = 'ACGT'*n
# noise = 'ACGTGG'*n
 
sequence = f'{noise}TGA{noise}TAG{noise}TGA{noise}'
ff = '{:>30} : {:.2e}'
 
patterns = ['TAA|TAG|TGA', 'TA[AG]|TGA', 'T(?:A[AG]|GA)', 'T[AG]{2}(?<!GG)']
 
for pattern in patterns:
    re.purge()
 
    startTime = timeit.default_timer()
    result = re.search(pattern, sequence)
    endTime = timeit.default_timer()
 
    print(ff.format(pattern, endTime - startTime))
 
startTime = timeit.default_timer()
result = sorted([(m, sequence.find(m)) for m in ['TAA', 'TAG', 'TGA'] if sequence.find(m) != -1], key = lambda t:t[1])[0] 
endTime = timeit.default_timer()
 
print(ff.format('find + List comprehension', endTime - startTime))
 
motifs = ['TAA', 'TAG', 'TGA']
startTime = timeit.default_timer()
for i in range(len(sequence)):
    find = False
    for m in motifs:
        if sequence[i:i+len(m)] == m:
            result = [m, i]
            find = True
            break
    if find:
        break
 
endTime = timeit.default_timer()
 
print(ff.format('test de chaque position', endTime - startTime))

J'ai aussi testé notamment pour voir si les optimisations dont je parlais précedemment montraient le bout de leur nez et rien à l'horizon (alors qu'avec le moteur PCRE elles sont visibles). Par contre pour mon test, le grand vainqueur est find + liste comprehension:

Code txt :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
                   TAA|TAG|TGA : 7.71e-03
                    TA[AG]|TGA : 5.07e-03
                 T(?:A[AG]|GA) : 4.93e-03
               T[AG]{2}(?<!GG) : 4.23e-03
     find + List comprehension : 1.46e-03
       test de chaque position : 5.04e-01

J'ai permuté à la mano pour voir d'éventuels changements et testé d'autres chaînes, mais rien de probant. Quant au fait de compiler les patterns à l'avance, ça ne change pratiquement rien. Par contre ce qu'il serait intéressant de tester c'est le comportement des différentes approches lorsqu'on augmente le nombre d'items recherchés.

[Beginner.]

Manifestement str.find(substr) est très sensible à la longueur de la string puisque Tyrtamos et moi sommes les seuls à l'utiliser et nos algos sont pénalisés par cette augmentation de longueur de la séquence. Le bon algo est donc celui qui, partant du 1° caractère de la séquence, teste chaque motif puis décale de un caractère et recommence, sauf s'il a trouvé un motif possible.

Je ne suis pas sûr d'avoir compris...

Si tu décales de 1 caractère à chaque fois en partant du 1° caractère de la séquence, on ne gagne pas grand chose puisque à chaque fois la recherche se fait sur le reste de la séquence, non ?

Ou bien j'ai mal compris ?

[ypcman]

Je ne suis pas sûr d'avoir compris...

Si tu décales de 1 caractère à chaque fois en partant du 1° caractère de la séquence, on ne gagne pas grand chose puisque à chaque fois la recherche se fait sur le reste de la séquence, non ?

Ou bien j'ai mal compris ?

La recherche ne s'effectue que sur le début de la séquence puisque il s'agit de comparer chaque motif recherché avec la sous-chaine de même longueur que ce motif, puis si négatif, de décaler de 1 caractère la recherche

[Beginner.]

La recherche ne s'effectue que sur le début de la séquence puisque il s'agit de comparer chaque motif recherché avec la sous-chaine de même longueur que ce motif, puis si négatif, de décaler de 1 caractère la recherche

Nos message se sont croisés...

Donc tu voulais parler de l'algo utilisé par Sve@r, c'est ça ?

[ypcman]

Nos message se sont croisés...

Donc tu voulais parler de l'algo utilisé par Sve@r, c'est ça ?

Oui exactement

[Beginner.]

Manifestement str.find(substr) est très sensible à la longueur de la string puisque Tyrtamos et moi sommes les seuls à l'utiliser et nos algos sont pénalisés par cette augmentation de longueur de la séquence. Le bon algo est donc celui qui, partant du 1° caractère de la séquence, teste chaque motif puis décale de un caractère et recommence, sauf s'il a trouvé un motif possible.

Ah je crois que je viens de comprendre : quand tu parles du bon algo, je croyais que tu disais qu'il fallait utiliser la fonctin find sur le reste de la séquence à chaque décalage d'un caractère... Mais en fait tu voulais parler de l'algo utilisé par Sve@r, c'est ça ?

Si oui eh bien je pense que c'est vrai si le nombre de motif à chercher est supérieur à un...

Si il n'y a qu'un seul motif à chercher, la fonction find devrait être aussi rapide voire plus rapide...

Qu'en pensez-vous ?