Discussion :

[Jasmine80]

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 :

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
# 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,

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

[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,

[iblis]

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 :

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

[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,