expression régulière et recherche de motifs se chevauchant

**Jasmine80** · 16/02/2010, 12h28

$for_rx et $rev_rx sont des listes de sous-séquences de ce type

$pcr_template contient une seule fois $for_rx puis plus loin un ou plusieurs $rev_rx.
J'aimerais récupérer tous les sous-séquences possibles comprises entre for et rev. Dans le cas où j'ai plusieurs rev, j'aurais donc plusieurs sous-séquences de taille différentes commençant toutes au même endroit (for).

Avez-vous une idée simple de la façon de procéder?

Voici une regexp dans le cas où les sous-séquences à récupérer seraient successives (et qui ne fonctionne donc pas dans mon cas)

Code :

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

my @prod_list = $pcr_template =~ m/((?:$for_rx).*(?:$rev_rx))/gi;

Merci,

**Philou67430** · 16/02/2010, 14h37

Pourrais-tu donner un exemple "simplifié" de valeur de $for_rx, $rev_rx, $pcr_template et du résultat attendu ?
Merci

(en attendant, je planche sur ce que je crois avoir compris)

**Jasmine80** · 16/02/2010, 14h45

Envoyé par Philou67430

Pourrais-tu donner un exemple "simplifié" de valeur de $for_rx, $rev_rx, $pcr_template et du résultat attendu ?
Merci

(en attendant, je planche sur ce que je crois avoir compris)

Merci pour ton aide

Code :

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

1
2
3
4
my $for_rx = 'AGTCGTGTCGTA|AGTAATGTCGTA|AGTCGTGTCGTA';
my $rev_rx = 'TGGCGTGATGTCGTA|GTCCGTATATGTCGT|TGCGTATGGTGCGAATA';
 
my $pcr_template = 'agtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGTggagagagata';

il faudrait récupérer :
AGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA
AGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGT

J'ai utilisé des majuscules et minuscules afin que la solution soit plus visuelle mais elles ne sont pas réparties de cette manière.

**Philou67430** · 16/02/2010, 14h51

A priori, en utilisant la récursion, ça devrait fonctionner :

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
#!/usr/bin/perl
 
use strict;
use warnings;
 
my $for_rx = 'AGTCGTGTCGTA|AGTAATGTCGTA|AGTCGTGTCGTA';
my $rev_rx = 'TGGCGTGATGTCGTA|GTCCGTATATGTCGT|TGCGTATGGTGCGAATA';
my $pcr_template = 'agtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGTggagagagata';
 
 
my @match = ();
sub check_pcr {
  my ($tmpl) = @_;
 
  if (my ($match, $next) = $tmpl =~ /(((?:$for_rx).*)(?:$rev_rx))/) {
    push @match, $match;
    check_pcr($next);
  }
}
 
check_pcr($pcr_template);
 
print map "[$_]\n", @match;

**Jasmine80** · 16/02/2010, 14h59

C'est super, merci beaucoup. J'ai du mal avec les récursions mais j'ai bien compris le fonctionnement de ton script.

**iblis** · 16/02/2010, 15h06

Tu dois pouvoir le faire par récursion, directement avec le moteur de regex.

En attendant, match globalement toutes les séquences qui finissent par $rev_rx (attention à ne pas être "gourmand" !) et ce à partir de $for_rx.

Code :

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

1
2
my @seqs = $pcr_template =~ /(.*?(?:$rev_rx))/g
    if $pcr_template =~ /$for_rx/g

Et là tu n'as plus qu'à assembler tes séquences pour avoir le cumul progressif.

Code :

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

1
2
my @cumul = ('');
for (@seqs) { push @cumul, $cumul[-1] .= $_ };

**iblis** · 16/02/2010, 15h18

J'ai vérifié avec tes données, cela fonctionne.

**Jasmine80** · 16/02/2010, 15h26

Envoyé par iblis

J'ai vérifié avec tes données, cela fonctionne.

Merci de t'intéresser à mon cas. C'est une bonne idée de penser à tout récupérer par petits morceaux puis à les assembler. J'ai dû un peu modifier ton script afin qu'il commence les séquences récupérées à partir de l'amorce sens ... le problème est que le dernier produit récupéré reste en double.

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
#!/usr/bin/perl
 
use strict;
use warnings;
 
 
my $for_rx = 'AGTCGTGTCGTA|AGTAATGTCGTA|AGTCGTGTCGTA';
my $rev_rx = 'TGGCGTGATGTCGTA|GTCCGTATATGTCGT|TGCGTATGGTGCGAATA';
 
my $pcr_template = 'agtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGTggagagagata';
 
my $for;
my @seqs = $pcr_template =~ /(.*?(?:$rev_rx))/g
    if ( ($for) = $pcr_template =~ /($for_rx)/ );
 
my @cumul = ('');
for (@seqs) { push @cumul, $cumul[-1] .= $_ };
 
# suppression du début de séquence inutile
map {$_ =~ s/^\w+($for)/$1/;} @cumul;
 
map {print "$_\n";} @cumul;

Je vais garder la solution de Philou67430, c'est plus élégant et ça semble plus propre.

**Philou67430** · 16/02/2010, 15h40

@iblis : en relisant (et même en voyant le résultat), je ne comprends pas comment cette ligne fonctionne :

Code :

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

1
2
my @seqs = $pcr_template =~ /(.*?(?:$rev_rx))/g
    if $pcr_template =~ /$for_rx/g

Pourquoi le if $pcr_template =~ /$for_rx/g réduit-il l'excursion dans la chaine $pcr_template ? (d'ailleurs, le modificateur /g semble inutile).

**Jasmine80** · 16/02/2010, 15h52

Envoyé par Philou67430

@iblis : en relisant (et même en voyant le résultat), je ne comprends pas comment cette ligne fonctionne :

Code :

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

1
2
my @seqs = $pcr_template =~ /(.*?(?:$rev_rx))/g
    if $pcr_template =~ /$for_rx/g

C'est pour récupérer tous les petits fragments de séquence contenant un $rev_rx. Dans l'exemple on récupère donc :

agtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA
tgagagatagatagtaGTCCGTATATGTCGT

Il faut ensuite récupérer à partir de $for pour obtenir

AGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA
tgagagatagatagtaGTCCGTATATGTCGT

puis concaténer ce début avec l'autre hit récupérer afin d'obtenir le second produit

AGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA
tgagagatagatagtaGTCCGTATATGTCGTtgagagatagatagtaGTCCGTATATGTCGT

C'est ce que je pense avoir compris, en tous cas cela fonctionne également.

**iblis** · 16/02/2010, 16h08

@Jasmine : tu as raison la solution de Philou est bien plus propre. Je voulais faire une expression récursive mais je n'ai pas réussi

. Et oui, ma façon d'assembler était très mal faite, pardon. Toujours bricolé mais mieux :

Code :

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

1
2
my $acc = '';
my @result = map { $acc .= $_; $acc } @seqs;

@Philou :

En fait on se positionne sur $for_rx (remarque le /g), afin d'éviter les séquences finissant en $rev_rx qui précèderaient $for_rx, ce que Jasmine ne veut pas.

Ensuite on capture toutes les séquences minimales (.*? pour ne pas être greedy) qui sont suivies par $rev_rx. Toujours grâce à /g. Et tu n'as pas besoin de \G, puisqu'on y est déjà.

**Philou67430** · 16/02/2010, 16h21

OK, j'ai compris : j'avais omis que lorsqu'une même chaine est utilisée consécutivement dans plusieurs recherches de pattern, la recherche commence là où s'est terminée la précédente. C'est en effet un cas que je pratique peu (différentes recherches consécutives dans une même chaine).

Cela dit, jasmine, comment doit se comporter le script si l'on trouve plusieurs pattern $for_rx avant des $rev_rx ? La recherche doit être greedy ou ungreedy ?

**iblis** · 16/02/2010, 16h47

La même approche mais récursive :

Code :

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

1
2
my @result = $pcr_template =~ /(.*?(?:$rev_rx)|\1(?:$rev_rx))/ig
  if $pcr_template =~ /$for_rx/g;;

**Philou67430** · 16/02/2010, 17h32

Tu es sûr que ça marche... j'obtiens pas le même résultat avec ta dernière version qu'avec les deux précédentes ?

Par ailleurs, pour être stricto-sensu équivalent à ma version, et à la demande de jasmine d'intégrer dans les extractions, le pattern de début, il faudrait écrire :

Code :

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

1
2
3
my @result = $pcr_template =~ /(.*?(?:$rev_rx)|\1(?:$rev_rx))/ig
  if my @first = $pcr_template =~ /($for_rx)/g;
@result = map $first[-1].$_, @result;

Mais j'ai un gros doute sur cette version...

**iblis** · 16/02/2010, 18h22

Ça a l'air d'être plutôt bon... ou alors j'ai mal compris ce qu'elle voulait.

Code :

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

1
2
3
4
5
my @result = $pcr_template =~ /(.*?(?:$rev_rx)|\1(?:$rev_rx))/ig
  if my @first = $pcr_template =~ /($for_rx)/g;
my $acc = shift @first;
@result = map { $acc .= $_; $acc } @result;
print map "[$_]\n", @result;

**iblis** · 16/02/2010, 18h24

Mais à vrai dire je préfère une solution plus explicite comme la tienne.

Je voulais utiliser des captures nommées mais je n'ai pas Perl 10 sur cette machine.

**Philou67430** · 16/02/2010, 18h39

Bah... bizarre, les résultats ne sont pas concordant avec les deux premières méthodes :

Le script :

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
#!/usr/bin/perl
 
use strict;
use warnings;
 
my $for_rx = 'AGTCGTGTCGTA|AGTAATGTCGTA|AGTCGTGTCGTA';
my $rev_rx = 'TGGCGTGATGTCGTA|GTCCGTATATGTCGT|TGCGTATGGTGCGAATA';
my $pcr_template = 'agtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGTggagagagata';
#my $pcr_template = 'agtgatagtacaAZGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGTggagaAGTAATGTCGTAgagata';
 
 
print "Méthode philou67\n";
 
my @match = ();
sub check_pcr {
  my ($tmpl) = @_;
 
  if (my ($match, $next) = $tmpl =~ /(((?:$for_rx).*)(?:$rev_rx))/) {
    push @match, $match;
    check_pcr($next);
  }
}
 
check_pcr($pcr_template);
 
print map "[$_]\n", @match;
 
print "Méthode iblis non récursive\n";
 
my @seqs = $pcr_template =~ /(.*?(?:$rev_rx))/g
    if $pcr_template =~ /$for_rx/g;
my @cumul = ('');
for (@seqs) { push @cumul, $cumul[-1] .= $_ };
print map "{$_}\n", @cumul;
 
print "Méthode iblis non récursive\n";
 
my @result = $pcr_template =~ /(.*?(?:$rev_rx)|\1(?:$rev_rx))/ig
  if my @first = $pcr_template =~ /($for_rx)/g;
my $acc = shift @first;
@result = map { $acc .= $_; $acc } @result;
print map "($_)\n", @result;

Le résultat :

Code bash :

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

1
2
3
4
5
6
7
8
9
10
11
$ ./match_between2.pl
Méthode philou67
[AGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGT]
[AGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA]
Méthode iblis non récursive
{ggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA}
{ggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGT}
{ggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGT}
Méthode iblis non récursive
(AGTAATGTCGTAagtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATA)
(AGTAATGTCGTAagtgatagtacaAGTAATGTCGTAggcagatgatagtacacacagatgatagtaTGCGTATGGTGCGAATAtgagagatagatagtaGTCCGTATATGTCGT)

Tu vois l'erreur ?

**iblis** · 16/02/2010, 19h06

Oui, tu as raison. Je vois le problème dans la regex.

**Jasmine80** · 17/02/2010, 08h38

Envoyé par Philou67430

Cela dit, jasmine, comment doit se comporter le script si l'on trouve plusieurs pattern $for_rx avant des $rev_rx ? La recherche doit être greedy ou ungreedy ?

On trouve toujours un seul $for_rx qui précède un ou plusieurs $rev_rx.

Un grand merci à vous deux pour votre aide.

**Philou67430** · 17/02/2010, 09h57

Envoyé par iblis

Oui, tu as raison. Je vois le problème dans la regex.

Vraiment ?
En fait, à part le paramètre /i qui n'est pas utile, la regexp est sans doute bonne. C'est le fait de vouloir récupérer le premier pattern dans le if (affectation de @first), qui "ré-initialise" la position du moteur de recherche dans la chaine (le pos() ou encore \G), et retourne alors le début de cette chaine dans la recherche des patterns de fin.

Ta première regexp, sans ma modif, et avec la dernière construction des séquences résultats me semble la plus valide des solutions sans utiliser de fonction récursive. Il faut juste récupérer le début de chaine "à part".

Ceci semble fonctionner comme mon exemple:

Code :

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

1
2
3
4
5
6
7
8
if ($pcr_template =~ /($for_rx)/g) {
  my $first = $1;
  print "pos=".pos($pcr_template)."\n";
  my @result2 = $pcr_template =~ /\G(.*?(?:$rev_rx))/g;
  my $acc2 = $first;
  @result2 = map { $acc2 .= $_; $acc2 } @result2;
  print map "/$_/\n", @result2;
}

Il est amusant d'ailleurs de constater que l'instruction my $first = $1; ne perturbe pas la position dans la chaine de recherche, alors que l'affectation "en passant" dans le if la reset (if my @first = $pcr_template =~ /($for_rx)/g)
Simple curiosité, tu as une idée de la raison, je n'ai rien trouvé en feuilletant la doc ?

expression régulière et recherche de motifs se chevauchant

Langage Perl

Discussions similaires

Partager

Partager