Expression régulière avec au moins 1 erreur toléré ?

wizard67370 · Le 22/01/2010, à 18:20

Bonjour à vous tous. Ca fait 3 mois maintenant que j'utilise ubuntu.
Je suis biologiste je cherche actuellement a développé un petit logiciel mais voilà j'ai un problème avec une expressions régulière que je cherche à faire.

En faite, je voudrais que grep me cherche une séquence (allant de 15 à 25 caractère) dans un génome (là rien de bien compliqué).
Là ou ca se corse, c'est que j'aimerai introduire une notion de variabilité. A savoir que 1 des caractères dans n'importe quels position peut changer.

Par exemple considérons ce mot.
AAAAA
j'aimerais que grep puisse me trouver AAAAA mais également [AGTC]AAAAA ou A[AGTC]AAAA ou AA[AGTC]AA ou AAA[AGTC]A ou AAAA[AGTC].

Pour l'instant je ne sais utilisé que
grep, more, tr, sed, wget. Je sais c'est pas beaucoup donc si vous me proposez un autre programme que celà, pourriez vous m'expliquez (en vulgarisant un peu) ? Je ne demande qu'à apprendre.

Je vous remercie tous d'avance pour votre aide.

Cordialement.

snapshot · Le 22/01/2010, à 18:36

L'ADN et les codons, c'était justement le sujet de mon mémoire :-)

Tu as trouvé la solution toi-même, avec la liste de "ou".
La regexp à utiliser est :

[AGTC]AAAAA|A[AGTC]AAAA|AA[AGTC]AA|AAA[AGTC]A|AAAA[AGTC]

Le symbole | (pipe) voulant dire "ou".

Mais il y a plusieurs pièges :
- grep, tout d'abord. Il existe deux principale syntaxe de regexp. La moderne et l'ancienne. Je te conseille d'utiliser la version moderne, en utilisant egrep au lieu de grep (ou si tu tiens à grep, utilises grep -E, ce qui revient au même. Avec l'ancienne syntaxe, la regexp devient un truc aussi illisible que :

\[AGTC\]AAAAA\|A\[AGTC\]AAAA\|AA\[AGTC\]AA\|AAA\[AGTC\]A\|AAAA\[AGTC\]

Avec l'ancienne syntaxe, les caractère [], |, et bien d'autres, perdent leur signification. Il faut les préfixer par \ pour qu'ils la retrouvent. Du coup la regexp est truffée de \ et devient illisible. Avec la nouvelle syntaxe, c'est exactement l'inverse : il faut mettre \ pour enlever la signification spéciale de ces caractères.

- le shell, mais je pense que tu le sais déjà. Le pipe est utilisé par le shell. Il faudra donc que tu mettes toute la regexp entre quote pour éviter qu'il se méprenne sur la signification de la ligne :

egrep '[AGTC]AAAAA|A[AGTC]AAAA|AA[AGTC]AA|AAA[AGTC]A|AAAA[AGTC]'

Avec cette méthode, tu pourras trouver des motifs relativement simples, mais elle est peu extensible. Si tu veux par exemple 2 erreurs, la longueur de la regexp à écrire devient exponentielle...
Il faudrait trouver un système de regexp spécialisé pour l'ADN

Dernière modification par snapshot (Le 22/01/2010, à 18:53)

snapshot · Le 22/01/2010, à 18:49

Pour les autres commandes du shell, je te conseille de lire la bible du shell en ligne :
http://abs.traduc.org/abs-fr/ch15.html

wizard67370 · Le 22/01/2010, à 20:28

En faite, j'aimerais justement éviter de taper 15 fois la même expression (en changeant à chaque fois 1 lettre).
En gros faire que grep (ou egrep) cherche l'oligo recherché et qu'il tolère 1 seul changement de caractère.

La séquence AAAAA n'était qu'un exemple. Je suis en train de faire un shell script ou l'utilisateur rentrera l'oligo qu'il souhaite sans avoir à écrire l'expression X fois.
Par exemple: si j'écris "science", qu'il intégre automatique ".cience", "s.ience", "sc.ence" , "sci.nce" etc sans que j'ai besoin de l'écrire.

EDIT: J'avais éventuellement pensé à ce que quand tu tape l'oligo, il compte le nombre caractère ( avec wc -o). Il copie colle la séquence X fois le nombre de caractère (histoire de générer une liste mais je sais pas encore faire (je lis le lien vais surment trouver)). Enfin avec sed, demandé qu'il remplace l'expression 1 (admettons science) par l'expression .cience, puis pour le second il remplace l'expression 1 (science) par s.ience etc... le nombre de fois nessaire.

Voilà aprés c'est devrait pas être compliqué avec egrep.

Merci pour le lien, c'est surper interressant. Je crois que je vais encore passé une nuit blanche lol.

Dernière modification par wizard67370 (Le 22/01/2010, à 20:45)

nesthib · Le 22/01/2010, à 20:43

bonjour wizard67370, je suis également biologiste et j'ai également commencé à développer mes scripts en bash. Je me suis rapidement trouvé limité par une syntaxe non adaptée. Puis j'ai découvert Biopython. Tu trouveras tout un tas de modules de Biopython qui font déjà ce que tu cherches à coder (j'avais fait des scripts pour manipuler les séquences). Le nom du paquet est python-biopython (il y a un version perl si tu préfères).
Pour faire de l'alignement tu as la possibilité d'utiliser les programmes du NCBI en local en installant le paquet blast2.
Pour le design d'oligos tu as primer3 disponible également dans les dépôts mais aussi (et c'est plus facile pour l'utiliser) via une page web.

Si tu es intéressé j'ai quelques scripts maison pour de la biomol.

edit : je ferais bien une page de doc tiens…

Dernière modification par nesthib (Le 22/01/2010, à 20:45)

grim7reaper · Le 22/01/2010, à 20:45

Salut,

wizard67370 a écrit :

En faite, j'aimerais justement éviter de taper 15 fois la même expression (en changeant à chaque fois 1 lettre).
En gros faire que grep (ou egrep) cherche l'oligo recherché et qu'il tolère 1 seul changement de caractère.
La séquence AAAAA n'était qu'un exemple. Je suis en train de faire un shell script ou l'utilisateur rentrera l'oligo qu'il souhaite sans avoir à écrire l'expression X fois.

Pas sur que ça soit réalisable avec grep (mais bon je peux me tromper je ne suis pas un spécialiste du grep), en tout cas ça ne me semble pas trivial.

Sinon, je ne sais pas ce que tu développes comme logiciel mais il y a des langages bien plus adapté pour la bioinformatique.
Si c'est juste un petit script, le bash peut faire l'affaire. Mais si tu veux faire un truc sérieux alors fuis le bash (c'est pas fait pour ça ,c'est pas portable et pas souple non plus).

Donc pour coder un bon truc en bioinfo je te conseillerais plutôt le Perl et ses extensions BioPerl (http://www.bioperl.org/wiki/Main_Page) ou alors le Python et sa bibliothèque BioPyhon (http://biopython.org/wiki/Main_Page).
Ces 2 langages fournissent des fonctions qui permettent de manipuler facilement les séquences, parser des fichier (FASTA, EMBL, Interpro, etc.) et d'utiliser de nombreux outils (les différents blast par exemple).

Bon après je ne sais pas ce que tu compte créer, ni ton niveau en informatique. Mais si ça t'intéresses ça reste des langages relativement simple à apprendre.

Edit :grillé par nesthib

Dernière modification par grim7reaper (Le 22/01/2010, à 20:46)

snapshot · Le 22/01/2010, à 20:51

J'ai beau chercher, je ne vois pas comment avec une regexp tolérer la moindre erreur, autrement qu'en faisant une liste de OU. Les regexp ne sont pas forcément adaptées à ce genre de recherche. Si tu y tiens absolument (sans utiliser les solutions données plus haut par les autres intervenants), je ferai un petit script qui calcule automatiquement une regexp liée à une séquence ADN avec au choix une, deux, ou trois erreurs dedans. Cette regexp serait ensuite passée à egrep via l'opérateur $() ou `backtick` du shell. Elle pourrait devenir relativement longue, mais ce doit plus être un problème pour nous que pour la machine.

wizard67370 · Le 22/01/2010, à 20:55

Merci je vais voir.
En faite, je travail en biologie de l'environnement.
J'utilise des séquences d'oligo spécifique d'un certaine classe de bactérie.
Je developpe donc un script qui me permet de télécharger automatique les génomes sur ncbi.
De rechercher génomes par génomes si mes amorces fonctionnerais.
Si celà fonctionne, mv le génome en question vers un autre dossier, sinon rm.
J'aurai ainsi une liste d'organisme chez qui mes oligos fonctionnerais. Je pourrais alors contrôler si mes amorces sont toujours spécifique de mes organismes.

Voilà, le seul problème, c'est que j'ai remarqué que même chez des amorces universelle il pouvait y avoir une tolérance de 1 nucléotide, et que ca pouvait être n'importe lequel (même si un consensus a été fixé).

(eDiT: Vous êtes super réactif sur ce forum, j'ai même pas le temps d'écrire que j'ai déjà 15 réponses lol. un grand merci, je crois que j'ai beaucoup de lecture du coup.)

Dernière modification par wizard67370 (Le 22/01/2010, à 20:59)

nesthib · Le 22/01/2010, à 21:04

@wizard67370
avec biopython tu as la possibilité d'interroger directement les bases de données de séquences (ex. NCBI, Expasy, PDB…) et de récupérer automatiquement les séquences (enfin faut coder le script ) et surtout de manipuler tes séquences comme tu le veux
avec biopython ou blast tu peux faire tes alignements
avec python tu peux faire tout le reste (lecture fichiers, écriture, déplacement, création répertoires…)
avec primer3 tu peux faire des alignements adaptés au oligonucléotides avec possibilité de choisir différentes tolérances.

Totor · Le 22/01/2010, à 22:20

Bonsoir,

wizard67370 a écrit :

En faite, j'aimerais justement éviter de taper 15 fois la même expression (en changeant à chaque fois 1 lettre).
En gros faire que grep (ou egrep) cherche l'oligo recherché et qu'il tolère 1 seul changement de caractère.

Alors en fait, c'est assez simple et il ne faut pas passer par la recherche de toutes les combinaisons possibles.
Pré-requis : tu as déjà vérifié que ton mot fait entre 15 et 25 caractères. En fait, ce n'en est pas vraiment un mais je considère que tu as déjà la solution. Si ce n'est pas le cas, fait-le savoir.

Bon, pour ton problème, en gros, tu as donné la piste de la solution : "[..] tolère 1 seul changement de caractère"
Cela signifie qu'il ne peut y avoir que 2 caractères distincts dans ton mot.
Le tout est donc de compter le nombre de caractères qui diffèrent.
Pour cela, on peut s'appuyer sur l'outil uniq. mais pour cela il faut :
1 : transformer ton mot en autant de ligne qu'il y a de lettre (uniq travaille avec des lignes)
2 : trier les lignes par ordre alphabétique (pour trouver les éléments distincts, il faut que le flux soit trié)

Pour transformer ton mot en ensemble de lignes, on peut utiliser sed avec l'idée de transformer chaque caractère par lui même avec en plus un retour à la ligne.
Pour trier les lignes, il ya l'instruction sort.

Cela donne (je considère que tu travailles avec une variable contenant ta chaine):

mot="AAADAAAAAAAAAAA"
sed -r 's/(.)/\1\n/g' <<< "${mot}"|sort|uniq

La transformation du dernier caractère du mot en ligne provoque la création d'une ligne vide (en 1ère position après le tri). 2 solutions :
1 - on la supprime (sed fera l'affaire)

sed -r 's/(.)/\1\n/g' <<< "${mot}"|sort|uniq|sed '1d'

2 - on la conserve en tolérant cette ligne comme 3ème caractère. Il faudra donc que le nombre de ligne soit <=3 (et non pas <=2)

Maintenant que l'on a toutes les lettres (sous forme de ligne) de la séquence, on les compte :
(sans suppression de la 1ère ligne vide) :

mot="AAADAAAAAAAAAAA"
nb_lettre=$(sed -r 's/(.)/\1\n/g' <<< "${mot}"|sort|uniq|wc -l)
((${nb_lettre} <= 3 )) && echo "${mot} est correcte \!" || echo "${mot} n'est pas correcte \!"

Voilà !

Pour le reste, puisque tu ne demandes qu'à apprendre, je te conseille de suivre les recommandations de nesthib

nesthib · Le 22/01/2010, à 23:03

@Totor : je pense que tu n'as pas compris la demande de wizard67370 (bon, pour ta défense il faut connaître un minimum de génétique ).

si l'on prend l'exemple d'une séquence ADN, codée par 4 lettre différents (A,C,G,T) :

catgtacccgattcgcgatattcttcatgagcgtcatgcgcatgctcgcattgatcgcagt

ce que veut wizard67370 c'est déterminer si une séquence courte donnée (ex. cgctatat) est contenue dans la première séquence avec au maximum une erreur (=une mutation ou un ajout/suppression)

catgtacccgattcgcgatattcttcatgagcgtcatgcgcatgctcgcattgatcgcagt
             ||| ||||
             cgctatat

Les alignements de séquence ne reposent pas sur des expressions rationnelles mais sur des algorithmes calculant la meilleure corrélation entre les 2 séquences grâce à un système de pénalités en cas de non correspondance (il existe différentes matrices) ce que fait parfaitement blast par exemple.
voir ici pour une explication → http://en.wikipedia.org/wiki/Sequence_alignment

sputnick · Le 22/01/2010, à 23:29

Qq'un a un Alka-Seltzer ?

nesthib · Le 22/01/2010, à 23:37

@sputnick : il dit qu'il voit pas le rapport

Totor · Le 22/01/2010, à 23:44

effectivement ce n'est pas ce que j'avais compris ! qd a la génétique, ça date d'il y a 15 ans
Pour le reste, ça reste tout aussi simple. Il "suffit" de convertir le mot et la séquence en code ascii binaire et de faire des comparaisons de type "ET" en procédant à des décalages de byte jusqu'à obtenir ke des 1 ou 1 seul 0. c possible en bash mais je ne pourrais pas fournir 2 code avant lundi relèveras-tu le défi ?;):D:P

nesthib · Le 22/01/2010, à 23:50

@Totor : en fait ce n'est pas si simple que ça, il y a tout un système de pénalités, différents algorithme selon que l'on utilise différents types de séquences (voir la page wikipédia pour vulgarisation)

nordinatueur · Le 24/11/2010, à 13:16

Sinon il y a agrep dans les dépôts, avec l'option -B :

man a écrit :

-y Used with -B option. When -y is on, agrep will always output the
best matches without giving a prompt.
-B Best match mode. When -B is specified and no exact matches are
found, agrep will continue to search until the closest matches
(i.e., the ones with minimum number of errors) are found, at which
point the following message will be shown: "the best match contains
x errors, there are y matches, output them? (y/n)" The best match
mode is not supported for standard input, e.g., pipeline input.
When the -#, -c, or -l options are specified, the -B option is
ignored. In general, -B may be slower than -#, but not by very
much.
-Dk Set the cost of a deletion to k (k is a positive integer). This
option does not currently work with regular expressions.
-G Output the files that contain a match.
-Ik Set the cost of an insertion to k (k is a positive integer). This
option does not currently work with regular expressions.
-Sk Set the cost of a substitution to k (k is a positive integer).
This option does not currently work with regular expressions.
....
Combination of exact and approximate matching
any pattern inside angle brackets <> must match the text exactly
even if the match is with errors. For example, <mathemat>ics
matches mathematical with one error (replacing the last s with an
a), but mathe<matics> does not match mathematical no matter how
many errors we allow.
....
agrep -1 -D2 -S2 'ABCD#YZ' foo
outputs the lines containing ABCD followed, within arbitrary dis‐
tance, by YZ, with up to one additional insertion (-D2 and -S2 make
deletions and substitutions too "expensive").
....
agrep -d '$$' -1 '<word1> <word2>' foo
finds all paragraphs that contain word1 followed by word2 with one
error in place of the blank. In particular, if word1 is the last
word in a line and word2 is the first word in the next line, then
the space will be substituted by a newline symbol and it will
match. Thus, this is a way to overcome separation by a newline.
Note that -d '$$' (or another delim which spans more than one line)
is necessary, because otherwise agrep searches only one line at a
time.

Je pense que cela peut t'être utile :
Surtout avec les option -D et -I, si tu veux juste une subistution. (-D2 indique qu'un suppression vaut 2 erreurs...)

Par exemple, si tu veux juste une substitution, tu peux faire :

 agrep -1 -D2 -I2 < fichier_séquence
# Et pour deux substitutions :
agrep -2 -D3 -I3 < fichier_séquence
# Un deux insertions ou trois substitutions :
agrep -6 -D7 -I3 -S2 < fichier_séquence
# Le problème c'est que ça autorise aussi l'ensemble { une substitution et une insertion } .

Bref voilà pour ma petite contribution...

Dernière modification par nordinatueur (Le 24/11/2010, à 13:17)

ehmicky · Le 24/11/2010, à 21:17

Je donne juste une possibilité en Bash pour la question de départ :
(sequence est la séquence recherchée (par exemple "acga") et fichier le chemin du fichier contenant les séquences à analyser (par exemple "/chemin/vers/le/fichier.txt") :

for (( a = 1 ; a <= ${#sequence} ; ++a ))
do
    grep -E "${sequence:0:a-1}.${sequence:a}" "$fichier"
done

Mais agrep te permettra d'être plus flexible, et sinon pour ce qui est d'envisager un autre langage, je pense que c'est une excellente idée.
Je pense que Python par exemple sera bien mieux, et en plus il doit y avoir plein de modules intéressants qui t'éviteront de réinventer la roue.

Dernière modification par ehmicky (Le 24/11/2010, à 21:18)

nordinatueur · Le 25/11/2010, à 05:24

Je suis d'accord, mais pour moi apprendre un nouveau langage est long... Déjà le bash je le connais pas encore bien... depuis le temps que je l'utilise... D'où ma solution « agrep », même si les solutions en python semblent plus « naturelles » quand elles sont maîtrisées.

De plus avec cette solution (que je trouve très jolie et ingénieuse, je dois l'avouer), il ne peut envisager que des "insertions" dans le code. Or ce qui est intéressant c'est surtout les substitutions dans son cas...
Quoi qu'avec un « ${sequence:a+1} » au lieu de « ${sequence:a} » pourrait donner le bon résultat en presque "full-bash".

Soit-dit en passant, merci ehmicky et nesthib pour vos contributions. Ça fait toujours plaisir de voir le libre avancer à travers ce forum. J'ai eu tellement l'occasion d'apprendre de vous directement et indirectement.

ehmicky · Le 25/11/2010, à 05:32

Oui, je suis d'accord avec toi, faut pas réinventer la roue, et agrep a l'air d'avoir des options qui lui donneront plus de possibilités, et ce sera plus simple à utiliser. J'ai juste donné du Bash "histoire de"
Après, pour Python, tout dépend de lui, s'il a la motivation je pense que ça vaut le coup.

Edit : en y réfléchissant, je me dit que par ailleurs, si le temps de recherche est un facteur vraiment important pour lui, ça vaudrait peut-être le coup de regarder les modules dont parle Nesthib ou tout autre algorithme prévu spécifiquement pour ce problème. En effet, grep est efficient ; néanmoins, il s'agit d'une recherche octet par octet. Si tes séquences ne bougent pas trop, rien qu'en les implémentant sous forme de hash tables, cela diviserait le temps de recherche par au moins 10. Après, sûrement que les modules prévus pour ça ont des solutions encore plus efficientes.
Edit 2 : tiens d'ailleurs l'article Wikipedia des hash tables parle explicitement de la recherche dans une base de donnée génétique.

Dernière modification par ehmicky (Le 25/11/2010, à 08:01)

nesthib · Le 25/11/2010, à 10:51

L'alignement de séquences nucléotidiques est un thème de recherche à part entière, je ne pense pas qu'avec les outils standards UNIX et sans plonger dans de l'algo vous réussissiez à faire mieux que les outils développés exprès pour.

Il y a des outils très bien pour faire tout ça, utilisez-les ! (en plus ils sont souvent libres)

pour ceux qui veulent une introduction à la thématique : http://en.wikipedia.org/wiki/Sequence_alignment

NB. un peu de déterrage au passage

nordinatueur · Le 25/11/2010, à 14:07

Certainement, tout comme la cryptographie... C'est pour ça que je me suis intéressé à agrep avant de commencer pyhton (parce que python ça a l'air vraiment puissant.)

Et pour l'instant, pour décoder un message, agrep est mon ami pour trouver la forme de cryptage puis la clé (qui sont souvent simples pour les exemples) en repérant des formes communes, et enfin un peu de bash pour convertir le message.

Et puis c'est un bon outil, du reste, je pense l'incure dans des scripts avec des paramètres très chiants... Vu que je suis un peu dyslexique c'est le genre de truc utile.

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 22/01/2010, à 18:20

Expression régulière avec au moins 1 erreur toléré ?

#2 Le 22/01/2010, à 18:36

Re : Expression régulière avec au moins 1 erreur toléré ?

#3 Le 22/01/2010, à 18:49

Re : Expression régulière avec au moins 1 erreur toléré ?

#4 Le 22/01/2010, à 20:28

Re : Expression régulière avec au moins 1 erreur toléré ?

#5 Le 22/01/2010, à 20:43

Re : Expression régulière avec au moins 1 erreur toléré ?

#6 Le 22/01/2010, à 20:45

Re : Expression régulière avec au moins 1 erreur toléré ?

#7 Le 22/01/2010, à 20:51

Re : Expression régulière avec au moins 1 erreur toléré ?

#8 Le 22/01/2010, à 20:55

Re : Expression régulière avec au moins 1 erreur toléré ?

#9 Le 22/01/2010, à 21:04

Re : Expression régulière avec au moins 1 erreur toléré ?

#10 Le 22/01/2010, à 22:20

Re : Expression régulière avec au moins 1 erreur toléré ?

#11 Le 22/01/2010, à 23:03

Re : Expression régulière avec au moins 1 erreur toléré ?

#12 Le 22/01/2010, à 23:29

Re : Expression régulière avec au moins 1 erreur toléré ?

#13 Le 22/01/2010, à 23:37

Re : Expression régulière avec au moins 1 erreur toléré ?

#14 Le 22/01/2010, à 23:44

Re : Expression régulière avec au moins 1 erreur toléré ?

#15 Le 22/01/2010, à 23:50

Re : Expression régulière avec au moins 1 erreur toléré ?

#16 Le 24/11/2010, à 13:16

Re : Expression régulière avec au moins 1 erreur toléré ?

#17 Le 24/11/2010, à 21:17

Re : Expression régulière avec au moins 1 erreur toléré ?

#18 Le 25/11/2010, à 05:24

Re : Expression régulière avec au moins 1 erreur toléré ?

#19 Le 25/11/2010, à 05:32

Re : Expression régulière avec au moins 1 erreur toléré ?

#20 Le 25/11/2010, à 10:51

Re : Expression régulière avec au moins 1 erreur toléré ?

#21 Le 25/11/2010, à 14:07

Re : Expression régulière avec au moins 1 erreur toléré ?

Pied de page des forums