Retrouver le premier motif dans une string parmi plusieurs motifs

Version imprimable

Voir 40 message(s) de cette discussion en une page

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

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:

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:

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 !

04/03/2023, 19h02
wiztricks

Citation:

Envoyé par cyrille_b

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
04/03/2023, 19h21
cyrille_b

Merci pour la réponse

Citation:

.. 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é.
04/03/2023, 19h58
wiztricks

Citation:

Envoyé par cyrille_b

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

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:

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.

Citation:

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

04/03/2023, 22h30
Sve@r

Bonjour

Citation:

Envoyé par cyrille_b

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....
04/03/2023, 23h30
wiztricks
Salut,

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

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

Bonjour

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

Code:

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:

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

Hello,
en reprenant les expressions régulières de wiztricks voici un code qui :
1 - donne le premier motif trouvé avec son index dans la chaîne de départ (en partant de 0)
2 - donne tous les motifs trouvés et leurs places dans la chaîne de départ :
Code:

1 2 3 4 5 6 7 8 9 10 import re sequence = 'TTATATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA' result = re.search("(TGA|TAA|TAG)", sequence) if result: print(f"résultat -> {result.group()} : index {str(result.start())}") result = re.finditer("(TGA|TAA|TAG)", sequence) for match_obj in result: print(match_obj) else: print("pas de résultat")
Résultat :

Citation:

résultat -> TGA : index 20
<re.Match object; span=(20, 23), match='TGA'>
<re.Match object; span=(29, 32), match='TAG'>
<re.Match object; span=(39, 42), match='TGA'>

Ami calmant, J.P

Bonjour.
Peut-être plus Pythonesque :

Code:

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])

Citation:

Envoyé par tyrtamos

Bonjour

Hey, ça faisait longtemps qu'on ne t'avait pas vu :chin:

Citation:

Envoyé par tyrtamos

Chacun a sa méthode

Force est de constater que celle de wiztricks est un modèle d'élégance et de simplicité. Et elle utilise un module peut-être écrit en C donc plus rapide que Python lui-même...

Citation:

Envoyé par tyrtamos

voilà la mienne:

Elle commence malheureusement par faire un find de toutes les séquences, ce qui est le noeud critique de l'algo.

Mais cela m'a donné une autre idée: puisqu'il faut trouver le premier motif, autant s'arrêter au premier motif...
Code:

1 2 3 4 5 6 7 8 9 10 11 sequence = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA' motifs = ['TAA', 'TAG', 'TGA'] for i in range(len(sequence)): for m in motifs: if sequence[i:i+len(m)] == m: print(m, i) exit(0) # if # for # for
Parfois faut pas avoir peur des boucles imbriquées, elles ne sont pas forcément synonyme de complexité...;)

05/03/2023, 10h58
tyrtamos
Bonjour Sve@r

Citation:

Envoyé par Sve@r

Hey, ça faisait longtemps qu'on ne t'avait pas vu

Et oui, je commence à faire partie des "retraités qui n'ont plus une minute à eux"... :D

Citation:

Envoyé par Sve@r

Elle commence malheureusement par faire un find de toutes les séquences, ce qui est le nœud critique de l'algo.

Je ne vois vraiment pas comment on peut calculer l'indice minimum sans les calculer tous!

Cependant, je peux améliorer mon code en ne calculant l'indice pour chaque motif que dans la boucle for.
Code:

1 2 3 4 5 ind0, motif0 = len(sequence), '' for i in range(0, len(motifs)): ind = sequence.find(motifs[i]) if ind>-1 and ind<ind0: ind0, motif0 = ind, motifs[i]
Ce qui donne, bien sûr, le même résultat (TGA 18), qui coïncide avec le résultat espéré par le PO.

Pour être complet, il faudrait d'ailleurs ajouter un test final pour vérifier qu'on a trouvé au moins un motif dans sequence:
Code:

1 2 3 4 if motif0=='': print("Aucun des motifs n'est trouvé dans sequence") else: print('Premier motif trouvé avec son index:', motif0, ind0)
Citation:

Envoyé par Sve@r

Parfois faut pas avoir peur des boucles imbriquées, elles ne sont pas forcément synonyme de complexité...;)

Entièrement d'accord!
05/03/2023, 11h05
Sve@r

Citation:

Envoyé par tyrtamos

Je ne vois vraiment pas comment on peut calculer l'indice minimum sans les calculer tous!

En traitant la chaine et en sortant dès qu'on trouve un motif, comme je l'ai écrit...
05/03/2023, 11h59
wiztricks

Citation:

Envoyé par Sve@r

En traitant la chaine et en sortant dès qu'on trouve un motif, comme je l'ai écrit...

Côté complexité (algorithmique), c'est pas top de créer autant de s/chaines que de caractères * nombre de motifs.

- W
05/03/2023, 12h11
tyrtamos

Citation:

Envoyé par Sve@r

En traitant la chaine et en sortant dès qu'on trouve un motif, comme je l'ai écrit...

Cela parait plus élégant, mais je ne suis pas sûr que ce soit plus rapide. En effet, on boucle alors sur les caractères de sequence, alors que je ne boucle que sur les motifs. Tout dépend en fait si find est écrit en python ou en C. Si c'est en C, je préfère ma méthode.
05/03/2023, 12h14
Sve@r
Citation:

Envoyé par wiztricks

Côté complexité (algorithmique), c'est pas trop de créer autant de s/chaines que de caractères * nombre de motifs.

Je compte aussi un peu sur la chance de trouver un résultat avant d'avoir tout balayé. De toute façon il faut faire un choix (de façon hypothétique s'entend car ta solution initiale à base de "re" reste la meilleure)
- un find pour chaque motif
- la boucle imbriquée
Chaque décision aura des avantages et inconvénients selon comment se présentent les datas à traiter
05/03/2023, 13h07
CosmoKnacki

Citation:

Envoyé par Sve@r

...ta solution initiale à base de "re" reste la meilleure

Je ne sais pas si c'est le cas pour re, mais certains moteurs de regex sont à même d'optimiser la recherche dans cette configuration précise (une alternative de plusieurs chaînes littérales à la racine et sans groupe comme ici TAA|TAG|TGA) en court-circuitant la recherche "normale" du moteur avec un algorithme de recherche rapide. Comme le temps alloué à la recherche d'une possibilité d'optimiser est trés court, la moindre "complication" détectée la fera avorter, d'où le fait d'éviter d'utiliser un groupe T(?:A[AG]|GA), ni même d'écrire TA[AG]|TGA en pensant bien faire.

Je viens de faire un test de performance entre un code qui utilise des boucles un code qui utilise les expressions régulières et le code de ypcman avec find :

Code:

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
import re
import timeit
sequence = 'TTATATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'
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:
            print(m, i)
            find = True
            break
    if find:
        break
        # if
    # for
# for
endTime = timeit.default_timer()
print("loop search time : ",str(endTime-startTime) + "s")
startTime = timeit.default_timer()
result = re.search("(TGA|TAA|TAG)", sequence)
endTime = timeit.default_timer()
print("regex search time : ",str(endTime-startTime) + "s")
if result:
    print(f"résultat -> {result.group()} : index {str(result.start())}")
    result = re.finditer("(TGA|TAA|TAG)", sequence)
    for match_obj in result:
        print(match_obj)
else:
    print("pas de résultat")
startTime = timeit.default_timer()
res =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(res[0],'en',res[1])
print("ypcman search time : ",str(endTime-startTime) + "s")

Voici le résultat que j'obtiens sur mon ordinateur en python 3.10 :

Citation:

TGA 20
loop search time : 0.0018425000016577542s
regex search time : 0.00039910000123200007s
résultat -> TGA : index 20
<re.Match object; span=(20, 23), match='TGA'>
<re.Match object; span=(29, 32), match='TAG'>
<re.Match object; span=(39, 42), match='TGA'>
TGA en 20
ypcman search time : 2.010000025620684e-05s

une explication pour ces différences ?

05/03/2023, 14h17
wiztricks

Citation:

Envoyé par jurassic pork

une explication pour ces différences ?

ça me semble cohérent avec la complexité (algorithmique) - en gros le nombre d'itérations... -.

- W

Voici un bench sur toutes les méthodes montrées ici

Code:

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
#!/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 = 'TTATATATTATATATTTATGATGGGGTTAGATGGGATTGAAAA'
motifs = ['TAA', 'TAG', 'TGA']
 
# 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

Et au résultat...

Code:

1
2
3
4
5
6
Vérification fonctions ok
taille data=(43, 3), repeat=20
wiztricks: min=0.122654, max=0.128518, avg=0.123840
svear: min=0.691222, max=0.697228, avg=0.692699
ypcman: min=0.124747, max=0.126022, avg=0.125062
tyrtamos: min=0.105545, max=0.106783, avg=0.106086

tyrtamos en sort grand vainqueur (aurait-on dû en douter? :aie:)

Voir 40 message(s) de cette discussion en une page