19 de agosto de 2010

Generar todas las posibles combinaciones posibles de n nucleótidos o aminoácidos

Erróneamente decimos que queremos generar todas las posibles 'combinaciones' de n letras, nucleótidos o aminoácidos cuando el término correcto sería 'variaciones con repetición' (Permutations-Variations-Combinations). Por ejemplo, las 16 posibles variaciones con repetición de 2 nucleótidos serían: AA, AC, AG, AT, CA, CC, CG, CT, GA, GC, GG, GT, TA, TC, TG, TT. El número de variaciones con repetición de n nucleótidos es 4^n y de n aminoácidos 20^n.

El siguiente código, es una adaptación de un código en PHP para generar todas las variaciones con repetición de n elementos, en nuestro caso, 2 aminoácidos y 4 nucleótidos.

 #!/usr/bin/perl -w  
 # Generate all the variations with repetition of n letters  
 my @aminoacids = ('A','R','N','D','C','Q','E','G','H','L','I','K','M','F','P','S','T','W','Y','V');  
 my @nucleotides = ('A','C','G','T');  
 # Generate all the variations of 2 aminoacids  
 my $aas = variations(\@aminoacids,2);  
 # Generate all the variations of 4 nucleotides  
 my $nts = variations(\@nucleotides,4);  
 # Print the results  
 print "\nAll the variations with repetition of 2 aminoacids: ";  
 foreach my $vari (@{$aas}){  
      foreach my $elem (@{$vari}){  
           print "$elem";  
      }  
      print " ";  
 }  
 print "\n";  
 print "\nAll the variations with repetition of 4 nucleotides: ";  
 foreach my $vari (@{$nts}){  
      foreach my $elem (@{$vari}){  
           print "$elem";  
      }  
      print " ";  
 }  
 print "\n\n";  
 sub variations {  
      my ($letters,$num) = @_;  
      my $last = [map $letters->[0] , 0 .. $num-1];  
      my $result;  
      while (join('',@{$last}) ne $letters->[$#{$letters}] x $num) {  
           push(@{$result},[@{$last}]);  
           $last = char_add($letters,$last,$num-1);  
           print '';  
      }  
      push(@{$result}, $last);  
      return $result;  
 }  
 sub char_add{  
      my ($digits,$string,$char) = @_;  
      if ($string->[$char] ne $digits->[$#{$digits}]){  
           my ($match) = grep { $digits->[$_] eq $string->[$char]} 0 .. $#{$digits};  
           $string->[$char] = $digits->[$match+1];  
           return $string;  
      } else {  
           $string = changeall($string,$digits->[0],$char);  
           return char_add($digits,$string,$char-1);  
      }  
 }  
 sub changeall {  
      my ($string,$char,$start,$end) = @_;  
      if (!defined($start)){$start=0;}  
      if (!defined($end)){$end=0;}  
      if ($end == 0) {$end = $#{$string};}  
      for(my $i=$start; $i<=$end; $i++){  
           $string->[$i] = $char;  
      }  
      return $string;  
 }  

Para terminar una breve lección de estadística, fuente: Aulafacil.com

a) Combinaciones:
Determina el número de subgrupos de 1, 2, 3, etc. elementos que se pueden formar con los "n" elementos de una nuestra. Cada subgrupo se diferencia del resto en los elementos que lo componen, sin que influya el orden.
Por ejemplo, calcular las posibles combinaciones de 2 elementos que se pueden formar con los números 1, 2 y 3.
Se pueden establecer 3 parejas diferentes: (1,2), (1,3) y (2,3). En el cálculo de combinaciones las parejas (1,2) y (2,1) se consideran idénticas, por lo que sólo se cuentan una vez.
b) Variaciones:
Calcula el número de subgrupos de 1, 2, 3, etc.elementos que se pueden establecer con los "n" elementos de una muestra. Cada subgrupo se diferencia del resto en los elementos que lo componen o en el orden de dichos elementos (es lo que le diferencia de las combinaciones).
Por ejemplo, calcular las posibles variaciones de 2 elementos que se pueden establecer con los número 1, 2 y 3.
Ahora tendríamos 6 posibles parejas: (1,2), (1,3), (2,1), (2,3), (3,1) y (3,3). En este caso los subgrupos (1,2) y (2,1) se consideran distintos.
c) Permutaciones:
Cálcula las posibles agrupaciones que se pueden establecer con todos los elementos de un grupo, por lo tanto, lo que diferencia a cada subgrupo del resto es el orden de los elementos.
Por ejemplo, calcular las posibles formas en que se pueden ordenar los número 1, 2 y 3.
Hay 6 posibles agrupaciones: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) y (3, 2, 1)

9 comentarios:

  1. En Perl v6, es un poco más fácil sacar permutaciones...

    use v6;
    say (<A C T G> X~ <A C T G>).join('-');

    Sale:
    AA-AC-AT-AG-CA-CC-CT-CG-TA-TC-TT-TG-GA-GC-GT-GG

    ResponderEliminar
  2. Gracias por la aportación, ingenioso este Perl 6...

    ¿y serviría para las permutaciones de 4 nucleótidos? ej. AAAA AAAC AAAG ...

    ResponderEliminar
  3. Bueno, no mucho más:

    use v6;
    my @ATCG = <A T C G>;
    say ((@ATCG X~ @ATCG) X~ (@ATCG X~ @ATCG)).join(' ');

    De todas maneras, Rakudo Star (Perl 6) salió el pasado día 29 de julio, y solo es una versión para que los programadores empecemos a aprender el nuevo lenguaje, no es el producto definitivo.

    Mientras tanto, seguiremos trabajando con Perl v5 ;)

    En CPAN tienes el módulo Algorithm::Combinatorics, de Xavier Noria, que implementa algunas de las funciones de combinatoria, pero escritas en puro C compilado, con lo que el resultado es rapidísimo.

    use Algorithm::Combinatorics "variations_with_repetition";
    my @combinaciones = variations_with_repetition([qw(A T C G)], 4);
    for $c (@combinaciones) {
        print @$c, "\n";
    }

    Por ejemplo, si en vez de 4, ponemos que nos genere las variaciones con repetición de las 4 letras, pero tomadas de 10 en 10 (1048576 combinaciones), lo hará en poco más de 12 segundos (en mi ordenador).

    ResponderEliminar
  4. un bosquejo en python:

    a = ['A', 'C', 'T', 'G']
    ["{}-{}".format(n, m) for n in a for m in a]

    ó

    [n+"-"+m for n in a for m in a]

    ResponderEliminar
  5. Cuando se trabaja con permutaciones con repeticion, en vez de pregenerar todas las permutaciones y guardarlas en un array, muchas veces es mejor utilizar un iterador que nos permita recorrer todas las permutaciones sin necesidad de tenerlas todas a la vez consumiendo memoria.

    Hay dos formas basicas de hacerlo:

    1) considerar que las permutaciones se pueden enumerar, o dicho de otra manera, cada permutacion tiene un indice y es relativamente sencillo pasar del indice a la permutacion y al reves

    2) utilizar el algoritmo del abaco para dada una permutacion pasar a la siguiente: si queremos obtener las permutaciones con repeticion de A elementos tomados de N en N, es facil ir generando las distintas permutaciones simplemente pensando que tenemos un abajo en base A con N filas en el cual para pasar de una permutacion a la siguiente simplemente sumamos 1.

    ResponderEliminar
  6. Salvador: ¿podrías poner un ejemplo de lo del ábaco o algún lugar donde verlo? gracias

    ResponderEliminar
  7. Acabo de recordar un one-liner (http://www.eead.csic.es/compbio/material/bioinfoPerl/node89.html) para generar permutaciones:

    $ perl -MAlgorithm::Permute -le '$l = [1,2,3,4,5]; $p = Algorithm::Permute->new($l); print @r while @r = $p->next'

    ResponderEliminar
  8. Hola Saludos,
    Tengo dos grupos de muestras, cada una sacada con una técnica diferente. El primer grupo es de cinco muestras (A1, A2, A3, A4 y A5) y el segundo de seis muestras (B1, B2, B3, B4, B5, y B6). Como puedo hacer las permutaciones, ya que la formula del coeficiente factorial da un total de 462 combinaciones y eso a mano, no es fácil.

    Agradezco su ayuda.

    ResponderEliminar
  9. Si lo que quieres es obtener todas las variaciones A1-A1,A1-A2...A1-B1,A1-B2...B6-B5,B6-B6

    Sustituye el código anterior con lo siguiente:
    my @aminoacids = ('A1','A2','A3','A4','A5','B1','B2','B3','B4','B5','B6');

    Ejecuta el código perl y obtendrás en pantalla las posibles combinaciones.

    Y si lo que quieres son las permutaciones, cambia esto:
    my $aas = variations(\@aminoacids,11);

    ResponderEliminar