Construir un suffix array: Manber y Myers

Hola,
hoy me gustaría volver un poco sobre el tema de los suffix array que ya ha sido tratado alguna vez en el blog.

En 1990, Manber y Myers publicaban Suffix arrays: a new method for on-line string searches, como motivo del primer ACM-SIAM symposium on Discrete algorithms. En éste fantástico e ilustrativo artículo, introducen la comparación de esta estructura con los suffix trees y proponen definiciones, notación y algoritmos para su construcción, búsqueda y optimización.

La mayor desventaja de suffix trees reside en el espacio requerido, y con los suffix arrays se consigue reducir considerablemente, siendo aún así competitivos frente a los suffix trees en términos de búsqueda y construcción.

Aquí veremos la primera parte, la creación de un suffix array ordenado (sección 3 del artículo original, sorprendentemente), con un algoritmo que requiere O(NlogN) como peor caso, si bien con optimizaciones se podría conseguir un tiempo esperado O(N); lo cual ya se consiguió de manera formal en 2003.

Quizás hoy día los suffix array van perdiendo protagonismo de primera plana, pero siguen siendo la base para muchas aplicaciones, por ejemplo implicados en métodos de obtención de la secuencia Barrows-Wheeler. Posiblemente en entradas posteriores hablemos de mejoras en el uso de suffix arrays y de otras estructuras relacionadas como FM-index y BWT.

Por ahora, aquí os dejo el código en Python (-V 2.6.6). Podéis cambiar la secuencia a indexar en la variable inicial A.

Y nos podemos preguntar ¿por qué usar éste código en lugar de la simple línea de ordenamiento MergeSort que aparecía en el código Perl de la entrada anterior sobre suffix arrays? Adjunto una tabla que lo explica en términos de tiempo requerido para la construcción del índice.

Long texto	Myers	MergeSort
20	0''019	0''004
100	0''023	0''005
1,000	0''055	0''013
11,000	0''717	0''401
110,000	22''200	41''075
220,000	1'36''004	2'42''189
660,000	9'31''297	25'54''598

Por supuesto estamos espectantes ante cualquier comentario, crítica o sugerencia.
¡Un saludo!

 #!/usr/bin/python

# Simple algorithm for Suffix Array creation,
# based on Manber & Myers, 1990
# by Cantalapiedra, 2011

############### FUNCTIONS ##############
## Function to print a Suffix Array
def printSA(text, sa = [], sa_name = "Suffix Array"):
  if len(sa) == 0:
       print "No records in {0}".format(sa_name)
  else:
       print sa_name
       for i in sa:
            print "{0}\t{1}".format(i, text[i:])
  print "\n"
  return

## Function to print one or several lists
def printTemp(things = [], title = "##", post_title = "#"):
  if len(things) == 0:
       print "No things to print"
  else:
       print title
       for a in things:
            print a
       print post_title
  print "\n"
  return

############### VARIABLES ##############

A = 'TTTTAGATCGATCGACTAGA$'

pos = [] # Contains the SA based on suffix numbers (SN)
prm = [] # Inverse of pos, each position is a SN containing its position in SA
bH = [] # Boolean array marking the buckets

b2H = [] # Temporary array for marking the 2H-buckets
count = [] # Counts the number of SN in a 2H-bucket

## All above variables have length = |A|

################ START ###################
# Some verbose
print "Your text is {0}\n".format(A[:len(A) - 1])

# Initial SA (POS)
pos = [(a,i) for i,a in enumerate(A)]
pos = sorted(pos)
pos = [a[1] for a in pos]

printSA(A, pos, "INITIAL SA")

# Initialize PRM
prm = [0]*len(A)

# Initial positions and buckets
prev_letter = ""
for i, pos_i in enumerate(pos):
  prm[pos_i] = i

  letter = A[pos_i]
  if letter != prev_letter:
       bH.append(1)
  else:
       bH.append(0)
  prev_letter = letter

######### H-STAGES ##########

count_changed = []

h_stage = 1
while h_stage < len(A): # max log2(|A| + 1)

  #print "stage {1} init {0}".format(time.time(), h_stage) IMPORT time module to use this

  # FIRST: re-assign prm as of buckets starting points
  #            and create count and b2H arrays
  prev_one = 0

  for i, bh_i in enumerate(bH):
       if bh_i == 1:
            prev_one = i # Is a bucket starting position
     
       if bh_i == 0:
            prm[pos[i]] = prev_one # Points to its bucket starting pos
     
       count.append(0)
       b2H.append(0)

  # Reset count[] to 0s
  for a in range(len(count)):
       count[a] = 0

  # THEN: for every bucket...
  # Here the entire SA is scanned, but in fact takes account
  # of the current bucket being covered
  prev_count = [a for a in count]
  for i, pos_i in enumerate(pos):
     
       if bH[i] == 1:
            b2H[i] = 1
     
       # We are moving the H-prefix (Ti) of suffix in i position
       ti = pos_i - h_stage
       if ti < 0: continue
     
       ### This is the heart of the algorithm
       # If its the first change of this bucket during this H-bucket run...
       if prev_count[prm[ti]] == count[prm[ti]]:
            change = True
       else:
            change = False
     
       count[prm[ti]] += 1
       count_changed.append(prm[ti])
       prm[ti] = prm[ti] + count[prm[ti]] - 1
     
       # ... that means this is a new 2H-bucket
       if change:
            b2H[prm[ti]] = 1
     
       #printTemp([prm, count, b2H], "After moving suff: {0}".format(ti), "")
     
       # If next position is another H-bucket, or is the last bucket
       if (i < len(bH) - 1 and bH[i + 1] == 1) or i == len(bH) - 1:
          
            #printTemp([prm, count, b2H], "", "NEXT H-BUCKET {0}".format(i + 1))
          
            for j in count_changed:
                 prev_count[j] = count[j]
            count_changed = []
     
       # If there are no buckets left
       if 0 not in b2H:
            break

  #print "end stage {0}".format(time.time())

  # If there are no buckets left
  if 0 not in b2H:
       break

  #printTemp([prm, count, b2H], "", "NEXT ROUND {0}".format(h_stage*2))

  # Update POS from PRM
  for j, prm_j in enumerate(prm):
       pos[prm_j] = j

  # Update BH from B2H
  bH = b2H

  # Reset vars for next H-STAGE
  count = []
  b2H = []
  h_stage *= 2

# Update POS from PRM
for j, prm_j in enumerate(prm):
  pos[prm_j] = j

printSA(A, pos, "FINAL SA")
#

La salida del ejemplo es:

Your text is TTTTAGATCGATCGACTAGA

INITIAL SA
$
AGATCGATCGACTAGA$
ATCGATCGACTAGA$
ATCGACTAGA$
ACTAGA$
AGA$
A$
CGATCGACTAGA$
CGACTAGA$
CTAGA$
GATCGATCGACTAGA$
GATCGACTAGA$
GACTAGA$
GA$
TTTTAGATCGATCGACTAGA$
TTTAGATCGATCGACTAGA$
TTAGATCGATCGACTAGA$
TAGATCGATCGACTAGA$
TCGATCGACTAGA$
TCGACTAGA$
TAGA$

FINAL SA
$
A$
ACTAGA$
AGA$
AGATCGATCGACTAGA$
ATCGACTAGA$
ATCGATCGACTAGA$
CGACTAGA$
CGATCGACTAGA$
CTAGA$
GA$
GACTAGA$
GATCGACTAGA$
GATCGATCGACTAGA$
TAGA$
TAGATCGATCGACTAGA$
TCGACTAGA$
TCGATCGACTAGA$
TTAGATCGATCGACTAGA$
TTTAGATCGATCGACTAGA$
TTTTAGATCGATCGACTAGA$

Transformada de Burrows-Wheeler (para comprimir secuencias y buscar patrones)

Hola,
como posiblemente haya vacaciones en el blog estas próximas semanas, os dejo una entrada algo más compleja, donde se muestran los fundamentos de la transformación de Burrows-Wheeler aplicada a la búsqueda de patrones en secuencias biológicas, como continuación natural de los vectores de sufijos y los árboles binarios, que vimos en una entrada anterior.

(fuente: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.1158)

Vaya por delante que las implementaciones reales de este algoritmo (como Bowtie o BWA) son bastante más complejas (porque permiten búsquedas inexactas) y eficientes (porque comprimen el corpus para que se pueda cargar en la memoria RAM) que el código de esta entrada, pero su filosofía es similar:

1) se precalcula la transformada de un corpus de secuencias (y se comprime)
2) se buscan patrones exactos/inexactos sobre el corpus precalculado (comprimido)

Para aprender más, además de la lectura del artículo original de Burrows y Wheeler, un material recomendable para iniciarse en estos temas puede ser el libro de Gabriel Valiente  'Combinatorial pattern matching algorithms in computational biology using Perl and R'.

El siguiente código en Perl muestra un prototipo con estas ideas, empleando para la búsqueda el árbol binario implícito en el vector de sufijos:

 use strict;  
   
 my $VERBOSE = 1;  
 my @ALPHABET = ( '$', 'a' .. 'z' ); # orden lexicografico, $ marca el final   
   
 my ($text,$pattern) = ('mississippi','ssi');           
            
 printf("# original text: '%s'\n\n",$text);  
   
 my ($bwt,$start,$F) = BWT($text,$VERBOSE);   
   
 printf("# BWT('%s') = ('%s',%d) | F: %s\n",$text,$bwt,$start,$F);   
   
 # ahora se pueden comprimir $bwt y $F, por ejemplo, con run-length coder:  
 # 'mmmmmsssiiii' (12 bytes) quedaría como 'm5s3i4' (6 bytes)  
   
 my ($orig_text,$ref_array_W) = revBWT($bwt,$start,$VERBOSE);  
   
 printf("# BWTinv('%s',%d) = '%s'\n\n",$bwt,$start,$orig_text);   
   
 print "# searching for '$pattern' matches in '$text' [base 0]:\n";  
 match_pattern_BWT($pattern,$F,$start,$ref_array_W);  
   
   
   
 # Calcula un vector de sufijos de manera que las diferentes subcadenas   
 # de una secuencia queden preordenadas lexicograficamente  
 sub make_suffix_array  
 {  
   my ($seq,$verbose) = @_;       
   
   my $l = length($seq);  
   my @suffix = (0 .. $l-1); # en base 0  
   
   # ordena los length($seq) posibles sufijos lexicográficamente (cmp),  
   # este paso consume RAM y es uno de los pasos que se puede optimizar  
   @suffix = sort {substr($seq,$a) cmp substr($seq,$b)} (@suffix);  
   if($verbose)  
   {  
     print "# suffix array for $seq :\n";  
     foreach my $suf (@suffix)  
     {   
       printf("%3d %s%s\n",  
         $suf,substr($seq,$suf),substr($seq,0,$l-($l-$suf)));   
     }  
     print "\n";  
   }  
   return @suffix;  
 }  
   
 # Devuelve: 1) string BWT, 2) índice $start, que indica la fila del vector  
 # de sufijos que contiene la cadena original, y 3) string $F, la columna   
 # F1..Fn concatenada.  
 # BWT realmente es la columna de caracteres que preceden a la primera (F)  
 # de un vector de sufijos, o la última (L) si en vez de sufijos la cadena  
 # se permuta circularmente  
 # F1 .............$ L1  
 # F2 ............$. L2  
 # Fn ......$....... Ln  
 sub BWT  
 {  
   my ($seq,$verbose) = @_;  
       
     $seq = $seq . '$'; # marca el final   
       
   my @suffix_rotation = make_suffix_array($seq,$verbose);  
   my ($bwt,$start,$F) = ('',0);  
   foreach my $c (0 .. length($seq)-1)  
   {  
     $bwt .= substr($seq,$suffix_rotation[$c]-1,1);  
         $F .= substr($seq,$suffix_rotation[$c],1);  
     if($suffix_rotation[$c] == 0)  
     {  
       # fila del vector de sufijos que contiene cadena original    
       $start = $c;   
     }  
   }  
   return ($bwt,$start,$F);  
 }  
   
 # Devuelve: 1) la cadena original correspondiente a una cadena  
 # previamente transformada con BWT y 2) una referencia a un array @W  
 # que contiene, para cada posicion del vector L (cadena transformada), la que  
 # le sigue en la secuencia original; ojo, el orden de @W se conserva en @F  
 sub revBWT  
 {  
   my ($bwt,$start,$verbose) = @_;  
   my (@L,@C,@K,@M,@W,@T,$original_string);  
   my ($c,$l,$r,$total,$last_char);  
     my $last_alphabet = scalar(@ALPHABET)-1;  
   
   # convierte cadena $bwt en array @L  
   @L = split(//,$bwt);  
     $last_char = scalar(@L)-1;  
   
   # calcula vectores auxiliares C y K, contienen las observaciones   
   # de cada letra del alfabeto en $bwt (@L)  
   foreach $l (0 .. $last_alphabet){ $K[$l] = 0 }  
       
   foreach $c (0 .. $last_char)  
   {   
     foreach $l (0 .. $last_alphabet)  
     {  
       if($L[$c] eq $ALPHABET[$l])  
       {  
         $C[$c] = $K[$l];    
         $K[$l]++;  
       }   
     }   
   }  
       
     foreach $l (0 .. $last_alphabet)  
   {  
     if($verbose && $bwt =~ /$ALPHABET[$l]/)  
     {  
       print "# $ALPHABET[$l] K=$K[$l]\n";  
     }               
   }  
   
   # calcula vector auxiliar M, que contiene la primera aparición  
   # de cada letra del alfabeto en vector implícito F, que es   
   # la primera columna del suffix array subyacente  
   $total = 0;  
   foreach $l (0 .. $last_alphabet)  
   {  
     $M[$l] = $total;  
     $total += $K[$l];    
     if($verbose && $bwt =~ /$ALPHABET[$l]/)      
     {  
       print "# $ALPHABET[$l] M=$M[$l]\n" if($verbose);  
     }  
   }  
   
   # calcula vector decodificador @W (forward), destruye @M  
   foreach $c (0 .. $last_char)  
   {  
     foreach $l (0 .. $last_alphabet)  
     {  
       if($L[$c] eq $ALPHABET[$l])  
       {  
         $W[$M[$l]] = $c;     
         $M[$l]++;   
       }    
     }    
   }  
   
   # decodifica cadena de texto original (@T)  
   $original_string = '';  
   $l = $start;  
   foreach $c (0 .. $last_char)  
   {  
     $original_string .= $L[$l] if($L[$l] ne '$');  
     $l = $W[$l]  
   }  
   
   return ($original_string,\@W);  
 }  
   
 # Funcion equivalente al operador cmp para comparar una cadena $pattern   
 # con la BWT de un texto, dada una fila $row del suffix_array.  
 # Devuelve < 0 si $pattern < $bwt (orden lexicográfico), > 0 en caso contrario,  
 # y 0 si la fila $r comienza con $pattern   
 sub BWTstrcmp  
 {  
   my ($pattern,$F,$row,$ref_W) = @_;  
     
   my @F = split(//,$F);  
   my $m = length($pattern);   
   my ($c,$match) = (0,'');    
       
   while($m >= 0 and $F[$row] eq substr($pattern,$c,1))  
   {  
         $match .= $F[$row];  
     $row = $ref_W->[$row];  
     $m--;  
     $c++;  
   }    
   
   if($m == 0){return 0 } # match  
   else{ return substr($pattern,$c,1) cmp $F[$row] }  
 }  
   
 # Procedimiento que busca ocurrencias de un patron recorriendo el vector de sufijos  
 # implicito en la BWT, por medio del vector @F. Imprime las posiciones encontradas  
 sub match_pattern_BWT  
 {  
   my ($pattern,$F,$start,$ref_W) = @_;  
     
     my ($med,$submed,$low,$high,$comp);  
     my $last = length($F);  
   $low = 0;  
   $high = $last;  
   
   while ($low <= $high)   
   {  
     $med = int (($low+$high)/2);     
     $comp = BWTstrcmp($pattern,$F,$med,$ref_W);  
   
     if($comp < 0){ $high = $med-1 } # retrocedemos   
     elsif($comp > 0){ $low = $med+1 } # avanzamos  
     else   
     {  
       $submed = $med; # filas anteriores  
             while($submed > 0 &&   
         BWTstrcmp($pattern,$F,$submed,$ref_W) == 0)  
       {   
         printf("# match at position %d\n",  
           get_real_position($submed,$start,$ref_W));  
         $submed--;   
       }  
         
             $submed = $med + 1; # filas posteriores  
       while ($submed < $last &&   
         BWTstrcmp($pattern,$F,$submed,$ref_W) == 0)  
       {  
         printf("# match at position %d\n",  
           get_real_position($submed,$start,$ref_W));  
         $submed++;   
       }  
       last;  
     }  
   }  
   
 }  
   
 # Devuelve la posicion en el texto original de una fila de @F  
 sub get_real_position  
 {  
   my ($Fpos,$start,$ref_W) = @_;   
       
   my $real_pos = 0;  
   while($start != $Fpos)  
   {  
     $start = $ref_W->[$start];  
     $real_pos++;       
   }  
   return $real_pos;  
 }