Siguiente: Implementación de FANS Anterior: Experimentos y Resultados Arriba: Ejemplos de Aplicación

El Problema de Predicción de Estructura de Proteínas

El Problema de Predicción de Estructura de Proteínas, PSP, es uno de los problemas abiertos más importantes a los que la que biología se enfrenta. En términos muy simples, se puede formular como: dada una secuencia de aminoácidos, cual es la estructura tridimensional asociada de mínima energía libre?.

PSP es un problema importante ya que la estructura 3D de una proteína determina la funcionalidad biológica de la misma. La obtención de la secuencia de aminoácidos de una proteína puede considerarse un problema resuelto; sin embargo, la determinación de la estructura mediante técnicas experimentales como la resonancia magnética nuclear o la cristalografía de rayos X, sigue siendo una tarea costosa, lenta y compleja.

Dada la complejidad de las proteínas, se debe recurrir a modelos simplificados para obtener información respecto al proceso de plegamiento. Dentro de los modelos simplificados, surge el modelo HP de K. Dill [14] donde una secuencia se representa como un string $s \in \{H,P\}^+$, donde $H$ representa un aminoácido hidrofóbico y $P$ un hidrofílico.

La Figura 5 muestra secuencias ubicadas en los reticulados cuadrado y triangular. Los contactos entre H's se muestran resaltados con líneas de puntos. La conformación de la Figura 5(a) tiene un puntaje de 17 mientras que la estructura en 5(b) tiene 9 (nueve contactos).

PSP en este modelo es encontrar la estructura de máximo puntaje y se probó que era un problema NP-Hard para el reticulado cuadrado [12] y el cúbico [4]. Entre los enfoques que se aplicaron para intentar resolverlo se pueden citar algoritmos genéticos, recocido simulado, GRASP y autómatas celulares[21,22,26,29].

Figura 5: Secuencias del modelo HP en reticulado cuadrado (a) y triangular (b).

(a)		(b)

Para representar las estructuras se puede utilizar un esquema basado en coordenadas internas, donde surgen dos tipos: absoluta y relativa. En la codificación absoluta, las estructuras se representan como una lista de movimientos absolutos en el espacio correspondiente. Por ejemplo, si se utiliza un reticulado cuadrado en 2D, entonces una estructura $e$ se codifica como un string $s=\{$Arriba, Abajo, Izquierda, Derecha$\}^+$. Bajo la codificación relativa, cada movimiento es interpreta en términos del anterior: la estructura se codifica como un string en el alfabeto $e=\{$Adelante, GirarDerecha, GirarIzquierda$\}^+$.

Recientemente se realizó una comparación directa entre ambas codificaciones en el marco de algoritmos evolutivos [21]. En esta sección, describiremos dos trabajos [9,27] sobre la aplicación de FANS a PSP cuyos objetivos fueron: primero, analizar la influencia de la codificación en los resultados que obtiene FANS; y segundo, evitar un problema teórico que se da en la aplicación de AG's a PSP en este modelo.