Download Clase sobre predicción de genes

Predicción de genes
Taboada, Fernando
Gómez Germán
Definición: predicción de genes

Para una secuencia de DNA no caracterizada
identificar la presencia de genes que
codifican proteínas.

Se habla de predecir o buscar genes.
Definición: predicción de genes

Dada una secuencia de DNA se puede
encontrar:






Qué región codifica para una proteína.
Qué hebra codifica el gen.
Cuál es el marco de lectura.
Dónde comienza y termina el gen.
Dónde comienza y terminan los intrones/exones.
Opcionalmente se encuentran las regiones
regulatorias del gen.
Transcripción y
traducción
Estructura de los genes
Eucariotas vs. procariotas

Procariotas




Genomas pequeños
Alta densidad de genes
Sin intrones
Identificación de genes
es relativamente simple

Eucariotas




Genomas grandes
Baja densidad de genes
Intrones y exones
Identificación de genes es
un problema complejo
Predicción de genes en procariotas y
eucariotas

Predecir genes que codifican a proteínas es más fácil en
procariotas que en eucariotas. Algunos motivos:
- procariotas carecen de intrones
- patrones de secuencia altamente conservados se
encuentran con gran frecuencia en regiones promotoras
y alrededor de zonas de comienzo de transcripción y
traducción.
Señal - una región en el ADN reconocida por la
maquinaria celular
Estrategias de predicción de genes

Basados en similitud (extrínsecos)

Usan herramientas de alineamiento local para
comparar contra secuencias anotadas (proteínas,
cDNAs, Est)


Pros: se basan en información biológica preexistemte
Contras:




limitado a información preexistente
errores en las bases de datos
difícil comparar los limites de un gen en base a similitud
hay métodos más rápidos que comparar contra base de
datos
Estrategias de predicción de genes

Métodos intrínsecos




Secuencias consenso, matrices de score
Modelos ocultos de Markov
Redes neuronales
Estrategias integradoras
Estrategias de predicción de genes

Métodos intrínsecos




Secuencias consenso, matrices de score
Modelos ocultos de Markov
Redes neuronales
Estrategias integradoras
Búsqueda de Open Reading Frames
(ORF)



ORF es una porción de DNA que contiene un
conjunto contiguo de codones que codifican
aminoácidos.
Forma más simple de buscar secuencias que
codifican proteínas.
En cada secuencia hay 6 posibles ORFS: 3
comenzando en las posiciones 1, 2 y 3 llendo
en la dirección 5’ 3’ de una secuencia y su
complementaria.
Búsqueda de Open Reading Frames
(ORF)


En procariotas el mayor ORF comenzando
desde el primer codón de start hasta el
primer codón de stop es una buena (pero no
segura) predicción de una región que codifica
proteínas.
En eucariotas es algo más complejo debido a
la presencia de intrones que suelen generar
codones de stop.
Cómo testear una predicción de ORF

Nos podemos basar en las siguientes propiedades:




Las secuencias codificantes no son una cadena al azar de
posibles codones (nonrandom property).
Cada especie tiene patrones característicos de uso de
codones sinónimos (codifican para el mismo aminoácido)
Hay pares de codones que suelen aparecer en exones de
secuencias eucariotas.
Por ejemplo en E. Coli hay cierta preferencia de pares de
codones en las regiones codificantes y de ciertos codones
en la zona siguiente al codon de stop.
Cómo testear una predicción de ORF

En base a las propiedades anteriores hay 3 tests:



1. Se basa en que toda tercera base tiene más chance de
ser la misma que de cambiar (TestCode)
2. Es un análisis que determina qué codones en el ORF
son los mismos que se utilizan en otros genes del mismo
organismo (CODONFRECUENCY).
3. El ORF es traducido en una secuencia de amino ácidos
y luego comparado contra otras secuencias de amino
ácidos de proteínas base de datos existentes.
TestCode






La cantidad de cada base es contada en todas las terceras
posiciones comenzando en las posiciones 1,2 y 3.
Para cada base se calcula el máximo de los 3 marcos de
lectura dividido el minimo más 1 (asymmetry score).
Se calcula la frecuencia de cada base (frecuency score)
Los scores son convertidos en probabilidades
Las probabilidades son multiplicadas por factores
determinados de manera tal que discriminen zonas
codificantes de no codificantes y luego son sumadas.
Si el valor resultante es mayor a 0.95 la secuencia codifica,
si es menor a 0.74 no codifica.
Estrategias de predicción de genes

Métodos intrínsecos




Secuencias consenso, matrices de score
Modelos ocultos de Markov
Redes neuronales
Estrategias integradoras
Secuencias consenso



Representan la secuencia del motivo para
una cierta mayoría de ejemplos.
Ejemplo: obtenidas por selección de la base
más frecuente en cada posición de un
alineamiento múltiple.
Desventaja: pueden producir muchos falsos
positivos o falsos negativos.
Positional weight matrix

Positional weight matrix
 Se calcula midiendo la frecuencia de cada elemento para
cada posición en el sitio
 El score para cada sitio putativo es la suma de los valores
de la matriz (convertidos en probabilidades) para esa
secuencia

Desventaja: supone independencia entre bases adyacentes
TACGAT
TATAAT
TATAAT
GATACT
TATGAT
TATGTT
1 2 3 4 5 6
A
C
G
T
0
0
1
5
6
0
0
0
0
1
0
5
3
0
3
0
4
1
0
1
0
0
0
6
Estrategias de predicción de genes

Métodos intrínsecos




Secuencias consenso, matrices de score
Modelos ocultos de Markov
Redes neuronales
Estrategias integradoras
Modelos ocultos de Markov






Alfabeto
Conjunto de estados
Probabilidades de transición entre estados
Probabilidades de emisión dentro de un
estado
Probabilidades iniciales de transición
3 problemas: evaluación, decodificación y
aprendizaje
HMM para predicción de genes




Los estados del modelo corresponden a las
unidades funcionales de un gen.
Las transiciones entre estados son de
manera tal que aseguren que la forma en
que el modelo marcha sea biológicamente
consistente.
HMM es entrenado o calibrado con genes
conocidos para estimar los parámetros
Se busca la secuencia de estados Pi que
maximiza P(x,Pi).
HMM para predicción de genes



Se generan estados para elementos límites (start,
stop,…) y para regiones de longitud variable.
Las regiones suelen ser intrones, exones y regiones
intergenicas. Una region intergénica es una
secuencia de codones que no codifica a ninguna
proteína.
A su vez los exones son divididos en iniciales,
internos y externos.
HMM para predicción de genes
Modelo simple de un HMM sin intrones:
En cada estado se generan nucleótidos con cierta
probabilidad

HMM para predicción de genes

Modelo simple de un HMM que tiene en cuenta
intrones, exones y alguna señales:
B = gene start
S = translation start
D = donor
A = accceptor
T = translation stop
E = gene end
HMM para predicción de genes




Inicialmente para los elementos límite se
usaban secuencias consenso.
Las regiones suelen ser modeladas con
modelos de Markov de orden mayor a 6.
Las conexiones entre estados se utilizan
tanto para modelar los diferentes marcos de
lectura como la longitud de cada
componente.
Como los genes pueden ocurrir en ambas
direcciones, los HMM suelen ser espejados.
HMM para predicción de genes

El modelo leerá una secuencia de ADN y encontrará los genes
más parecidos al conjunto con los cuales se entrenó o calibró
el modelo.

Como el uso de codones y secuencias de cambio puede variar
de un genoma a otro entonces el entrenamiento deberá
hacerse por genoma.

La precisión del modelo depende de
- la precisión de la información respecto al comienzo
(start) y fin (stop) del gen con la que se entrena o
calibra el modelo
- el número de genes usado para entrenar.
Uso de HMM para predicción de genes
Algoritmo para generar una secuencia de DNA de longitud L
Set n=1
Hacer {
Si n=1 elegir estado q1 de acuerdo a las probabilidades
iniciales
Sino elegir estado qn en base a las probabilidades de
transición del estado actual
Elegir dn de acuerdo a la distribución de longitudes para el
estado qn
Elegir un string sn de longitud dn de acuerdo al modelo
probabilistico del estado qn

} Hasta que la suma de los dn sea mayor a L
Uso de HMM para predicción de genes

Para encontrar el conjunto de estados Pi que maximizan P(x, Pi)
se utiliza el algoritmo de Viterbi:
Input: x = x1……xN
Inicialización:
V0(0) = 1
Vk(0) = 0, para todo k > 0
(0 es la posición inicial)
Iteración:
Vj(i)
= ej(xi)  maxk akj Vk(i-1)
ptrj(i) = argmaxk akj Vk(i-1)
Terminación:
P(x, *) = maxk Vk(N)
Rastreo:
N* = argmaxk Vk(N)
i-1* = ptri (i)
Combinando HMM con redes neuronales



Combinar poder de expresividad de las redes
neuronales con el aspecto secuencial de los
HMM.
RN re utiliza para reparametrizar y modular el
HMM. La idea básica consiste en utilizar RN
en el tope de los HNN para el calculo de las
funciones de transición y emisión.
Ambos modelos son entrenados con
algoritmos unificados
GenMark para procariotas
GenMark.hmm para procariotas
GenMark.hmm
para eucariotas
GenScan para
eucariotas
HMM de 5to orden

El análisis de codones secuenciales en genes ha mostrado que
algunos pares de bases se encuentran con mayor frecuencia
que la esperada por sí solas. Considerando ésto tendríamos un
HMM lineal.

Una mejor elección es un modelo que use información desde el
5ta base anterior. O sea utilizar un HMM de 5to orden.

En lugar de usar pares de bases para diferenciar secuencias
codificantes de no codificantes se usan hexámeros (la base
actual más las 5 anteriores).

GenMark.HMM es una versión de GenMark que usa un HMM de
5to orden para buscar genes E. coli.
HMM de 5to orden






Problema:
HMM de 5to orden dará predicciones de genes precisas si hay
varios representantes de cada hexámero en los genes, de lo
contrario el método estará estadísdicamente limitado.
Solución:
IMM (interpolated Markov model) busca los posibles patrones más
largos (de hasta 8 bases) presentes en secuencias de genes
conocidos. Si no hay suficientes hexámeros entonces buscará
pentámeros y así sucesivamente.
En general cuanto más largo es el patrón más precisa es la
predicción.
IMM combina probabilidades de los patrones con distintos tamaños
dando énfacis a los patrones de mayor longitud y otorgando mayor
peso a las secuencias bien formadas en las secuencias de
entrenamiento.
HMM de 5to orden
Problema

Tanto GenMark.HMM como IMM asumen que la
predicción de genes hecha por otros métodos son
precisos, tal es el caso de los métodos usados para
determinar la similitud entre las secuencias de las
proteinas traducidas y las conocidas proteinas de la E.
coli.

El resultado de ésto podrían ser predicciónes
confiables de genes que NO se corresponden con
ninguna secuencia de ninguna proteina ya conocida.
HMM de 5to orden
Solución

Existe una mejora de la predicción de la posición del codón de
comienzo.

El método consiste en tomar un conjunto de predicciones para
un codón de start en un conjunto de secuencias para el cual sí
se conoce la posición del codón.

Se otorga un determinado peso a cada conjunto de secuencias
input

Los pesos se ajustan de manera tal que las predicciones se
hacen más precisas por un método llamado programación entera
mixta.
Estrategias de predicción de genes

Métodos intrínsecos




Secuencias consenso, matrices de score
Modelos ocultos de Markov
Redes neuronales
Estrategias integradoras
Redes neuronales: Grail II

Usado para encontrar exones en genes de eucariotas.

Provee analisis de regiones codificadoras de
proteinas, poly(A) y regiones promotoras y realiza
búsqueda en bases de datos.

El método usa una red neuronal para identificar
patrones carácterísticos de secuencias codificantes.

El sistema es entrenado con secuencias codificantes
conocidas.
Redes neuronales: Grail II
Se establecen candidatos de exones.
 Son evaluados utilizando una red neuronal
 La red neuronal tiene 3 capas:



una capa de input, que tiene la información del
exon candidato.
Una capa hidden para discernir relaciones entre
los valores de entrada.
Una capa de output que indica si efectivamente
es un exon
Redes neuronales: Grail II
Redes neuronales: Grail II






Inputs:
Indicadores de patrones de secuencia.
Modelo de Markov.
Resultados de lugares de splice (splice
sites)provenientes de otras dos redes
neuronales.
Indicador de preferencia de 6-mer
(hexámeros).
Etc.
Redes neuronales: Grail II





Output
Cada neuron recibe información de la capa inferior, la
suma y la convierte en un valor de aprox. a 0 o 1.
Si la salida de la red neuronal el un valor próximo a 1
ent. se predice que la secuencia candidata es exon.
La secuencia candidata es evaluada calculando
frecuencias de patrones en la secuenciasy aplicando
estos valores a la red neuronal.
Si la salida de la red neuronal el un valor próximo a 1
ent. se predice que la secuencia candidata es exon.
Redes neuronales: GeneParser




Predice la combinación de intrones y exones más
probable mediante el uso programación dinámica y
redes neuronales.
Para cada posición de la secuencia se determina la
probabilidad de estar en un intrón o exon .
Las posiciones de intrones y exones son alineadas
con la restricción de que deben alternar en el gen.
Output: secuencia de intrones y exones del gen.
Redes neuronales: GeneParser


Provee mecanismos para ajustar los pesos
asignados a cada tipo de patrón que aparece en
intrones y exones.
La red neuronal se usa para ajustar los pesos
dados a
- indicadores de secuencia de regiones
conocidas de intrones y exones.
- uso preferencail de codones
- frecuencia de hexámeros
- matrices de scoring para señales de
splicing
Redes neuronales: GeneParser
1.
Se prepara una tabla de frecuencia de hexameros para un conjunto
de exones.
2.
Iteramos, para cada secuencia de entrenamientose hace lo siguiente
2.1
Se arman matrices indicadoras.
- Una matriz tal que cada posición (i,j) representa una subsecuencia
con principio en la posición i y fin en la j de la secuencias. Cada
posición contiene la probabilidad de que un exon comience y
termine en tales posiciones. Para ésto se considera la frecuencia de
hexámeros.
- Basta con usar media matriz.
- En la otra mitad se hace lo mismo pero para intrones.
- Se arman otras matrices basadas en distribución de longitudes,
señales de splice, etc.
Redes neuronales: GeneParser
2.2 Cada uno de los valores (i,j) de la matriz es
transformado según un pero asignado. Los pesos
iniciales usados son arbitrarios, luego son
ajustados hasta proveer la correcta estructura de
la secu. de entrenamiento.
2.3 Se suman lo nuevos valores, s, y se transforma
el resultado en un número L próximo a 0 ó 1
L = 1/ [ 1 – h ]
donde h es e elevado a -s
Redes neuronales: GeneParser
2.4.. Los valores (i,j) transformados son puestos en
nuevas matrices Le y Li para exones e intrones.
Ambas matrices son medias matrices.
2.5. El fin de estas transformaciones es usar esta
información como input de la red neuronal.
2.3
Se usa programación dinámica para predecir el
número y longitudes de intrones hasta cualquier
posición de la secuencia de entrenamiento.
Redes neuronales: GeneParser
3.
Se determina la presición de la predicción.
4.
Si no se alcanza el nivel de presición requerido se
usa una red neuronal parecida a la de Grail II para
ajustar los pesos de la características de cada
exon e intrón input.
5.
Si el nivel de presición es alcanzado es método
está listo para determinar la estructura de
secuencias genómicas de DNS desconocidas.
Estrategias de predicción de genes

Métodos intrínsecos




Secuencias consenso, matrices de score
Modelos ocultos de Markov
Redes neuronales
Estrategias integradoras
Estrategias integradoras



Hay otros programas que combinan métodos
intrínsecos y extrínsecos, por ejemplo,
GenomeScan, FGENESH+, Procrustes
Otras posibilidad es combinar predicciones
de diferentes programas
Por ejemplo, combinar GenScan y
HMMGene que son los mejores candidatos
Evaluación de resultados

A nivel de la secuencia
TN
FN
TP
FP
TN
FN
TP
REALITY
PREDICTION
Sensibilidad
Sn 
TP
TP  FN
Especificidad
Sp 
TP
TP  FP
FN
TN
Evaluación de resultados

A nivel de los exones
Incorrect
Correct
Missing
Reality
Prediction
Sensibilidad
C
ESn 
ER
Especificidad
C
ESp 
TP
Conclusiones



La mayoría de los tests se entrenan sobre
secuencias particulares, por lo cual funcionan mejor
en la predicción de genes similares al set de
entrenamiento.
Muchos métodos requieren para funcionar predecir
un comienzo y fin concretos con lo cual van a
cometer errores frente a genes truncados o
múltiples genes.
Hay genes que no tienen ninguna estructura
canónica, por lo que no pueden ser detectados por
ningún método actual.
Bibliografía






David W.Mount. Bioinfoimatics – Sequence and
Genome Analysis.
Durbin et al. Biological Sequence Analysis – Probabilistic
models of proteins and nucleis acids.
Meidanis y Setubal. Introduction to Computational
Molecular Biology
Brunak. Chapter 9, Probabilistic Graphical Models in
Bioinformatics.
Larry Ruzzo. Lecture 9, Gene Prediction, II
Diapositivas de la cátedra.