INTRODUCCIÓN A LA
BIOINFORMÁTICA
METAHEURÍSTICAS APLICADAS AL
PROBLEMA DEL PLEGADO DE
PROTEÍNAS
SANTIAGO REVALE & PÁVEL MORALES-RIVAS
Esbozo de la Presentación:





Breve introducción a la Biología Molecular.
Problema del Plegado de Proteínas.
Optimización de Colonia de Hormigas aplicado al modelo 2D
HP del Plegado de Proteínas.
Otros algoritmos.
Conclusiones.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Biología Molecular



Es el estudio de la vida a un nivel molecular.
Concierne principalmente al entendimiento de las interacciones de los
diferentes sistemas de la célula, lo que incluye muchísimas relaciones, entre
ellas las del ADN con el ARN, la síntesis de proteínas, el metabolismo, y el
cómo todas esas interacciones son reguladas para conseguir un afinado
funcionamiento de la célula.
Pretende fijarse con preferencia en el comportamiento biológico de las
macromoléculas (ADN, ARN, enzimas, hormonas, etc.) dentro de la célula y
explicar las funciones biológicas del ser vivo por estas propiedades a nivel
molecular.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Unidad de Vida
Procariotas Vs. Eucariotas
La Célula
“Es la unidad viva más pequeña capaz de crecimiento autónomo y reproducción, así como de
utilizar sustancias alimenticias químicamente diferentes de sí misma".

Todos los sistemas biológicos tienen una serie de características comunes:

capacidad de reproducción;

capacidad de absorber sustancias nutritivas y metabolizarlas para obtener energía y
desarrollarse;

capacidad de expulsar los productos de desecho;

capacidad de respuesta a los estímulos del medio externo;

capacidad de mutación.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Unidad de Vida
Procariotas Vs. Eucariotas
La Célula (cont.)

Todas las células vivas son fundamentalmente semejantes.

Constituidas por el protoplasma

Del griego 'protos' -primario- y 'plasma' -formación-.

Complejo orgánico compuesto básicamente de proteínas, ácidos nucleicos, lípidos y polisacáridos.

Debido a esto, es aceptado que todas las células descienden de algún antepasado común, de una
célula primordial.

Rodeadas por membranas limitantes y algunas por paredes celulares.

Poseen un núcleo o sustancia nuclear equivalente.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Unidad de Vida
Procariotas Vs. Eucariotas
Procariotas Vs. Eucariotas
Se clasifica a los seres vivos en dos grandes grupos:


Procariota (del griego pro = previo a y karyon = núcleo)

Célula sin núcleo celular diferenciado (su ADN no se encuentra rodeado por
membranas).

Primeras formas de vida sobre la tierra (aparecieron hace 3500 millones de años).

Básicamente, organismos unicelulares (x ej: bacterias).
Eucariota (del griego eu = verdadero y karyon = núcleo)

Poseen un núcleo verdadero rodeado por membranas.

Es típicamente mayor y estructuralmente más compleja que la procariota.

Estos incluyen algas, protozoos, hongos, plantas superiores y animales.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Unidad de Vida
Procariotas Vs. Eucariotas
Procariotas Vs. Eucariotas (cont.)
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
Acidos nucleicos
Todas las células contienen la información necesaria para realizar distintas reacciones
químicas mediante las cuales las células crecen, obtienen energía y sintetizan sus
componentes.

Esta información está almacenada en el material genético.

Puede copiarse con exactitud para transmitir dicha información a las células hijas.

Estas instrucciones pueden ser modificadas levemente.


Variaciones individuales: un individuo no es exactamente igual a otro de su misma especie (distinto
color de ojos, piel, etc.).

En conclusión, el material genético es suficientemente maleable como para hacer posible la evolución.
La información genética o genoma, está contenida en unas moléculas llamadas ácidos
nucléicos. Existen dos tipos de ácidos nucléicos:

el ADN, que guarda la información genética en todos los organismos celulares, y

el ARN, que es necesario para que se exprese la información contenida en el ADN.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Acidos nucleicos
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
ADN – Acido desoxirribonucléico



Provee el código genético que determina todas las características
individuales de las personas.
En este código las unidades básicas de información son llamadas bases (ó
desoxiribonucleótidos) y son Adenina (A), Guanina (G), Citosina (C) y
Timidina (T).

Estas bases se unen siempre de manera complementaria en la hebra de ADN

A siempre une con T, y C siempre une con G.
La combinación de una base con su complementaria se la conoce como par
de bases.

Está ubicado en el núcleo o espacio nuclear de las células.

Suele encontrarse en un estado laxo o “relajado” llamado cromatina.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
El Gen


Es una secuencia determinada de bases (fragmento de ADN) que contiene
toda la información necesaria para producir una proteína.
Es la unidad mínima que se puede heredar, o sea, que puede ser tomada
de uno de los progenitores para formar el nuevo individuo.
Si las características heredables (como el aspecto de la cara) las descomponemos en
otras subcaracterísticas (color de los ojos, color del pelo, tez), cuando ya no podamos
dividir más esas características de forma que sigan siendo heredables, diremos que esa
característica es debida a un gen.

El Gen tiene básicamente dos funciones:
1.
reproducirse a sí mismo, e
2.
indicar el modo de construcción y comportamiento de un nuevo ser vivo completo.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
El Gen

A grosso modo, podemos dividir el gen en 5 regiones:

una promotora: estimula o inhibe la expresión del gen,

una de iniciación,

una codificante (exón): parte que se expresará,

una no codificante (intrón): no llegará a expresarse, y

una de terminación.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
Regulación de la expresión
Ya vimos que en el ADN (o los Genes) se encuentra la información para la construcción y
comportamiento de un nuevo ser vivo completo.
Pero si además sabemos que todas las células de nuestro cuerpo poseen el mismo material
genético, ¿cómo es que cada célula expresa cosas diferentes?
En forma resumida, podemos decir que cada
parte de nuestro cuerpo posee factores que
estimulan el desarrollo de las características
de lo que deben ser e inhiben aquellas que
no se correspondan.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
Los Cromosomas

Su número es constante para toda especie: el ser humano tiene 22 pares autosómicos y
1 par sexual, o sea, 46 cromosomas por célula (con excepción de las sexuales).
¿Qué son los cromosomas?


Teóricamente, son los portadores de los factores de la herencia o genes.
Físicamente, son pequeños cuerpos en forma de bastoncillos en que se organiza la
cromatina del núcleo celular durante las divisiones celulares.
¿Cuál es su función?

Comprimir la información necesaria para la construcción de un ser vivo completo.
Pero, ¿por qué comprimirla?

La longitud del ADN de cada célula humana es de aproximadamente 2 metros. Si se
sumara la longitud del ADN de todas las células de una sola persona se podría rodear
la circunferencia terrestre 500,000 veces.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
Compactación del ADN en un Cromosoma
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
Integración de conceptos del ADN
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
ARN – Acido ribonucleico




Es un intermediario para la expresión de la información contenida en el
ADN.
En este código las unidades básicas de información son también llamadas
bases (ó ribonucleótidos) y son Adenina (A), Guanina (G), Citosina (C) y
Uracilo (U), este último equivalente a la base Timina en el ADN.
El ácido ribonucleico se forma por la polimerización de ribonucleótidos. En
general los ribonucleótidos se unen entre sí, formando una cadena simple.
La cadena simple de ARN puede plegarse y presentar regiones con bases
apareadas, de este modo se forman estructuras secundarias del ARN, que
tienen muchas veces importancia funcional, como por ejemplo en los ARNt
(ARN de transferencia).
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
ARN – Acido ribonucleico (cont.)
Se conocen tres tipos principales de ARN:

ARN mensajero (ARNm)

ARN de transferencia (ARNt)

ARN ribosomal (ARNr)

No entra en el alcance de la exposición.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
ARN mensajero (ARNm)




Consiste en una molécula lineal de ribonucleótidos (monocatenaria).
Su secuencia de bases es complementaria a una porción de la secuencia de
bases del ADN.
Las instrucciones residen en tripletes de bases a las que llamaremos
codones.
Son los ARN más largos y pueden tener entre 1000 y 10000 nucleótidos.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
ADN – Acido desoxirribonucleico
El Gen
Regulación de la expresión
Los Cromosomas
Integración de conceptos del ADN
ARN – Acido ribonucleico
ARN de transferencia (ARNt)

Es el más pequeño de todos, tiene aproximadamente 75 bases en su cadena.

Se pliega adquiriendo lo que se conoce con forma de hoja de trébol plegada.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Qué son las proteínas?
¿Qué hacen las proteínas?
¿Qué son los aminoácidos?
Clasificación de aminoácidos
¿Qué son las proteínas?



Son las macromoléculas más abundantes en las células y constituyen
alrededor del 50% de su peso seco.
Grupo de compuestos que mayor cantidad de funciones desempeñan en los
seres vivos, prácticamente no existe proceso biológico en el que no participe
por lo menos una proteína.
Dentro de las células se las encuentra en formas muy variadas: como
constituyente de las membranas biológicas, como catalizadores de reacciones
metabólicas (enzimas), interactuando con los ácidos nucleicos (histonas) o con
neurotransmisores y hormonas (receptores), etc.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Qué son las proteínas?
¿Qué hacen las proteínas?
¿Qué son los aminoácidos?
Clasificación de aminoácidos
¿Qué hacen las proteínas?


Algunos ejemplos de lo que las proteínas hacen:

La enizma alcohol dehidrogenasa transforma el alcohol proveniente de cerveza/vino/licor en una
forma no tóxica que el cuerpo utiliza para comida.

La hemoglobina transporta oxígeno en nuestra sangre.

La fibrina forma una costra ó “cascarita” para proteger los cortes mientras curan.

La insulina regula la cantidad de azúcar en sangre y es utilizada para tratar la diabetes.
Las proteínas están presentes en todas las cosas vivas, inclusive en plantas,
bacterias y virus. Algunos organismos tienen proteínas que les brindan sus
características especiales:

El fotosistema I es una colección de proteínas en las plantas que capturan la luz solar para poder
realizar el proceso de fotosíntesis.

La luciferasa cataliza la reacción química que hace que la luciérnaga brille.

La hemoaglutinina ayuda al virus influenza (de la gripe) a invadir nuestras células.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Qué son las proteínas?
¿Qué hacen las proteínas?
¿Qué son los aminoácidos?
Clasificación de aminoácidos
¿Qué son los aminoácidos?






Son la unidad estructural básica de las proteínas.
Dos aminoácidos se combinan para forman un dipéptido. Si se une un tercer aminoácido se
forma un tripéptido y así, sucesivamente, para formar un polipéptido.
Cuando las cadenas polipeptídicas superan los 40 aminoácidos se denominan proteínas.
Existen cientos de aminoácidos diferentes, pero sólo 20 son necesarios para poder formar las
proteínas.
La proteína humana más grande conocida es Titina, que mide 34.350 aminoácidos.
Estructura general: un carbono central unido a un grupo
carboxilo (rojo en la figura), a un grupo amino (verde), a
un hidrógeno (en negro) y a una cadena lateral (azul).

La diversidad de la cadena lateral caracteriza a cada
aminoácido.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Qué son las proteínas?
¿Qué hacen las proteínas?
¿Qué son los aminoácidos?
Clasificación de aminoácidos
Clasificación de aminoácidos
Existen muchas formas de clasificar los aminoácidos; las dos formas que se presentan a
continuación son las más comunes.


Según su obtención

Esenciales: son aquellos aminoácidos que necesitan ser ingeridos por el cuerpo para obtenerlos.

No esenciales.
Según las propiedades de su cadena lateral

Neutros polares, polares o hidrófilos.

Neutros no polares, apolares o hidrófobos.

Con carga negativa, o ácidos.

Con carga positiva, o básicos.

Aromáticos.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
Dogma Central de la Biología Molecular


P: ¿Cómo logra la naturaleza expresar en los organismos la información contenida
en el ADN?
R: A través de las Proteínas.
P: ¿Cómo se obtienen entonces las proteínas a partir del ADN?
R: Con la ayuda del ARN y a través de los procesos de transcripción y traducción.
Finalmente, y dicho técnicamente, llegamos al dogma central de la Biología Molecular:
¿Cómo hace una molécula de ADN para codificar una
proteína?
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
Transcripción

Es el proceso de transferencia de información de ADN en ARNm.

Ocurre entre dos alfabetos simples: el de ADN y el de ARN.

Se realiza en el núcleo (eucariotas) o espacio nuclear (procariotas).

Se realiza a partir de la hebra molde de ADN (la 3’-5’).

El ARNm resultante es de cadena simple, a diferencia de la doble
hélice formada por el ADN.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
Traducción

Es el proceso mediante el cual se forman las proteínas a partir de
los aminoácidos codificados por el ARNm.

Ocurre en el citoplasma (básicamente, fuera del núcleo).

Se da en 4 pasos*:
1.
2.
3.
4.
Activación.
Iniciación de la síntesis.
Elongación de la cadena polipeptídica.
Terminación de la síntesis.
* Analogía simple con la
construcción de un edificio:
1) obtener los materiales,
2) preparar los cimientos,
3) agregar pisos, y
4) Terminar (je! :D)
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
Pero, si existen 20 aminoácidos diferentes, ¿cómo se identifican si sólo se
tienen 4 bases distintas?



Con 1 posición, 4 bases, se podrían obtener 4 aminoácidos.
(No sirve, demasiado poco…)
Con 2 posiciones, 4*4 combinaciones de bases, se podrían
obtener 16 aminoácidos. (Sigue sin alcanzar)
Con 3 posiciones, 4*4*4 combinaciones de bases, se podrían
obtener 64 aminoácidos. (¡Bingo!)
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
El Código Genético
El código genético es el conjunto de reglas por las que la información codificada en el
material genético (secuencias de ADN o ARN) se traduce en proteínas (secuencias de
aminoácidos) en las células vivas.







Define la relación entre secuencias de tres bases, llamadas codones, y aminoácidos.
Un codón se corresponde con un aminoácido específico.
La secuencia del material genético se compone de cuatro bases nitrogenadas distintas, que
tienen una función equivalente a letras en el código genético: A, T, C y G en el ADN y A, U, C y
G en el ARN.
Debido a esto, el número de codones posibles es 64.
61 de ellos codifican aminoácidos (siendo además uno de ellos el codón de inicio, AUG)
los tres restantes son sitios de parada (e stop): UAA, UAG, UGA.
La secuencia de codones determina la secuencia aminoacídica de una proteína en concreto, que
tendrá una estructura y una función específicas.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
El Código Genético: características

Universalidad



Continuidad




El código genético es compartido por todos los organismos conocidos, incluyendo virus y orgánulos
(aunque pueden aparecer pequeñas diferencias).
Este hecho indica que el código genético ha tenido un origen único en todos los seres vivos conocidos.
Ningún codón codifica más de un aminoácido: de no ser así, conllevaría problemas considerables para
la síntesis de proteínas específicas para cada gen.
No presenta solapamiento: los tripletes se hallan dispuesto de manera lineal y continua.
Su lectura se hace en un solo sentido (5' - 3'), desde el codón de iniciación hasta el codón de parada.
Degeneración

Que 61 codones codifiquen nada más que 20 aminoácidos hace del código genético que sea
redundante, lo que se denomina como código degenerado.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
El Código Genético: tabla estándar
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
La Expresión Génica
Transcripción
Traducción
El Código Genético
Resumen
Resumiendo…
Transcripción
Traducción
Secuencia de ADN
Secuencia de ARN
Secuencia aminoacídica
ATG
AUG
MET
Secuencia de un triplete en ADN
Codón en ARNm
Aminoácido en proteína
Una analogía del Dogma llevada a la informática, más precisamente a un programa de
computadora:
Secuencia de ADN
Secuencia de ARN
Secuencia aminoacídica
Código Fuente
Código precompilado
Ejecutable
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Por qué es la forma tan importante?
¿Qué forma adoptará una proteína?
La estructura protéica
Ejemplos
¿Por qué es la forma tan importante?
¡La estructura especifica la función de
la proteína!
Por ejemplo, una proteína que quiebre la glucosa de manera tal que la célula
pueda utilizar la energía almacenada en el azúcar tendría una forma que
reconociese a la glucosa y se le adhiriese (como llave y cerradura) y
aminoácidos químicamente reactivos que reaccionen con la misma y la quiebren
para liberar la energía.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Por qué es la forma tan importante?
¿Qué forma adoptará una proteína?
La estructura proteica
Ejemplos
¿Qué forma adoptará una proteína?


A pesar de que las proteínas sean simplemente una cadena de
aminoácidos, no les gusta mantenerse en una línea estirada.
La proteína se pliega hasta formar un globo compacto, pero mientras lo va
haciendo:





deja algunos aminoácidos cerca del centro del mismo, y otros hacia fuera; y
mantiene algunos pares de aminoácidos bien cerca y otros bien separados.
Cada tipo de proteína se pliega en una muy forma específica, y es
siempre la misma.
La mayoría de proteínas se pliegan por su cuenta, aunque algunas
necesitan alguna ayuda extra para plegarse en la forma correcta.
La forma única de una proteína particular es el estado más estable que
puede adoptar.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
¿Por qué es la forma tan importante?
¿Qué forma adoptará una proteína?
La estructura proteica
Ejemplos
La estructura proteica
La estructura de las proteínas puede
jerarquizarse en una serie de niveles,
interdependientes. Estos niveles corresponden
a:
1.
2.
3.
4.
Estructura primaria, que corresponde a la
secuencia de aminoácidos.
Estructura secundaria, que provoca la
aparición de motivos estructurales.
Estructura terciaria, que define la estructura
de las proteínas compuestas por un sólo
polipéptido.
Estructura cuaternaria, si interviene más de
un polipéptido.
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Algunos ejemplos…
La hemoglobina es una proteína
tetramérica, que sirve como un buen
ejemplo de proteína con estructura
cuaternaria.
¿Por qué es la forma tan importante?
¿Qué forma adoptará una proteína?
La estructura proteica
Ejemplos
Biología Molecular
La Célula
Acidos Nucleicos
Proteínas
Dogma Central de la Biología Molecular
Plegamiento de Proteínas
Algunos ejemplos…
Dominio de unión a calcio de calmoldulina;
las esferas azules representan al metal.
¿Por qué es la forma tan importante?
¿Qué forma adoptará una proteína?
La estructura proteica
Ejemplos
Representación de la
estructura proteica a
tres niveles: arriba, el
primario, compuesto por
los aminoácidos; en el
centro, el secundario,
definido por las
estructuras en alfa
hélice, beta lámina y
semejantes; y abajo el
terciario, que detalla
todos los aspectos
volumétricos.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Definición del problema
Motivación del enfoque computacional
El Problema del Plegado de Proteínas
En la actualidad, la conformación de una proteína, es decir, la
estructura final de la misma en el espacio tridimensional, es
comúnmente estudiada a través de técnicas tales como la
espectroscopia por resonancia magnética nuclear (RMN) y la
cristalografía con rayos X, las cuales son costosas en términos de
equipos, procesamiento y tiempo.
Adicionalmente, el uso de estas técnicas requiere de procesos previos
de aislamiento, purificación y cristalización de la proteína a estudiarse.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Definición del problema
Motivación del enfoque computacional
El Problema del Plegado de Proteínas
Dada la complejidad y el costo de los factores antes mencionados la
predicción automática de dicha conformación a partir de la secuencia
de aminoácidos que componen la proteína es uno de los problemas
mas prominentes de la biología computacional.
Sin embargo, a pesar de lo atractivo del problema, de su importancia
práctica y del considerable progreso alcanzado en las técnicas
utilizadas hasta el momento, el rendimiento de los mas avanzados
métodos computacionales probados a la fecha sigue siendo
considerado insuficiente.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Definición del problema
Motivación del enfoque computacional
La dificultad de la resolución de este problema de predicción tiene su
origen en dos factores principales, a saber:
1)
El problema fundamental de, dada una estructura candidata,
tener un mecanismo adecuado de medición de la calidad de dicha
estructura, es decir, del nivel energético de la misma.
Este problema necesita ser resuelto por la bioquímica a partir del
estudio y modelado de los procesos reales de plegado proteico.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Definición del problema
Motivación del enfoque computacional
1)
El problema fundamental de, dada una estructura candidata, tener un
mecanismo adecuado de medición de la calidad de dicha estructura, es
decir, del nivel energético de la misma.
2)
Dada dicha medición, el problema de determinar las estructuras óptimas
o cercanas a la óptima para una secuencia de aminoácidos.
Este problema es una fuente rica e interesante de problemas
computacionales para optimización global y local.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Definición del problema
Motivación del enfoque computacional
Con el fin de lograr la separación entre estos
dos aspectos básicos, el problema de la
optimización es frecuentemente estudiado a
partir de modelos simplificados del problema
original.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Historia del modelo
Sustento biológico
Modelo HP
Modelo 2D HP
Los trabajos estudiados se enfocan en el modelo Hidrofóbico-Polar en 2
dimensiones (2D HP por sus siglas en inglés), un modelo extremadamente
simple pero extensamente utilizado para el estudio de enfoques
algorítmicos al problema de la predicción de estructura proteica.
Aún con este modelo simplificado, encontrar plegamientos óptimos es
computacionalmente difícil tanto para la versión en 2 dimensiones como
para su variante en 3 dimensiones (técnicamente hablando, es un
problema NP-Hard tanto para el modelo original como para muchas de
las variaciones del mismo. Berger & Leighton. 1998. N. Krasnogor et al.
1999).
Debido a lo anterior los métodos de optimización heurísticos se perfilan
como algunos de los mas promisorios enfoques para atacar el problema.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Historia del modelo
Sustento biológico
Modelos HP y 2D HP
El modelo HP fue propuesto originalmente por Dill
(1985) y desarrollado luego por Lau & Dill (1989)
llevándolo estos a su planteamiento actual.
En el trabajo de estos últimos se incorpora el modelado
de las moléculas como cadenas cortas de aminoácidos
en un retículo cuadrado de dos dimensiones (2D HP
PFP).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Historia del modelo
Sustento biológico
Modelos HP y 2D HP
El modelo se basa en el enfoque termodinámico al problema de la
predicción de la estructura terciaria de las proteínas y asume que
las mismas buscan al plegarse minimizar la cantidad de energía
utilizada por el sistema llegando a un estado estable llamado
estado nativo.
Mas aún, es generalmente aceptado por la comunidad científica
especializada -con base en los resultados empíricos obtenidos- que
todas las proteínas naturales tienen un estado nativo único. Esta
hipótesis es conocida como la Hipótesis Termodinámica o el Dogma
de Anfinsen.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Historia del modelo
Sustento biológico
Modelos HP y 2D HP
En particular, el modelo HP encuentra sustento biológico adicional
en resultados bien conocidos sobre el importante rol de los
aminoácidos hidrofóbicos y polares en la estructura proteica final
ya que la interacción hidrofóbica es la fuerza impulsora del
plegado de proteínas y la hidrofobicidad de los aminoácidos la
principal fuerza para el desarrollo de la conformación nativa de
pequeñas proteínas globulares (Richards, 1977. Lau & Dill, 1989).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Historia del modelo
Sustento biológico
Modelos HP y 2D HP
En el modelo HP, cada uno de los 20 aminoácidos es clasificado
como Hidrofóbico (H) o Polar (P) en base a sus características
moleculares fundamentales.
Basados en esta clasificación, cada secuencia de aminoácidos
primaria de una proteína (la cual puede ser representada
originalmente como una cadena de caracteres de un alfabeto de
20 letras -una por cada aminoácido-) es abstraida a una secuencia
de residuos hidrofóbicos o polares, es decir, a una cadena, de la
misma longitud que la original, pero con un alfabeto reducido a
solo 2 letras (H y P, dependiendo de la clasificación del
aminoácido).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Historia del modelo
Sustento biológico
Modelos HP y 2D HP
Ejemplo:
Esta conformación en particular representa a la secuencia:
HPHPPHHPHPPHPHHPPHPH.
Los cuadrados negros representan aminoácidos hidrofóbicos y los blancos simbolizan
aminoácidos polares.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Historia del modelo
Sustento biológico
Modelos HP y 2D HP
Ejemplo:
El cuadrado negro indicado como con el Número 1 corresponde al elemento s1 de la
secuencia.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Historia del modelo
Sustento biológico
Modelos HP y 2D HP
Cabe mencionar que uno de los enfoques más comunes para la
predicción de estructuras proteicas es el de modelar la energía
libre de un aminoácido dado dependiendo de su conformación y a
partir de allí encontrar conformaciones de minimicen dicha
energía.
En el modelo HP, basados en la motivación biológica antes
descrita, la energía de una conformación está definida como el
número de contactos topológicos entre aminoácidos hidrofóbicos
que no son vecinos en la secuencia dada.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Historia del modelo
Sustento biológico
Modelos HP y 2D HP
En el caso de la figura, las líneas continuas representan el camino
seguido por la secuencia original y las líneas punteadas
representan los contactos H-H necesarios para el cálculo de
energía según el método antes mencionado.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Historia del modelo
Sustento biológico
Modelos HP y 2D HP
En el caso de la figura, las líneas continuas representan el camino
seguido por la secuencia original y las líneas punteadas
representan los contactos H-H necesarios para el cálculo de
energía según el método antes mencionado.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Historia del modelo
Sustento biológico
Modelos HP y 2D HP
En el caso de la figura, las líneas continuas representan el camino
seguido por la secuencia original y las líneas punteadas
representan los contactos H-H necesarios para el cálculo de
energía según el método antes mencionado.
En la conformación del ejemplo la
energía tendría un valor de
-9, la cual se sabe que es óptima para
la secuencia utilizada
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Historia del modelo
Sustento biológico
Modelos HP y 2D HP
Más específicamente, una conformación c con cexactamente
tales contactos H-H
n tiene una energía libre

de
E ( c )  n  (  1)
El problema de 2D HP PFP puede ser definido entonces mas
formalmente de la siguiente manera:


s  s1 sencontrar
... s n
Dada una secuencia de aminoácidos s = s1s2s3..,
una
2
conformación de minimice la energía de s, es decir, encontrar sc* tal
que E(c*) = min{E(c)
C(s) es
c * | c e C} E, (donde
c *)  min
E (el
c )conjunto
| c  C de todas
Clas
( s conformaciones
)
válidas de s.
s
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
El Ant Colony Optimization (ACO por sus siglas en inglés) es un
enfoque basado en poblaciones para resolver problemas de
optimización combinatoria inspirado en la naturaleza exploradora
de las colonias de hormigas.
El enfoque subyacente del ACO es el de un proceso iterativo en el
cual una población de agentes simples (“hormigas”) construye
repetidamente posibles soluciones a los problemas abordados.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Este proceso de construcción está probabilísticamente guiado tanto
por información heurística de la instancia dada del problema como
por una memoria compartida que contiene la experiencia
recolectada por las hormigas en iteraciones previas (“rastro de
feromona”).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
En el trabajo estudiado (A. Shmygelska et al. 2002) se analiza un
algoritmo ACO para resolver el problema de Plegamiento de
Proteínas usando el modelo 2D HP.
Cabe mencionar que dicho trabajo fue seleccionado como el mejor
trabajo presentado durante el ANTS 2002: From Ant Colonies to
Artificial Ants 3rd International Workshop on Ant Algorithms –el más
importante taller internacional dedicado a aplicaciones de ACOrealizado en Bruselas, Bélgica, en Septiembre del 2002
Seguidamente se analizan mejoras posteriores (por los mismos
autores en 2003 y 2005) aplicadas a dicho algoritmo y se
comparan los mismos con las mejores soluciones algorítmicas
conocidas en la actualidad para el mismo problema o ligeras
variaciones del mismo.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
En el trabajo se usan instancias del problema utilizadas por
implementaciones anteriores (usando otros métodos) según muestra la
siguiente tabla:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Las hormigas del algoritmo construyen conformaciones candidatas por
medio del algoritmo ACO para una secuencia HP de proteínas dada y
luego aplica búsqueda local para lograr mejores resultados.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Las conformaciones candidatas son representadas por medio de motivos
de estructura local (o direcciones de plegado relativas) straight (S), left (L)
y right (R) los cuales indican, para cada aminoácido, su posición siguiente
en el retículo 2D con relación a su predecesor directo tal como se muestra
en la figura siguiente:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Ya que las conformaciones son invariantes con respecto a las rotaciones, la
posición de los primeros 2 aminoácidos de la secuencia pueden ser fijados
en cualesquiera dos lugares adyacentes del retículo sin pérdida de
generalidad.
A partir de esta observación, se representan las conformaciones
candidatas para una secuencia proteica de longitud n por una secuencia
de motivos de estructura locales de longitud n-2.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Por ejemplo, a la secuencia usada anteriormente
(HPHPPHHPHPPHPHHPPHPH), correspondería la secuencia de motivos
LSLLRRLRLLSLRRLLSL según se puede apreciar en la siguiente figura:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
En la fase de construcción del algoritmo, cada hormiga determina de
manera aleatoria un punto de inicio dentro de la secuencia proteica.
Esto se hace eligiendo una posición de la secuencia entre 1 y n-1 de
acuerdo a una distribución aleatoria uniforme y asignando arbitrariamente
al correspondiente aminoácido (H o P) y a su sucesor directo dos
posiciones vecinas dentro del retículo 2D.
A partir de este punto de inicio cada secuencia es plegada en ambas
direcciones, añadiendo un aminoácido a la vez.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Las posiciones relativas hacia las cuales la conformación va extendiéndose
en cada caso se determinan aleatoriamente usando una función heurística
y valores de feromona (también llamados intensidad del rastro).
Estas direcciones relativas corresponden a motivos estructurales locales
entre triples de secuencias consecutivas de las posiciones .i-1 s si+1que
srepresentan
ss
los componentes de la solución obtenida a partir del ACO.
i 1 i i  1
Conceptualmente, estos motivos juegan el mismo rol que las aristas
(distancias) entre ciudades en la aplicación clásica del ACO al TSP
(Clásico Problema del Viajante de Comercio).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Al extender una conformación de la posición i hacia
i la derecha
s i  1 la retícula el algoritmo usa valores de
colocando el aminoácido si+1en
feromona ti,d y valoresheurísticos
ni,d donde d e {S,
es
 i ,L,d R}
i ,d
una
S , L , Rrelativa.

d dirección
 i , d guiar el proceso de
Los valores heurísticos utilizados ni,d deben
construcción hacia soluciones de alta calidad, esto es, hacia
conformaciones con un número máximo de interacciones H-H.
En el algoritmo esto es logrado al definir ni,dbasados
en hi+1,,hes
decir,
i ,d
i 1, d
en el número de nuevos contactos H-H obtenidos al colocar si+1 en la
s i 1
dirección
d relativa a si y si-1 cuando
s i estamos
s i 1 plegando hacia adelante (y
análogamente cuando se pliega hacia atrás)
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
s i 1=P,Peste aminoácido no puede contribuir a ningún
Nótese que si Si+1
nuevo contacto H-H por lo cual hi,S = hi, L =hihi,
R. h. i ,Más
 haún,
para
0 1<i<
,S
L
i,R
n- 1, hi,d1<=
 i 2 yn  1 h n 1. , d  3 h i , d  2
En cada caso, los valores de hi,d hpueden
ser fácilmente determinados
i ,d
revisando los 7 posibles vecinos de la posible solución de si+1 en la
s i  1 la posición de si esta ocupada y no debe ser
s i tomada
retícula (obviamente
en cuenta).
 hi , d  1
Los valores heurísticos son entonces definidos como ni ,d = 
hi,d
i , d , esto
asegura que ni,d > 0i ,para
 0todos los i y d, lo cual es importante ya que
d
impide excluir a priori algún lugar de Si+ en el proceso de construcción.
s i 1
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
s i  1 el
Al extender una conformación parcial sk...ss ik hacia
... s i si+1 durante
proceso de construcción del algoritmo ACO, la dirección relativa d de
Si+1s icon
respecto a s i-1sisesta
determinada basada en la heurística y los
i 1
1
valores de feromona de acuerdo a las siguientes probabilidades:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
A partir de su punto de inicio aleatoriamente determinado l, cada
l
s1 otra
hormiga primero construye una conformación parcial s..l...s1 syl ...
luego
s l ... s n
sl...sn.
Se probaron variantes del algoritmo en la cuales todas las hormigas
iniciaban el proceso de construccion desde el mismo punto (inicio, medio y
fin de la secuencia).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Especialmente en el caso de secuencias largas, es frecuente encontrar
conformaciones infactibles durante el proceso de construcción. Esto pasa si
una conformación incompleta no puede ser extendida mas allá de una
posición de la retícula por estar ocupados todos las posiciones vecinas de
dicha posición.
El algoritmo usa dos mecanismos para solucionar este problema:.
Primero, usa un sencillo mecanismo de "mirar hacia adelante" al nunca
permitir que un aminoácido "interno" si (1 < i < n)
s i sea
(1 colocado
i  n ) en un
lugar tal que todas sus posiciones vecinas en la retícula están ocupadas
(esto es barato computacionalmente ya que puede ser chequeado
fácilmente durante el cálculo del valor heurístico).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Segundo, si durante un paso de la construcción todas las posiciones de si
son descartadass ipor el mecanismo anterior, se retrocede hasta la mitad
de la distancia ya plegada y se reinicia el proceso de construcción desde
la posición respectiva en la secuencia.
Es interesante notar que se probaron varias modificaciones a este
mecanismo de retroceso y que se utilizó esta basados en que probó ser
razonablemente rápida y efectiva.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
De manera similar a lo utilizado en otros algoritmos ACO conocidos, el
algoritmo estudiado incorpora una fase de búsqueda local.
En esta, después de cada fase de construcción, cada hormiga aplica una
búsqueda local híbrida de mejora iterativa para su conformación
candidata respectiva.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Después de cada fase de construcción y búsqueda local, hormigas
seleccionadas actualizan los valores de feromona según el método
estándar:
Donde
es la persistencia de la feromona (un parámetro que
determina que tan rápido la información recolectada en iteraciones
previas es “olvidada”) y .............es la calidad relativa de la solución para
la conformación candidata c de la hormiga dada si tal conformación
contiene un motivo de estructura local d en la secuencia en la posición i y
cero en caso contrario.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Se usa una formula de calidad relativa para cada solución dada por E(c)
/ E* donde E* es la energía mínima conocida para la secuencia de
proteínas dada (o una aproximación basada en el numero de residuos H
de la secuencia), esto para prevenir estancamiento prematuro en la
búsqueda para secuencias con valores energéticos altos.
Como un mecanismo adicional para prevenir estancamiento se usa un
método de renormalización de los valores de feromona conceptualmente
similar al método usado en el Sistema de Hormigas MAX-MIN (Stutzle &
Hoos, 1997).
Esto garantiza que la probabilidad de elegir un motivo de estructura local
para la correspondiente posición en la secuencia no se vuelva
arbitrariamente pequeña.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Como mencionamos con anterioridad, el algoritmo fue probado en 9
instancias de prueba estándar, a saber:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Como puede verse a partir de la tabla, el algoritmo encontró soluciones óptimas
para todas menos para las dos secuencias más largas de las instacias de prueba
utilizadas.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
También puede observarse la comparación efectuada entre el algoritmo con
búsqueda local y sólo la búsqueda local. Se puede ver que en todos los casos fue
mejor y mas rápida la combinacion de ambas cosas con lo cual se aisla el valor
propio del algoritmo sin la búsqueda local.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Con respecto a los detalles de la implementación:



Los experimentos fueron conducidos realizando un número variable de
corridas para cada instancia del problema; cada corrida fue terminada
cuando no fue encontrada mejora en la calidad de la solución en 10,000
ciclos del algoritmo.
Se usaron 10 hormigas para secuencias pequeñas (s <= 25) y 10-15
para secuencias mas largas.
Se fijaron los valores de los parámetros básicos del algoritmo en:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Con respecto a los detalles de la implementación:




El procedimiento de búsqueda local fue terminado cuando no se
observaba mejora a la solución después de 100-300 pasos de la
búsqueda.
Se usó un método de actualización de feromona elitista en el cual solo el
20% mejor de las conformaciones obtenidas después de la fase de
búsqueda local fue usada.
Adicionalmente, la mejor conformación global fue utilizada para
actualizar el valor de feromona cuando no fue encontrada una mejora a
la mejor solución global dentro de 20-50 ciclos.
El tiempo de ejecución fue medido en términos de tiempo de CPU y todos
los experimentos fueron realizados en PCs con procesador Pentium III a 1
GHz, 256KB de cache y 1GB de RAM.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Con respecto a los detalles de la implementación:



El procedimiento de búsqueda local fue terminado cuando no se
observaba mejora a la solución después de 100-300 pasos de la
búsqueda.
Se uso un método de actualización de feromona elitista en el cual solo el
20% mejor de las conformaciones obtenidas después de la fase de
búsqueda local fue usada.
Adicionalmente, la mejor conformación global fue utilizada para
actualizar el valor de feromona cuando no fue encontrada una mejora a
la mejor solución global dentro de 20-50 ciclos.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Como puede verse a partir de la tabla, el algoritmo encontró soluciones óptimas
para todas menos para las dos secuencias más largas de las instancias de prueba
utilizadas.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Una gráfica de mediciones de run-time distributions (RTD) fue utilizada basada en
los trabajos que en esta metodología hicieron Hoos y Stutzle (2000) para aquellas
secuencias en las que se obtuvo el valor óptimo más de una vez. Los resultados se
pueden apreciar en la siguiente grafica:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
En la gráfica puede observarse evidencia de estancamiento en las secuencias mas
largas; en el trabajo se sugiere que en estos casos una mejor heurística y/o una
mejor búsqueda local podrían mejorar los resultados obtenidos.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Buscando evaluar el beneficio de usar una población de hormigas en lugar de una
sola hormiga se estudió el impacto de variar el número de hormigas para el
algoritmo. Si bien usando una sola hormiga se obtuvieron buenos resultados para
instancias pequeñas (n <= 25) la mejor solución al problema 4 (n=36) no pudo ser
encontrado después de una corrida de 2 horas de CPU.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Como en otros casos donde ha sido utilizado el algoritmo, en esta caso también la
estrategia de actualización de feromona basada en un criterio elitista también
parece aplicar a este problema: Se probaron 3 tipos de actualizaciones diferentes:
1) Todas las hormigas.
2) Todas las hormigas con refuerzo para el 20% mejor de las hormigas.
3) Solo el 20% mejor de las hormigas.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Los resultados obtenidos pueden ser apreciados en la siguiente gráfica:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Como puede verse, los mejores resultados fueron obtenidos a partir de las
estrategias donde se actualizaba a partir de los resultados (únicos o reforzados)
del mejor 20% de las hormigas.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Esto sugiere que la intensificación en la búsqueda provista por la
estrategia antes mencionada se requiere para alcanzar un buen
rendimiento en el algoritmo ACO utilizado.
Al mismo tiempo, experimentos adicionales no reportados en el trabajo
pero mencionados en el, indican que el mecanimo de renormalizacion de
feromona es crucial para resolver instancias grandes del problema, lo cual
subraya la importancia de la diversificación de la búsqueda (escape de
mínimos locales).
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
El siguiente análisis estudio la importancia relativa de la heurística contra la de la
feromona. Los resultados se muestran en la siguiente grafica:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Como puede apreciarse, en principio ambos valores probaron ser importantes en
los resultados obtenidos.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Es interesante observar que eliminar la influencia de la feromona es más perjudicial
que eliminar la influencia de la heurística aún para casos pequeños. Este fenómeno
se hace más pronunciado a medida que se intentan resolver instancias mayores del
problema.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática


Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
Finalmente, se estudiaron el efecto del punto de inicio en la construcción de las
conformaciones en el rendimiento final del algoritmo.
Con tal fin, se probaron 4 estrategias para determinar la posición inicial desde el
cual iniciar las conformaciones en la etapa de construcción del algoritmo:
1) Todas las hormigas pliegan hacia adelante iniciando en la posición 1.
2) Todas las hormigas pliegan hacia atrás iniciando en la posición n
3) Todas las hormigas pliegan hacia adelante y hacia atrás iniciando en la mitad
de la secuencia
4) Todas las hormigas pliegan hacia adelante y hacia atrás iniciando en posiciones
aleatoriamente determinadas de la secuencia.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Algoritmo de Hormigas
Fase de construcción, feromona y valores heurísticos
Búsqueda Local
Actualización de feromona
Resultados obtenidos
La cuarta estrategia, es decir, la de que cada hormiga iniciara en una posición de la
secuencia elegida aleatoriamente y de allí plegara en un sentido y luego en el otro, mostró
ser con mejor que las demás. Esta diferencia es aún mayor en secuencias mas largas y sugiere
que la diversificación de la búsqueda aportada por múltiples y diversos puntos de inicio es
importante para lograr un buen rendimiento.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Trabajos posteriores
ACO 2003 y 2005
Como una de las conclusiones del trabajo presentado (2002) se menciona que si
bien no se pudieron mejorar los logros de los mejores algoritmos conocidos para las
instancias del problema estudiadas, los resultados eran muy alentadores y la
implementación dejaba sin lugar a dudas enseñanzas valiosas que podrían
aprovecharse en trabajos futuros.
Estos resultados no tardaron en llegar ya que el mismo grupo de investigación
(liderado por Shmygelska y Hoos) siguieron trabajando en mejoras sucesivas al
algoritmo con resultados muy interesantes.
En particular se presentaron trabajos en el 2003 y el 2005, siendo los resultados
de este último casi tan buenos como los mejores algoritmos conocidos hasta el
momento.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Trabajos posteriores
ACO 2003 y 2005
Algunas de las mejoras que se fueron incorporando al algoritmo original incluyen:
•
Método de búsqueda local (2003 y 2005)
•
Estrategia para avanzar en el plegado hacia adelante o hacia atrás (2003)
•
•
•
•
Hormigas de mejora aplicadas no solo al mecanismo global sino también a las
mejoras locales (2003)
Mucho mayor cantidad de hormigas (2003, 2005)
Se incorporan soluciones de muy alto rendimiento al problema en su versión
3D (2005)
Definición de la fórmula heurística basada ahora en la distribución de
Boltzman (2005)
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática



Otros Algoritmos
Existe una gran cantidad de trabajos para resolver el 2D HP PFP con un enfoque
computacional.
Entre estos se incluyen: Enfoques desde los algoritmos geneticos, variantes y
enfoques clásicos del método de Monte Carlo (siendo uno de estos, el llamado
PERM –Prune Enrichement Rosenbluth Method, acaso la solución computacionalmente
más exitosa entre las que se conocen) Algoritmos con Tabu Seach, Simulated
Annealing, etc. además de varios métodos de solución específicos al problema.
Es importante notar que el problema ha sido además extensamente atacado en
años recientes por lo cual es dificil entender en cada momento cual es la mejor
implementación de todas aún para las instancias más comunes del problema.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática

Otros Algoritmos
De una novedosa implementación reciente (Filter-and-Fan approach. Rego et al.
2006) obtuvimos una tabla más o menos reciente con los mejores algoritmos en ese
momento:
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Algunas aplicaciones biológicas
La era de las “OMICs” de la Biología Molecular
Algunas aplicaciones biológicas
Acoplamiento proteína-proteína
Anotación de genomas
Análisis de imagen de alto rendimiento
Biología evolutiva computacional
Análisis de la expresión de proteínas
Genómica comparativa
Análisis de la expresión génica
Medición de la biodiversidad
Análisis de la regulación
Modelado de sistemas biológicos
Análisis de mutaciones en el cáncer
Predicción de la estructura de las
proteínas
Análisis de secuencias
Hoy en día, son cada vez más los congresos, tales como el MAEB (Congreso sobre
Metaheurísticas, Algoritmos Evolutivos y Bioinspirados), que tienen como principal
objetivo reflejar el estado del arte respecto al uso de las técnicas metaheurísticas y
bioinspiradas en aplicaciones biológicas y/o biomédicas.
El problema del Plegado de Proteínas
Modelo 2D HP PFP
ACO aplicado a 2D HP PFP
Mejoras sucesivas al ACO
Otros algoritmos aplicados
Otros Problemas de la Bioinformática
Algunas aplicaciones biológicas
La era de las “OMICs” de la Biología Molecular
La era de las “OMICs” de la Biología Molecular







Genómica (Genomics): estudio de los genomas de los organismos (secuenciación, mapeo e
interacciones génicas).
Proteómica (Proteomics): estudio de todo el complemento proteico en un sistema u organismo.
Transcriptómica (Transcriptomics): todos los ARN mensajeros (ARNm) o "transcriptos", producidos
por una célula o un conjunto de células.
Metabolómica (Metabolomics): mapa completo de todos los metabolitos moleculares pequeños
en el cuerpo humano (metaboloma humano)
Genómica Estructural (Structural Genomics): determinación de la estructura 1D, 2D y 3D de
todas las proteínas en un organismo dado.
Informática (Informatics): aplicación de tecnología de la información al campo de la Biología
Molecular.
Farmacogenómica (Pharmacogenomics): identifica las bases genéticas para la herencia y
variación interindividual en respuesta a drogas.
Descargar

www-2.dc.uba.ar