modifications multiples dans une séquence

Version imprimable

Bonjour,

J'aimerais savoir comment résoudre mon problème de façon la plus optimale possible. Excepté en faisant une série de boucles, je ne vois pas comment faire.
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 # Récupérer toutes les combinaisons possibles # GtcgggtacggGaat # GtcgggtacggTaat # AtcgggtacggGaat # AtcgggtacggTaat my $Sequence = "RtcgggtacggKaat"; my %Correspondances = ( 'R' => ["G", "A"], 'K' => ["G", "T"], 'S' => ["G", "C"], 'W' => ["A", "T"], 'M' => ["A", "C"], 'Y' => ["T", "C"], 'D' => ["G", "A", "T"], 'V' => ["G", "A", "C"], 'B' => ["G", "T", "C"], 'H' => ["A", "T", "C"], 'N' => ["A", "T", "C", "G"], ); my @CompteDeg = $Sequence =~ /[RKSWMYDVBHN]/ig;
J'ai donc la séquence RtcgggtacggKaat et j'aimerais remplacer le R et le K par leurs valeurs en récupérant toutes les combinaisons possibles (4 ici).
# GtcgggtacggGaat
# GtcgggtacggTaat
# AtcgggtacggGaat
# AtcgggtacggTaat

Merci beaucoup,

Jasmine,

19/02/2008, 12h34
iblis

Bonjour.

D'un point de vue algorithmique, je ne vois pas d'autre solution qu'une exploration combinatoire de l'arbre. Personnellement, j'opterais plutôt pour une fonction récursive (sur la séquence), plus facile à penser de mon point de vue.

Une question ta séquence peut-elle arbitrairement longue (et en l'occurrence très très longue) ? Cela joue à mon avis dans le choix d'une solution optimale.
19/02/2008, 13h03
Jasmine80

Non, elle n'est jamais longue au grand maximum 70 lettres et les lettres dégénérées ne représentent jamais plus du cinquième de la séquence.

Merci,

Jasmine,

J'ai eu finalement un peu de temps pour regarder ton problème d'un peu plus près.

Pour être franc, je n'ai pas trouvé de solution récursive évidente. J'avais pensé qu'une réduction récursive de la séquence pour être à la fois économe et élégante. Mais je n'ai pas réussi et j'avoue n'avoir pas trop de temps pour chercher plus avant.

Voilà qui m'est venu naturellement. L'exploration est redondante, d'où le hash pur le résultat.

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
#!/usr/bin/perl
use strict;
use warnings;
 
my $sequence = "RtcgggtacggKaat";
 
my %associations =
(
        'R' => ["G", "A"],
        'K' => ["G", "T"],
        'S' => ["G", "C"],
        'W' => ["A", "T"],
        'M' => ["A", "C"],
        'Y' => ["T", "C"],
        'D' => ["G", "A", "T"],
        'V' => ["G", "A", "C"],
        'B' => ["G", "T", "C"],
        'H' => ["A", "T", "C"],
        'N' => ["A", "T", "C", "G"],
);
 
my %result;
 
sub reduce {
	my $seq = shift;
	$result{$seq}++	if ($seq !~ /[RKSWMYDVBHN]/);
	for my $meta (keys %associations) {
		next if ($seq !~ /$meta/);
		for my $base (@{$associations{$meta}}) {
				my $newseq = $seq; 
				$newseq =~ s/$meta/$base/; 
				reduce($newseq);
		}
	}
 
}
 
reduce($sequence);
print map {$_."\n"} keys %result;

20/02/2008, 08h42
Jasmine80

Merci beaucoup, cela fonctionne. C'est vraiment ingénieux comme script, je ne pense jamais à faire des fonctions récursives, je vais y remédier à l'avenir. Maintenant que j'ai bien compris comment cela fonctionne, je vais essayer de voir si il n'y a pas moyen de l'améliorer. Bonne journée.

Jasmine,