Matrice distances hamming chaine 0/1

Postez ici vos questions, réponses, commentaires ou suggestions - Les sujets seront ultérieurement répartis dans les archives par les modérateurs

Modérateur : Groupe des modérateurs

Oriane Moyne
Messages : 17
Enregistré le : 20 Oct 2015, 15:50

Matrice distances hamming chaine 0/1

Messagepar Oriane Moyne » 24 Nov 2016, 13:18

Bonjour à tous,

Je n'arrive pas à résoudre ce casse-tête.

J'ai une matrice comportant des 0 et des 1. Nombre de lignes (individus) = N, nombre de caractères dans la chaine 0/1 = m.
Extrait :

Code : Tout sélectionner

head(mat)
      V1                              V2
A 0001011101001010011010100010110
B 0010101110011111111111100110111
C 0110011101101111010110010111011
D 0110011101101011010111010111011
E 0110011101101101010111010110011
F 0101101011101100101110110010110


Je veux comparer les chaines de 0/1 entre elles (la position dans la chaine est importante) afin d'obtenir une matrice des différences entre les profils 0/1 pour chaque individu. C'est-à-dire que si pour une position donnée, on a "1" pour l'individu A et "0" pour B (ou inversement), cela compte pour une différence entre A et B. La matrice que je cherche à construire contiendrait le nombre de différences obtenues en comparant tous les individus 2 à 2.

La matrice doit donc être symétrique, de dimensions N, N (nombre d'individus en ligne et colonne, comparés deux à deux).

Voici ce que j'ai essayé :

Code : Tout sélectionner

mat_diff<-matrix(0,nrow=N, ncol=N)

fun_a <- function(x){(str_split_fixed(x,"", n=m))} #pour découper ma chaine de caractères
fun_b <- function(x){(str_split_fixed(x,"", n=m))}

d <- 0

for(i in 1:N-1){
     
  aa <- fun_a(mat_pfge$bands[i]) #découpe des chaines de caractères, du premier à l'avant-dernier

for(i in 1:N-1){
 
  aa <- fun_a(mat_pfge$bands[i])
 
  for(j in (i+1):N){
   
        bb <- fun_b(mat_pfge$bands[j])
       
        for (k in 1:m){
                d <- d + match(aa[i,k], bb[j,k])
            }
         
            mat_diff[i,j] <- m-d
            mat_diff[j,i] <- m-d
        }
                     
             }


Et R me retourne le message d'erreur suivant :
Error in bb[j, k] : subscript out of bounds


Bref, je suis totalement perdue dans mon code !

Est-ce que quelqu'un pourrait m'aider ?

Gabriel Terraz
Messages : 591
Enregistré le : 26 Sep 2011, 15:11

Re: Matrice distances hamming chaine 0/1

Messagepar Gabriel Terraz » 24 Nov 2016, 15:55

Salut,
Voici une idée :

D'abord le jeu de données :

Code : Tout sélectionner

df <- data.frame(replicate(5, paste(sample(0:1,20,rep=T), collapse="")),
   row.names= LETTERS[1:5],stringsAsFactors = FALSE)
names(df) <- "evenements"
head(df)
            evenements
A 10000111000110110111
B 11111000111111111111
C 11110111010010001100
D 10001010011010101000
E 11001001001101011011


Puis le code proprement dit :

Code : Tout sélectionner

st <- sapply(strsplit(df$evenements, ""), as.numeric)
head(st)
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    1    1    1
[2,]    0    1    1    0    1
[3,]    0    1    1    0    0
[4,]    0    1    1    0    0
[5,]    0    1    0    1    1
[6,]    1    0    1    0    0

combn(1:5,2, function(x) 20 - sum(st[, x[1]] - st[, x[2]] == 0))
 [1] 12 10 11 10 12 11  8  9 14 11

Oriane Moyne
Messages : 17
Enregistré le : 20 Oct 2015, 15:50

Re: Matrice distances hamming chaine 0/1

Messagepar Oriane Moyne » 25 Nov 2016, 15:55

Bonjour,

Et merci pour votre réponse.
J'ai essayé votre solution, qui marche très bien... dans un premier temps !

Code : Tout sélectionner

df <- data.frame(replicate(5, paste(sample(0:1,20,rep=T), collapse="")),
                 row.names= LETTERS[1:5],stringsAsFactors = FALSE)

names(df) <- "evenements"
head(df)

N <- nrow(df)
m <- nchar(df$evenements[1])

st <- sapply(strsplit(df$evenements, ""), as.numeric)
head(st)
st <- aperm(st) # Je comprends mieux dans ce sens
head(st)
head(st)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20]
[1,]    1    0    1    0    1    0    0    1    1     0     0     0     1     1     1     0     1     1     1     1
[2,]    1    1    0    0    0    1    1    0    0     0     0     0     0     1     1     0     0     0     0     1
[3,]    1    1    0    1    1    1    1    1    0     0     1     1     0     0     1     0     0     0     1     0
[4,]    1    0    0    0    1    0    1    0    0     0     1     0     0     0     0     1     1     0     1     1
[5,]    1    0    1    1    1    1    1    0    1     0     0     0     0     0     1     1     1     1     0     0


Puis la fonction :

Code : Tout sélectionner

differences <- combn(1:N,2, function(x) m - sum(st[x[1],] - st[x[2],] == 0)) #vu que je travaille en ligne, j'ai inversé l'indexation
differences
[1] 11 13 10  9  8  9 10  9 10  9


Dans le résultat, "11" correspond bien au nombre de différences entre les lignes 1 et 2, "13" aux différences entre les lignes 1 et 3. Tout va bien !

Mais du coup à quoi correspondent les st[x[1],] et st[x[2],] de la fonction ? Ne servent-ils pas à cibler la comparaison sur les lignes 1 et 2 ?

En tout cas le résultat me plait bien, il faut juste que j'arrive à intercaler des "0" tous les N-1 dans le vecteur "differences" pour obtenir ma matrice finale...

Merci pour tout !

Gabriel Terraz
Messages : 591
Enregistré le : 26 Sep 2011, 15:11

Re: Matrice distances hamming chaine 0/1

Messagepar Gabriel Terraz » 25 Nov 2016, 18:02

Salut,
Pour finir de répondre à ton problème, sauf erreur de ma part :

Code : Tout sélectionner

mat <- matrix(0, ncol=5,nrow=5)
mat[lower.tri(mat)] <- differences

mat <- t(mat)
mat[lower.tri(mat)] <- differences
mat
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    8   16    9    5
[2,]    8    0   10    9    7
[3,]   16   10    0   11   15
[4,]    9    9   11    0   10
[5,]    5    7   15   10    0


En ce qui concerne ta question à propos de l'indexation

Code : Tout sélectionner

differences <- combn(1:N,2, function(x) m - sum(st[x[1],] - st[x[2],] == 0))


La fonction combn() te renvoie une paire de nombre, c'est donc un vecteur de longueur 2, qu'on utilise dans la fonction anonyme qui suit.
Dans la fonction anonyme ce vecteur est appelé x mais on aurait pu aussi mettre n'importe quoi.
Dans cette fonction on veut choisir deux lignes de la matrice st, les index de ces lignes sont dans x, un en position 1 et l'autre en position deux

Code : Tout sélectionner

combn(1:N, 2, simplify = F, function(nimportequoi) nimportequoi)
[[1]]
[1] 1 2

[[2]]
[1] 1 3

[[3]]
[1] 1 4

[[4]]
[1] 1 5

[[5]]
[1] 2 3

[[6]]
[1] 2 4

[[7]]
[1] 2 5

[[8]]
[1] 3 4

[[9]]
[1] 3 5

[[10]]
[1] 4 5


Je suis pas totalement convaincu par la clarté de mon explication...

Oriane Moyne
Messages : 17
Enregistré le : 20 Oct 2015, 15:50

Re: Matrice distances hamming chaine 0/1

Messagepar Oriane Moyne » 16 Déc 2016, 16:13

Bonjour,

N'ayant pas vu votre réponse, j'ai finalement trouvé (avec un peu d'aide !) une solution bis :

Code : Tout sélectionner

data <- data.frame(cbind(LETTERS[1:5], replicate(5, paste(sample(0:1,20,rep=T), collapse=""))))
data[,2] <-as.character(data[,2])
data
  X1                   X2
1  A 01010011100111011011
2  B 01111101010010010110
3  C 11000101001001110110
4  D 01001100011100100011
5  E 11111110000100111001

Code : Tout sélectionner

L <- data[,1]  #Labels
SQ <- data[,2] #sequence

N <- length(SQ)   #total number of profiles
m <- nchar(SQ[1]) #profile length

DSTMAT <- matrix(0, nrow=N, ncol=N)

Code : Tout sélectionner

for(i in 1:N){
  a <- substring(SQ[i],1:m,1:m)
 
  for(j in 1:N){
    b <- substring(SQ[j],1:m,1:m)
   
    d <- 0
    for(k in 1:m){
      d <- d + 1*(identical(a[k],b[k]))
    }
    DSTMAT[i,j] <- m - d
  }
}

Code : Tout sélectionner

DSTMAT

     [,1] [,2] [,3] [,4] [,5]
[1,]    0   10   12    9   10
[2,]   10    0    8   13   10
[3,]   12    8    0   13   10
[4,]    9   13   13    0   11
[5,]   10   10   10   11    0


Merci en tout cas pour votre aide !

François Bonnot
Messages : 537
Enregistré le : 10 Nov 2004, 15:19
Contact :

Re: Matrice distances hamming chaine 0/1

Messagepar François Bonnot » 04 Jan 2017, 07:34

Bonjour,
Autre solution (st étant l'objet créé plus haut avec les profils en colonne) :

Code : Tout sélectionner

as.matrix(dist(t(st),method="manhattan"))
François


Retourner vers « Questions en cours »

Qui est en ligne

Utilisateurs parcourant ce forum : Google [Bot] et 1 invité