recherche de motifs imparfaits

**Jasmine80** · 21/12/2007, 12h02

Bonjour,

J'ai un problème et je ne sais pas comment le résoudre d'une façon simple.
J'ai une séquence et j'y recherche un motif mais j'accepte que dans ce motif il y ait quelques lettres de différence.
Y a-t'il plus simple que de tester tous les motifs possibles par des expressions régulières?

Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
my $Seq = "GCCAGCAGGATCTGGTGGACTACTCGCCGGTCAGCGAAAAACACCTTGCCGACGGCATGACGGTCGGCGA";
my $Amorce "GGTGGACTACTCGCC";
# recherche avec 2 mismatch
/..TGGACTACTCGCC/
/G..GGACTACTCGCC/
/GG..GACTACTCGCC/
# mais aussi
/.GT.GGACTACTCGCC/
/.GT.GACTACTCGCC/
/.GTG.ACTACTCGCC/

Je pourrais également faire glisser une fenêtre de la taille de mon motif sur la séquence et calculer un score entre celle-ci et le vrai motif.

Quelles serait la meilleure approche?

Merci,

Jasmine,

**Gardyen** · 21/12/2007, 15h01

euh je pense que tu cherches à réinventer la roue là non ?

tu dois avoir la possibilité d'utiliser des implémentations de l'algo smith-watermann, comme par exemple pSW

**Jasmine80** · 21/12/2007, 15h44

Merci mais la matrice blosum62 est pour les protéines et moi j'analyse de l'ADN. Il existe peut-être une fonction similaire pour l'ADN, je vais regarder.
"pSW is an Alignment Factory for protein sequences. It builds pairwise alignments using the Smith-Waterman algorithm."

Jasmine,

**Gardyen** · 21/12/2007, 16h04

désolé c'était la fête du groupe hier soir et je n'ai pas les yeux en face des trous aujourd'hui

reste que cela doit exister

bon courage !

**Schmorgluck** · 21/12/2007, 16h49

J'ai trouvé un moyen d'y arriver en Perl 5.10, avec les nouvelles fonctionnalités des regex, en l'occurence le verbe FAIL (pour être tout à fait franc, ça me donnait un prétexte pour m'amuser avec).
Enfin, un moyen... disons que je suis sur une piste, quoi.
Pour l'amorce que tu donnes :

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
my $match;
my @adequations;
$Seq=~m/
(?{$match=0})
(?>G(?{$match++})|.)
(?>G(?{$match++})|.)
(?>T(?{$match++})|.)
(?>G(?{$match++})|.)
(?>G(?{$match++})|.)
(?>A(?{$match++})|.)
(?>C(?{$match++})|.)
(?>T(?{$match++})|.)
(?>A(?{$match++})|.)
(?>C(?{$match++})|.)
(?>T(?{$match++})|.)
(?>C(?{$match++})|.)
(?>G(?{$match++})|.)
(?>C(?{$match++})|.)
(?>C(?{$match++})|.)
(?{push @adequations,$match})
(*FAIL)
/x;

Au terme de quoi je me retrouve avec un tableau contenant le nombre de caractères correspondants trouvés à chaque position testée.
Si je l'imprime, j'obtiens :

4
4
3
3
5
6
2
2
5
2
7
3
3
15
3
3
7
4
4
0
4
5
2
3
3
5
1
3
6
4
5
4
6
3
5
8
2
3
5
3
1
3
3
5
3
0
7
4
1
5
6
5
1
6
6
3

On trouve en 14ème position une adéquation maximale, 15, qui correspond à une reconnaissance complète.
Je bute encore sur la façon de procéder pour générer la regex dynamiquement à partir de l'amorce.
De plus, je ne suis même pas sûr que mon idée n'est pas totalement stupide, mais je m'amuse bien. Je continue à travailler dessus.

**Schmorgluck** · 21/12/2007, 17h16

Trouvé ! Voici ce que ça donne sous forme de sous-programme :

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
sub matchsequences($$)
{
  use re 'eval';
  my ($sequence, $amorce)=@_;
  my $pre_regex;
# on transforme l'amorce en un ensemble de groupements atomiques de la forme (?>X(?{$match++})|.)
# ce qui fait que $match sera incrémenté à chaque correspondance trouvée
# mais qu'une non-correspondance n'empêche pas la comparaison de se poursuivre.
  foreach my $char (split //, $amorce)
  {
    $pre_regex.= "(?>$char(?{\$match++})|.)";
  }
 
  my $match;
  my @adequations;
  $sequence=~m/
    (?{$match=0}) #on initialise ou réinitialise $match
    $pre_regex
    (?{push @adequations,$match}) #on ajoute la valeur de $match à la liste
    (*FAIL) #on force l'échec pour reprendre à zéro
  /x;
  return @adequations;
}

En fait, j'avais oublié de mettre use re 'eval', du coup ça marchait moyen pour automatiser.
Donc, ce sous-programme prend la séquence et l'amorce en arguments, et retourne la liste des niveaux de correspondance.

Alors bien sûr, tu n'as peut-être pas encore la possibilité d'utiliser Perl 5.10 et il vaut sans doute mieux chercher autre chose. N'empêche, je me suis bien amusé.

**Schmorgluck** · 21/12/2007, 17h32

Mmmh, je viens de lire la page de pSW, et je vais peut-être dire une ânerie, mais j'ai l'impression que, même s'il y est question spécifiquement de protéines, il n'est indiqué nulle part la forme que doivent prendre les séquences. Si ça se trouve ce sont juste des chaînes de caractères, auquel cas rien n'empêche d'utiliser ces fonctions pour des séquences de nucléotides, ça m'a l'air plus ou moins isomorphe, avec juste un vocabulaire plus restreint.

Maintenant, je ne suis pas un spécialiste et je me mets peut-être le doigt dans l'oeil, mais ça vaut peut-être le coup d'essayer.

**Jasmine80** · 22/12/2007, 08h15

Bonjour,

Merci pour votre aide à tous les deux.

Code :

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

(?>G(?{$match++})|.)

Pourrais-tu m'expliquer ce que cela signifie s'il te plait et me donner un lien vers l'ensemble des explications de ce type d'expressions régulières. Cela ne ressemble pas au ExpReg classique, comment nomme t'on ce type de code?

Pour ce qui est de pSW en fait l'ADN est composé de 4 nucléotides et les protéines de 20 acides aminés. Les matrices utilisées sont donc différentes car elles donnent des scores pour le passage d'un nucléotide vers un autre ou alors en ce qui concerne les protéines, d'un acide aminé vers un autre ce qui est totalement différent au niveau probabilités et scores utilisés. La matrice blosum62 utilisée pour des protéines ne peut pas l'être pour de l'ADN ... maintenant il est peut être possible d'aller changer la matrice utilisée en modifiant la fonction.
Il me faut une matrice ne contenant que des 1 (correspondance) et des 0 (différence). Je veux travailler avec un score d'identité et non de similarité comme le ferait blosum62.

blosum62
http://www.uky.edu/Classes/BIO/520/B...W/blosum62.htm

Merci,

Jasmine,

**Leishmaniose** · 24/12/2007, 16h44

sinon il y a ça :

http://www.ncbi.nlm.nih.gov/sutils/e-pcr/

Sauf si je n'ai pas bien saisi

, cet outil permet de chercher les sites d'amorçage en introduisant aussi bien des mismatch que des gaps

Moi je l'ai installé en local pour l'adapter à mes banques de séquences... et je l'ai même interfacé en perl, ce qui m'a permis d'executer le programme à partir du script avec mes paramètres puis de récupérer l'output et d'en faire ce que je veux !!!

A vous de juger

**Schmorgluck** · 26/12/2007, 16h10

Envoyé par Jasmine80

Bonjour,

Code :

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

(?>G(?{$match++})|.)

Pourrais-tu m'expliquer ce que cela signifie s'il te plait et me donner un lien vers l'ensemble des explications de ce type d'expressions régulières. Cela ne ressemble pas au ExpReg classique, comment nomme t'on ce type de code?

Il s'agit d'exécution de code à l'intérieur des regex. C'est assez délicat, et je ne maîtrise pas encore. Je vais essayer de trouver de la doc en ligne. Apparemment il n'y a rien à ce sujet dans la FAQ ni dans les cours. J'ai trouvé ça dans "Maîtrise des expressions régulières" 2ème édition.
D'abord, l'ensemble est englobé dans un groupement atomique avec (?>...), qui fait que ce qui est reconnu par son contenu n'est jamais restitué au cours de la tentative de reconnaissance : ça passe ou ça casse. J'avais bêtement tenté dans un premier temps avec de simples parenthèses non-capturantes, mais du coup le moteur de regex tentait toutes les combinaisons, ce qui n'était pas l'intérêt du truc.
À l'intérieur de ce groupement atomique, il y a deux parties alternatives, donc. La première reconnait le caractère recherché et, si c'est le cas, exécute le bloc (?{$match++}) qui incrémente la variable $match. Si le caractère n'est pas reconnu, c'est la deuxième alternative qui est utilisée, qui reconnait forcément grace au point, et qui n'exécute pas d'incrémentation.
Au final, une fois tous les caractères testés, un bloc de code ajoute la valeur de $match à la liste @adequations, puis FAIL force l'échec de la regex, qui reprend à zéro (grâce aux groupements atomiques) en décalant d'un caractère sur la chaîne, et en réinitialisant $match.

Pour ce qui est de pSW en fait l'ADN est composé de 4 nucléotides et les protéines de 20 acides aminés. Les matrices utilisées sont donc différentes car elles donnent des scores pour le passage d'un nucléotide vers un autre ou alors en ce qui concerne les protéines, d'un acide aminé vers un autre ce qui est totalement différent au niveau probabilités et scores utilisés. La matrice blosum62 utilisée pour des protéines ne peut pas l'être pour de l'ADN ... maintenant il est peut être possible d'aller changer la matrice utilisée en modifiant la fonction.

Oui, c'est ce qui m'étonne un peu : qu'il n'y ait pas, pour deux problèmes aussi proches, une couche d'abstraction permettant de passer aisément de l'un à l'autre.

Il me faut une matrice ne contenant que des 1 (correspondance) et des 0 (différence). Je veux travailler avec un score d'identité et non de similarité comme le ferait blosum62.

Ah, je vois, donc mon programme fournissant des nombre de 0 à 15 (dans le cas d'une amorce à 15 nucléotides) ne convient pas. Je vais tacher de le modifier.
Si j'ai bien compris, ce que tu voudrais, c'est un tableau de tableaux, chaque tableau intérieur étant une liste de 1 et de 0.

Je vais y réfléchir, mais il restera le problème que ma solution est basée sur Perl 5.10. Il faudra peut-être songer à une solution sans regex.

recherche de motifs imparfaits

Langage Perl

Vue hybride

Discussions similaires

Partager

Partager