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
, donde
representa un aminoácido hidrofóbico y
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].
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 se codifica
como un string
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
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.