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

[jurassic pork]

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 :

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

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 :

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

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

[Sve@r]

Bonjour

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

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

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 python :

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

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

[tyrtamos]

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

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 :

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

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 :

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

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)

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

Entièrement d'accord!

[Sve@r]

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

[wiztricks]

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

[tyrtamos]

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.

[Sve@r]

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

[CosmoKnacki]

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

[jurassic pork]

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 :

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

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 ?

[wiztricks]

une explication pour ces différences ?

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

- W

[Sve@r]

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

Code python :

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
#!/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 :

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

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