[TEORÍA DE LA INFORMACIÓN] Resumen

Accelerating Protein Classification Using Suffix Trees

Bogdan Dorohonceanu and C.G. Nevill-Manning

Introducción

Las matrices de búsqueda de posición específica han sido usadas extensamente para reconocer regiones altamente conservadas de proteinas. Dorohonceanu y Nevill-Manning presentan un método para acelerar las búsquedas usando estructura de arboles de sufijos calculada desde las secuencias que se buscarán.

Estas matrices de búsqueda capturan la distribución característica de aminoácidos. Son más sensitivas que los métodos basados en expresión regular coo PROSITE y EMOTIF pero requieren menos información que los modelos ocultos de Markov.

Su principal desventaja contra PROSITE y EMOTIF es su velocidad. Debido a que en esos métodos permiten hacer saltos en cualquier discrepancia, en una matriz de búsqueda siempre se acierta con la misma probabilidad, por lo que hacer saltos es algo problemático.

La desventaja de usar arboles de sufijos es que es muy caro en términos de memoria; requiere 37 bytes por símbolo de entrada. Sin embargo los autores lograron reducir esto a 17 bytes.

Matices de búsqueda

Una matriz de búsqueda de posición específica S representa un alineamiento local sin pausas de una familia de secuencias. El alineamiento consiste en varias posiciones contiguas, cada posición representada por una columna en la matriz. Cada columna j consiste en un vector Sj(r), un resultado por cada posible residuo r.

Una matriz de búsqueda puede ser usada en análisis de secuencias, pasando la matriz por la secuencia y calculando el resultado del segmento. Cada resultado es la suma de las entradas apropiadas de la matriz, donde cada residuo corresponde a un resultado en una columna de la matriz.

Intuitivamente, un resultado del segmento mayor indica un mayor probabilidad de que la secuencia sea igual que la matriz de búsqueda.

Muchas implementaciones de PSSM's para funciones de predicción de proteínas aplican la matriz a cada segmento de cada proteína en la entrada. ordenan los segmentos por sus resultados y presentan los mejores resultados.

Arboles de sufijos

Un árbol de sufijos es un árbol compacto de sufijos en una cadena, para cada sufijo de una cadena hay un camino en su árbol correspondiente desde la raíz hasta las hojas que contengan la cadena.

La imagen anterior muestra un árbol de sufijos para la cadena "abab$". Este árbol es compactado de la siguiente manera. Donde sea que dos aristas inicien en el mismo nodo que comparta un prefijo, una nueva arista y un nodo son creados, y la arista tendrá la misma cadena. Por lo que las aristas anteriores ya no comparten el prefijo. Esto se hace hasta que ninguna arista comparta prefijos.

Para encontrar un segmento de buenos resultados en un set de secuencias de proteínas, primero se crea un arreglo de secuencias. Después se hace un DFT (búsqueda de profundidad) del árbol, calculando los resultados para las cadenas de las aristas.

Donde sea que el resultado alcance el umbral, todas las subcadenas representadas por las hojas de ese nodo deben también alcanzarlo, y pueden ser reportadas.

Esa es la llave para la aceleración, muchas subcadenas pueden ser descontinuadas basado en un simple camino. La siguiente imagen muestra dos casos: un subarbol que acierta y uno que no lo hace.

Arboles de sufijos compactos

Un problema significante es que los arboles son su tamaño en memoria primaria. Los aminoacidos consisten en 20 elementos, en la base de datos se registran 20 millones de aminoacidos y con aproximadamente 30 millones de nodos. Esto es 30,000,000 nodos x 22 punteros por nodo x 4 bytes por puntero dando como resultado 2.6 Gb. Pero no todos los nodos cuentan con almentos 20, se puede ahorrar memoria al usar listas enlazadas a sus hijos.

Esto da a un total de 30,000,000 nodos x 4 bytes por nodo x 4 bytes por puntero dando resultado a 480 Mb.

Fuente:
http://www.aaai.org/Papers/ISMB/2000/ISMB00-013.pdf