comparaison de chaînes de caractères

**Jasmine80** · 25/07/2007, 12h05

Bonjour,

J'aimerais savoir comment optimiser ce script. Je sais qu'imbriquer des boucles n'est pas l'ideal. J'ai pensé à la fonction map sur mes array mais je ne vois pas comment l'utiliser.
Mon programme compare des chaines de caractères et compte de nombre de lettres communes (la position est importante).

par exemple

ATCGC
ACCGT

3 lettres identiques à la même position

J'aimerais aussi garder les informations récupérées dans un tableau ayant pour clé chacune des chaînes de caractères analysées et en valeur la liste des séquences étant identique à une lettre près. Est-ce possible sans devoir passer par un objet complexe?

Merci,

Jasmine,

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
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/local/bin/perl
 
 
use strict;
use warnings;
use Data::Dumper;
 
#----------------------------------------- IdentiteAmorces.pl -----------------------------------------#
 
 
# contient en clé la séquence et en valeur son numéro de référence
my %Hash =      (
                        "ATGTCCTGTCCGTG" => 0,
                        "ATCTCCTGTCCGTG" => 1,
                        "ATGTCCTGGACGTG" => 2,
                        "ATCTCCTGGACGTG" => 3,
                        "ATCTCCTGTCCGTA" => 4
                );
 
# Pour chaque couple possible d'amorces, calcul du nombre de nucléotides commun
# Chaque amorce mise dans une array par un split @Amorce_ref et @Amorce
 
my %Hash_Identite;
 
foreach my $Seq_ref (keys %Hash)
{
        my @Amorce_ref = split ("", $Seq_ref);
        my @Liste_Amorces; # liste des amorces ayant un pourcentage d'identité supérieur au seuil
        foreach my $Seq (keys %Hash)
        {
                unless ($Seq eq $Seq_ref)
                {
                        my @Amorce = split ("", $Seq);
                        my $Identite = 0; # compte des nucléotides communs
                        for (my $i=0; $i<@Amorce_ref; $i++)
                        {
                                if ($Amorce_ref[$i] eq $Amorce[$i])
                                {
                                        $Identite++;
                                }
                        }
                        # print "$Seq_ref\t$Seq\tidentité : $Identite\n";
                        my $Seuil = @Amorce_ref-2;
                        print "Seuil : $Seuil\n";
                        if ($Identite>=$Seuil){push (@Liste_Amorces, $Seq)}
                }
        }
        my $Ref_Liste_Amorces = \@Liste_Amorces;
        $Hash_Identite{$Seq_ref}= $Ref_Liste_Amorces;
}
 
print Dumper %Hash_Identite;
 
close;

**Woufeil** · 25/07/2007, 12h32

Bonjour,

Je vais te donner deux pistes : l'utilisation de la fonction substr (si tu veux te contenter de travailler sur les chaînes de caractère) et celle du module Set::Array (si tu veux passer par des tableaux).

Explore ces deux pistes et dis-nous si l'une d'elle te convient

**Jasmine80** · 25/07/2007, 14h21

Merci beaucoup, je vais explorer ces nouvelles pistes.

Jasmine,

**MarneusCalgarXP** · 25/07/2007, 14h55

Tu veux juste récupérer le nombre de lettres avec même valeur et même position ?

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
#!/usr/bin/perl
 
use strict;
use warnings;
 
my $sequence1 = 'ATCGC';
my $sequence2 = 'ACCGT';
 
my $common_letters_count = getCommonLettersCount($sequence1, $sequence2);
printf("[%s] et [%s] ont %d lettres en commun à des positions identiques\n", ($sequence1, $sequence2, $common_letters_count));
 
sub getCommonLettersCount
{
	my ($string1, $string2) = @_;
	my $length1 = length($string1);
	my $length2 = length($string2);
	my $minlength = ($length1 > $length2) ? $length2 : $length1;	
	my $count = 0;
 
	for (my $pos = 0; $pos < $minlength; $pos++) {
		my $char1 = substr($string1, $pos, 1);
		my $char2 = substr($string2, $pos, 1);
		$count += ($char1 eq $char2);
	}
 
	return $count;
}

**Jasmine80** · 25/07/2007, 16h04

Tu veux juste récupérer le nombre de lettres avec même valeur et même position ?

Oui, exactement. Je veux regrouper ensemble celles ne divergeant que d'une seule lettre. J'y arrive en utilisant des boucles foreach.

Je construis donc un tableau complexe contenant en les informations
$TabComp_Identite{$Num_seq}{$Seq_ref} = @Liste_amorces_similaires

@Liste_amorces_similaires contient donc toutes mes séquences ne différent que d'une seule lettre par rapport à ma séquence de référence ($Seq_ref).
=> c'est bien ce que je veux

Merci J'ai remplacé mon

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
foreach my $Seq_ref (keys %Hash)
{
        my @Amorce_ref = split ("", $Seq_ref);
        my @Liste_Amorces; # liste des amorces ayant un pourcentage d'identité supérieur au seuil
 
        foreach my $Seq (keys %Hash)
        {
                unless ($Seq eq $Seq_ref)
                {
                        my @Amorce = split ("", $Seq);
                        my $Identite = 0; # compte des nucléotides communs
                        for (my $i=0; $i<@Amorce_ref; $i++)
                        {
                                if ($Amorce_ref[$i] eq $Amorce[$i])
                                {
                                        $Identite++;
                                }
                        }
                        # print "$Seq_ref\t$Seq\tidentité : $Identite\n";
                        my $Seuil = @Amorce_ref-2;
                        if ($Identite>$Seuil)
                        {push (@Liste_Amorces, $Seq);}
                }
 
        }
        #foreach my $val (@Liste_Amorces){print $val."\n\n";}
        $TabComp_Identite{$Hash{$Seq_ref}}{$Seq_ref}= \@Liste_Amorces;
        $Hash_Identite{$Seq_ref}=\@Liste_Amorces;
}

par ta fonction

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
foreach my $Seq_ref (keys %Hash)
{
        my @Amorce_ref = split ("", $Seq_ref);
        my @Liste_Amorces; # liste des amorces ayant un pourcentage d'identité supérieur au seuil
 
        foreach my $Seq (keys %Hash)
        {
                unless ($Seq eq $Seq_ref)
                {
                        my $Identite = getCommonLettersCount($Seq_ref, $Seq);
                        my $Seuil = @Amorce_ref-2;
                        if ($Identite>$Seuil)
                        {push (@Liste_Amorces, $Seq);}
                }
 
        }
        #foreach my $val (@Liste_Amorces){print $val."\n\n";}
        $TabComp_Identite{$Hash{$Seq_ref}}{$Seq_ref}= \@Liste_Amorces;
        $Hash_Identite{$Seq_ref}=\@Liste_Amorces;
}

Mais ce que j'avais écrit

Code :

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

1
2
3
4
5
6
7
8
9
                        my @Amorce = split ("", $Seq);
                        my $Identite = 0; # compte des nucléotides communs
                        for (my $i=0; $i<@Amorce_ref; $i++)
                        {
                                if ($Amorce_ref[$i] eq $Amorce[$i])
                                {
                                        $Identite++;
                                }
                        }

était-il plus mauvais que la fonction que tu as faite?

Merci pour votre aide,

Jasmine,

**Jasmine80** · 25/07/2007, 16h08

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#!/usr/local/bin/perl
 
 
use strict;
use warnings;
use Data::Dumper;
 
#----------------------------------------- IdentiteAmorces.pl -----------------------------------------#
 
 
# contient en clé la séquence et en valeur son numéro de référence
my %Hash =      (
                        "ATGTCCTGTCCGTG" => 0,
                        "ATCTCCTGTCCGTG" => 1,
                        "ATGTCCTGGACGTG" => 2,
                        "ATCTCCTGGACGTG" => 3,
                        "ATCTCCTGTCCGTA" => 4
                );
 
# Pour chaque couple possible d'amorces, calcul du nombre de nucléotides commun
# Chaque amorce mise dans une array par un split @Amorce_ref et @Amorce
 
my %Hash_Identite;  # clef : séquence de référence et en valeur les amorces étant une identité la plus proche
my %TabComp_Identite; # $TabComp_Identite{$Num_seq}{$Seq_ref} = @ListeAmorcesAssociees
 
 
foreach my $Seq_ref (keys %Hash)
{
        my @Amorce_ref = split ("", $Seq_ref);
        my @Liste_Amorces; # liste des amorces ayant un pourcentage d'identité supérieur au seuil
 
        foreach my $Seq (keys %Hash)
        {
                unless ($Seq eq $Seq_ref)
                {
                        my $Identite = getCommonLettersCount($Seq_ref, $Seq);
                        my $Seuil = @Amorce_ref-2;
                        if ($Identite>$Seuil)
                        {push (@Liste_Amorces, $Seq);}
                }
 
        }
        #foreach my $val (@Liste_Amorces){print $val."\n\n";}
        $TabComp_Identite{$Hash{$Seq_ref}}{$Seq_ref}= \@Liste_Amorces;
        $Hash_Identite{$Seq_ref}=\@Liste_Amorces;
}
 
# $TabComp_Identite{$Num_seq}{$Seq_ref}
foreach my $Num_seq (keys %TabComp_Identite)
{
        foreach  my $Seq_ref (keys %{$TabComp_Identite{$Num_seq }})
        {
               my $Compte_Amorces_Associees =  @{$TabComp_Identite{$Num_seq }{$Seq_ref}};
	       print ("N° $Num_seq\t$Seq_ref => $Compte_Amorces_Associees amorces associées\n");
        }
}
 
 
 
# print Dumper %TabComp_Identite;
# print Dumper %Hash_Identite;
 
 
close;
 
 
sub getCommonLettersCount
{
	my ($string1, $string2) = @_;
	my $length1 = length($string1);
	my $length2 = length($string2);
	my $minlength = ($length1 > $length2) ? $length2 : $length1;
	my $count = 0;
 
	for (my $pos = 0; $pos < $minlength; $pos++) {
		my $char1 = substr($string1, $pos, 1);
		my $char2 = substr($string2, $pos, 1);
		$count += ($char1 eq $char2);
	}
 
	return $count;
}

Tableau
# $TabComp_Identite{$Num_seq}{$Seq_ref} = @ListeAmorcesAssociees

J'obtiens en sortie :
$Num_seq $Seq_ref => @ListeAmorcesAssociees amorces associées

N° 4 ATCTCCTGTCCGTA => 1 amorces associées
N° 1 ATCTCCTGTCCGTG => 2 amorces associées
N° 0 ATGTCCTGTCCGTG => 1 amorces associées
N° 3 ATCTCCTGGACGTG => 1 amorces associées
N° 2 ATGTCCTGGACGTG => 1 amorces associées

Maintenant, j'aimerais faire un tri afin de retrouver les amorces de références ayant le plus de séquences associées. Que la n°1 se retrouve en premier car elle a 2 amorces associées.
Quelle fonction puis-je utiliser?

Merci,

Jasmine,

**Jasmine80** · 25/07/2007, 16h14

Bonjour,

Je vais te donner deux pistes : l'utilisation de la fonction substr (si tu veux te contenter de travailler sur les chaînes de caractère) et celle du module Set::Array (si tu veux passer par des tableaux).

Explore ces deux pistes et dis-nous si l'une d'elle te convient

Je suis un peu à la bourre, j'ai le chef sur le dos afin d'avoir les résultats au plus vite , je cherche à terminer le programme et à l'occasion je l'optimiserai. Puis, c'est plus pour être méticuleuse car déjà ainsi quand je l'éxécute sur mes 300 amorces à tester il ne prend pas plus de 2 minutes à m'afficher le résultat.

Si j'utilise la fonction substr .... je vais également devoir passer par un ensemble de boucles. En quoi cela rendrait-il ce programme plus performant?

Merci,

Jasmine,

**MarneusCalgarXP** · 25/07/2007, 18h44

Envoyé par Jasmina

était-il plus mauvais que la fonction que tu as faite?

non, je ne pense pas qu'elle était plus mauvaise, c'était juste une autre solution, comme il en existe des tonnes en Perl (TIMTOWTDI

)

**MarneusCalgarXP** · 25/07/2007, 18h48

Envoyé par Jasmine80

Maintenant, j'aimerais faire un tri afin de retrouver les amorces de références ayant le plus de séquences associées. Que la n°1 se retrouve en premier car elle a 2 amorces associées.
Quelle fonction puis-je utiliser?

J'aurais tendance à te conseiller de construire une nouvelle hash indicée sur le nombre d'occurences...

**MarneusCalgarXP** · 25/07/2007, 19h07

Erf, je crois qu'en réalité tu n'utilises pas les bons outils : tu utilises une hash pour associer une valeur 0, 1, 2, 3, ce qui serait fait automatiqueement avec un tableau:

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
43
44
45
#!/usr/local/bin/perl
 
 
use strict;
use warnings;
use Data::Dumper;
 
#----------------------------------------- IdentiteAmorces.pl -----------------------------------------#
 
my %TabComp_Identite = ();
my %Sort_Hashmap = ();
 
 
# contient en clé la séquence et en valeur son numéro de référence
my @sequences = (
                        'ATGTCCTGTCCGTG' , # indice 0
                        'ATCTCCTGTCCGTG' , # indice 1
                        'ATGTCCTGGACGTG' , # indice 2
                        'ATCTCCTGGACGTG' , # indice 3
                        'ATCTCCTGTCCGTA' , # indice 4
);
 
foreach my $sequence_reference (@sequences)
{
        my $seuil = length($sequence_reference) - 2;
        my @Liste_Amorces = (); # liste des amorces ayant un pourcentage d'identité supérieur au seuil
 
        foreach my $sequence (@sequences) {
            next, if ($sequence eq $sequence_reference);
            my $identite = getCommonLettersCount($sequence_reference, $sequence);
            push (@Liste_Amorces, $sequence), if ($identite > $seuil);
        }
 
        $TabComp_Identite{$sequence_reference} = \@Liste_Amorces;
        $Sort_Hashmap{scalar(@Liste_Amorce)}{$sequence_reference} = 1;
}
 
# Impression avec tri par valeur
foreach my $count (reverse sort keys %Sort_Hashmap )
{
    foreach my $sequence ( keys %{ $Sort_Hashmap{$count} }) {
        print ("$sequence => $count amorces associées\n");
        # tu peux récupérer les séquences à l'aide de $TabComp_Identite{$sequence}
    }
}

J'ai pas d'interpréteur perl sur cet ordi, alors j'ai p'tet fait des erreurs, mais ca devrait tourner

**Jasmine80** · 26/07/2007, 09h12

Bonjour,

Oui cela fonctionne très bien merci. Je n'aime pas les array et je préfère les hash car je ne sais pas comment récupérer les valeurs des index. Avec les hash je peux accéder facilement aux valeurs de keys et de values. Si j'utilise une array

Code :

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

1
2
3
my @array = qw(...);
my $i = 0;
foreach my $val (@array){print "$i\t$val\n";$i++; }

Ce n'est pas très gracieux. Comment faire?

Par amorce de référence, je veux récupérer : son numéro et sa liste d'amorces associées.

Est-il préférable d'utiliser plus tableaux simples associés (hash) qu'un seul tableau complexe unique $TabComp_Identite{$Num_seq}{$Seq_ref} = \@Liste_Amorces? Quel nom porte ce dernier type de tableau?

Une dernière question:

Code :

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

my $minlength = ($length1 > $length2) ? $length2 : $length1;

Qu'est-ce que cela signifie?

Merci beaucoup,

Jasmine,

**Jasmine80** · 26/07/2007, 09h48

Voici la structure de mon tableau final

Code :

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

$TabComp_Identite{$Hash{$Seq_ref}}{$Seq_ref}= \@Liste_Amorces;

$VAR1 = '32';
$VAR2 = {
'TCGATTACGC' => [
'ACGATTACGC',
'TCGATTAAGC',
'TCGTTTACGC',
'TCGATAACGC',
'TCGATTTCGC'
]
};
$VAR3 = '127';
$VAR4 = {
'ACTATAACGC' => [
'ACTATATCGC',
'AGTATAACGC',
'GCTATAACGC',
'ACTTTAACGC',
'TCTATAACGC',
'ACGATAACGC'
]
};
$VAR5 = '90';
$VAR6 = {
'TCGAAATCGC' => [
'TCGTAATCGC',
'ACGAAATCGC'
]
};
$VAR7 = '276';
$VAR8 = {
'AGTTTAACGC' => [
'CGTTTAACGC',
'TGTTTAACGC',
'AGTATAACGC',
'AGTTAAACGC',
'AGATTAACGC',
'AATTTAACGC',
'ACTTTAACGC',
'AGTTTATCGC'
]
};

J'utilise

Code :

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

1
2
3
4
foreach my $Num_seq (sort { $a <=> $b } keys %TabComp_Identite)
{
        foreach  my $Seq_ref (keys %{$TabComp_Identite{$Num_seq }})
        {

Je vais essayer avec des array, comme tu le suggères, c'est plus simple pour le tri. Je vais autoincrémenter un $i afin de récupérer mes index.

Merci,

Jasmine,

**Jasmine80** · 26/07/2007, 10h17

Si j'ai un tableau complexe à plusieurs couches et que je veux trier en fonction de la dernière couche, il faut que je récupère les valeurs des clés du tableau dans une array ordonnées en fonction de ces valeurs de dernières couche.

... je pense que ma question est incompréhensible.

Pour
$TabComp_Identite{$Hash{$Seq_ref}}{$Seq_ref}= \@Liste_Amorces

Si je veux imprimer toutes les valeurs de ce tableau en fonction de la taille de @Liste_Amorces, il faut que crée une array contenant mes clés $Hash{$Seq_ref}} triées selon les valeurs de @Liste_Amorces.

Merci,

Jasmine,

**Jasmine80** · 26/07/2007, 10h52

Au sujet de la réponse de Woufeuil,

Bonjour,

Je vais te donner deux pistes : l'utilisation de la fonction substr (si tu veux te contenter de travailler sur les chaînes de caractère) et celle du module Set::Array (si tu veux passer par des tableaux).

Explore ces deux pistes et dis-nous si l'une d'elle te convient

J'ai regarder la fonction Set::Array que je ne connaissais pas. Je n'en vois pas trop l'utilté. La majorité des fonctions peuvent facilement être exéctuées sans faire appel à ce package.
Par contre j'ai remarqué :

unique() - Removes/returns non-unique elements from the list.

C'est intéressant ça. Je le garde dans un coin de ma mémoire, ça me servira peut être plus tard.

index(val) - Returns the index of the first element of the array object that contains val.

Et voila comment récupérer mes index à partir de mes valeurs. C'est justement la question que je me posais un peu plus haut.

Merci,

Jasmine,

**Woufeil** · 26/07/2007, 11h34

Envoyé par Jasmine80

Une dernière question:

Code :

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

my $minlength = ($length1 > $length2) ? $length2 : $length1;

Qu'est-ce que cela signifie?

Ah, l'opérateur ternaire ?: . Pas très joli, mais assez pratique je dois dire. C'est en fait un if-then-else déguisé. En fait, il marche comme ceci

Code :

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

condition ? code si condition vérifiée : code sinon

Donc dans ton cas, ta variable minlength recevra la valeur de $length1 si elle est plus petite que celle de $length2, cette dernière sinon.

Ensuite, si tu veux vraiment récupérer la liste des index, évite d'incrémenter une variable $i manuellement, fait plutôt

Code :

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

1
2
3
4
foreach my $i (1..$#array)
{
   #index : $i ; valeur :$array[$i] 
}

Pour Set::Array, honte à moi ! Ce n'est pas du tout ce que je voulais te conseiller, je voulais te conseiller Array::Compare et la méthode full_compare

full_compare \@ARR1, \@ARR2

Do a full comparison between two arrays.

Checks each individual column. In scalar context returns the number of columns that differ (zero if the arrays are the same). In list context returns an list containing the indexes of the columns that differ (an empty list if the arrays are the same).

Je pensais que tu voulais savoir les éléments qui différaient entre les deux tableaux. C'est ce que fait ce module. Je me suis trompé ?

**Jasmine80** · 26/07/2007, 12h43

Merci beaucoup pour votre aide. Maintenant le programme fait ce que je veux.
Bonne fin de semaine et bon week end,

Jasmine,

**MarneusCalgarXP** · 26/07/2007, 21h02

Envoyé par Woufeil

Ensuite, si tu veux vraiment récupérer la liste des index, évite d'incrémenter une variable $i manuellement, fait plutôt

Code :

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

1
2
3
4
foreach my $i (1..$#array)
{
   #index : $i ; valeur :$array[$i] 
}

Euh, pourquoi commence-tu ton indicage à 1 alors que le tableau commence à l'indice 0 ???

**Woufeil** · 27/07/2007, 09h47

Envoyé par MarneusCalgarXP

Euh, pourquoi commence-tu ton indicage à 1 alors que le tableau commence à l'indice 0 ???

Un oubli, tout simplement

comparaison de chaînes de caractères

Langage Perl

Discussions similaires

Partager

Partager