Download Predicción de Genes

Predicción de Genes
Jesús Alejandro Hernández Mejía
Cinvestav-Zacatenco
2 de Julio de 2013
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
1 / 52
1
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
2 / 52
Predicción de genes
1
Introducción
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
3 / 52
Predicción de genes
Introducción
Introducción
En los años recientes ha habido una rápida acumulación de
información genómica que necesita ser procesada para predecir la
estructura de los genes. Dicho proceso incluye la detección de marcos
abiertos de lectura (ORF’s) así como la descripción de exones e
intrones en organismos eucariotas. El objetivo principal es describir
todos los genes en una cadena de ADN con 100 % de precisión .
Sin embargo, la predicción de genes representa uno de los problemas
más difíciles en el área, debido a que las regiones codificantes
(regiones compuestas de exones que codifican proteínas) no suelen
tener motivos conservados.
La predicción de genes en general no sólo incluye la identificación de
genes codificantes de proteínas, sino también genes codificantes de
ARN o de regiones reguladoras.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
4 / 52
Predicción de genes
Introducción
Introducción
Ha habido mucho progreso en la predicción de genes procariotas, con
varios algoritmos que presentan diversos grados de éxito. Sin embargo,
para organismos eucariotas, aún no hay resultados satisfactorios.
Esto se debe a que los organismos eucariotas son más complejos que
los procariotas, recordemos que estos últimos generalmente no tienen
intrones y están compuestos de una sola hebra de ADN que es
relativamente pequeña (de 0.5 a 10 Mbp)
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
5 / 52
Predicción de genes
1
Categorías de los programas de predicción de genes
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
6 / 52
Predicción de genes
Categorías de los programas de predicción de genes
Categorías de los programas de predicción de genes
Los métodos de predicción de genes actuales se pueden clasificar en
dos categorías principales: ab initio y basados en homología.
El enfoque ab initio se basa en dos características de los genes:
La existencia de señales en genes, éstas señales pueden ser codones de
inicio y parada, sitios de enlaces ribosomales, etc.
El contenido del gen por sí mismo, ya que las regiones codificantes
varían significativamente de las regiones no codificantes. Los modelos
probabilísticos como los modelos ocultos de Markov ayudan a esta
tarea.
Los métodos basados en homología hacen sus predicciones
comparando una secuencia con secuencias conocidas de genes.
Algunos algoritmos pueden hacer uso de ambas estrategias, este tipo
de algoritmos se les conoce como basados en consenso.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
7 / 52
Predicción de genes
1
Predicción de genes en procariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
8 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
El entendimiento detallado de la estructura genética de estos
organismos se vuelve muy útil para la predicción de genes. Veamos
algunos puntos clave:
La densidad de genes es de más del 90 %.
Un gen se compone de una sola tira de un marco abierto de lectura sin
interrupciones.
Hay muy pocas secuencias repetitivas.
La mayoría de los genes tienen un codón de inicio ATG (AUG en ARN).
Aunque también puede haber GTG y TTG como codones de inicio.
Además de los codones de inicio, otra características están asociadas
con la traducción. Un ejemplo es la secuencia de Shine-Dalgarno, esta
secuencia está compuesta por 6 o 7 nucleótidos antes del codón de
inicio y regula la iniciación de la traducción.
Existen tres posibles codones de parada.
Hay genes típicos y atípicos. Los genes típicos varían en longitud desde
100 hasta 500 aminoácidos, mientras que los atípicos son mucho más
cortos.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
9 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Figura : Estructura típica de un gen procariota.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
10 / 52
Predicción de genes
1
Predicción de genes en procariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
11 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Esto nos lleva a concluir que la identificación de genes puede estar
basada en la determinación de ORFs y de las señales principales.
Como primer paso, el ADN se puede traducir a sus seis maneras
diferentes (recordemos que se toman codones de 3 nucleótidos), tres
en un sentido y tres en sentido inverso.
Debido a que un codón de parada puede ocurrir por azar cada veinte
codones, un marco con más de 50 o 60 codones sin codones de parada
es sugerente para ser una región codificante.
El gen supuesto se confirma buscando señales de inicio y la secuencia
Shine-Dalgarno. Posteriormente se traduce a una proteína y se
compara en una base de datos de proteínas.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
12 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Figura : Los seis posibles marcos de lectura
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
13 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Los primeros algoritmos para la predicción de genes se basaron en una
regla empírica. En una región codificante la tercera posición de un
codón suele tener preferencia por la base G o C o suele repetirse
mucho. Esta regla tiende a identificar sólo genes típicos y omite los
atípicos.
La nueva genración de algoritmos de predicción usan modelos
estadísticos más sofisticados.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
14 / 52
Predicción de genes
1
Predicción de genes en procariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
15 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Un modelo de Markov describe la probabilidad de la distribución de los
nucleótidos en una secuencia de ADN, en la que la probabilidad
condicional de una posición particular de la secuencia depende de las k
posiciones previas. En este caso, k es el orden de un modelo de
Markov. Un modelo de Markov de segundo orden se fija en las dos
bases precedentes para determinar a la base que sigue, algo que es
característico en los codones. Entre mayor sea el grado del modelo de
Markov, más precisamente se puede predecir un gen.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
16 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Figura : Un modelo oculto de Markov de segundo orden para predicción de genes
procariotas.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
17 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Los análisis estadísticos han mostrado que la frecuencia de seis
nucleótidos únicos en una región codificante es mucho más alta que
por mero azar. Sería lógico entonces usar un modelo de Markov de
quinto orden. Sin embargo, los modelos de Markov de orden grande no
son eficaces para secuencias de genes cortas.
Para enfrentar esta limitación se usa un modelo de Markov de orden
variable, llamado Modelo de Markov Interpolado (IMM por sus siglas
en inglés). Este método toma una muestra del mayor número de
patrones de secuencias con k desde 1 a 8 y usa un esquema ponderado,
con más peso en k-meros raros y menos en los más frecuentes.
Los genes atípicos tienden a escapar al modelo de Markov. Por tanto,
para tener un algoritmo robusto de predicción, se necesita más de un
modelo de Markov.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
18 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Existen aplicaciones en la red que implementan distintos tipos de
modelos de markov para la predicción de genes de procariotas.
GeneMark - Implementa HMM’s de quinto orden. El programa principal
está entrenado con genomas microbianos. El HMM puede usar el ADN
de un organismo que tenga relación al genoma de entrada o se puede
proporcionar un ADN, siempre y cuando tenga al menos 100 kbp.
También tiene variante para organismos eucariotas.
Glimmer - Implementa un IMM, al igual que GeneMark primero entrena
el modelo y después hace la predicción. También tiene variante para
organismos eucariotas.
FGENESB - Usa HMM’s de quinto orden. Está entrenado con
secuencias de bacterias y usa el algoritmo Vertibi para encontrar el
resultado óptimo.
RBSfinder - Utiliza la salida de Glimmer para buscar las secuencias
Shine-Dalgarno en el vecindario del codón de inicio.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
19 / 52
Predicción de genes
1
Predicción de genes en procariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
20 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
La precisión de la predicción puede ser medida por la sensibilidad y la
especificidad. Recapitulemos los cuatro parámetros y la fórmula de
estas métricas:
Sensibilidad = VP/(VP + FN) Especificidad = VP/(VP + FP)
Donde VP = Verdadero Positivo, VN = Verdadero Negativo, FP =
Falso Positivo y FN = Falso Negativo.
La sensibilidad es la proporción de señales verdaderas predichas de
todas las señales verdaderas las posibles. La especificidad es la
proporción de señales verdaderas predichas de todas las señales
predichas.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
21 / 52
Predicción de genes
Predicción de genes en procariotas
Predicción de genes en procariotas
Para predecir completamente la precisión, se necesita un solo valor que
resuma la especificidad y la sensibilidad. Un valor llamado coeficiente
de correlación (CC) se usa con este fin y está dado por la siguiente
fórmula:
CC = √
VP×VN−FP×FN
(VP+FP)(VN+FN)(FP+VN
El valor de CC varía de -1 a 1 siendo 1 una predicción siempre correcta
y -1 una predicción incorrecta.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
22 / 52
Predicción de genes
1
Predicción de genes en eucariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
23 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Análogamente a como lo hicimos con los procariotas, veamos algunas
características de los organismos eucariotas.
Los genomas son usualmente más grandes que en los procariotas,
variando desde 10Mbp a 670 Gbp, con una densidad de genes mucho
más baja.
El espacio entre genes es usualmente muy grande y rico en secuencias
repetitivas y elementos transponibles.
Lo más importante quizá es que los genomas tienen una organización
en la que la parte codifican de un gen tiene partes intermedias no
codificantes.
La transcripción (de ADN a ARNm) pasa por tres etapas antes de la
traducción de proteínas.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
24 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
La primer fase es el capping (la adición de un nucleótido especial en el
extremo 5’ del ARN)
La segunda fase es el splicing, en que se eliminan los intrones y se
juntan los exones. Esta fase se puede complicar pues los exones se
pueden juntar de diferentes maneras y generan una transcripción
diferente (Splicing alternativo).
La última fase es la adición de un tira de A’s (aprox. 250) en el
extremo 3’.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
25 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
El problema principal en la predicción de genes eucariotas es la
identificación de exones, intrones y posiciones de splicing. El splicing
hace particularmente difícil este problema.
Afortunadamente hay secuencias conservadas que permiten la
predicción. Por ejemplo, la intersección de intrones y exones siguen la
regla GT-AG en que un intrón en la intersección de splicing 5’ tiene un
motivo de consenso GTAAGT y en la intersección de splicing 3’ un
motivo de consenso (Py )12 NCAG.
Otra caractersística son las islas CpG, que son regiones cerca del inicio
del gen con alta densidad de dinucleótidos CG.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
26 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Figura : Transcripción de un gen eucariota y splicing.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
27 / 52
Predicción de genes
1
Predicción de genes en eucariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
28 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Este tipo de programas predicen exones, basados en las señales y el
contenido del gen.
Las señales incluyen la de inicio, de parada, presuntas posiciones de
splice o consensos reconocibles.
El contenido se refiere a las estadísticas de las regiones codificantes, lo
cual incluye distribución de nucleótidos no aleatoria, frecuencias de
hexámeros, etc. La frecuencia de hexámeros parece ser muy buena
para discriminar las regiones codificantes.
Tres técnicas son prominentes para la predicción: redes neuronales,
modelos ocultos de markov y análisis de discriminantes.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
29 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
En los métodos basados en redes neuronales, una red neuronal es
entrenada con cadenas de genes conocidos, donde la información del
gen está apropiadamente separada en varias características.
La red recibe como entrada una secuencia con intrones y exones, y
devuelve como salida la probabilidad de la estructura del exón.
GRAIL es un programa en la red que usa redes neruonales y está
especializado en los organismos humano, de ratón, Arabidopsis,
Drosophila y E. coli.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
30 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Figura : Estructura básica de una red neuronal para predicción de genes
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
31 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Las técnicas que usan análisis de discriminantes funcionan graficando
en dos dimensiones las señales codificantes contra todas las posiciones
potenciales de slice 3’.
El análisis lineal divide las señales codificantes de las no codificantes
mediante una linea.
El análisis cuadrático divide las señales codificantes de las no
codificantes mediante una curva.
Programas que implementan este análisis son FGENES y MZEF.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
32 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Figura : LDA vs QDA, los triángulos son características codificantes, los taches
son regiones no codificantes.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
33 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Varios programas están disponibles en la red que usan HMM.
GENSCAN es uno de ellos y usa un modelo de markov de quinto orden.
HMMgene es otro de ellos que utiliza una característica única llamada
probabilidad condicional máxima para discriminar. Esta propiedad dice
que si una secuencia tiene una región que ya ha sido identificada como
codificante, se queda fija y la predicción subsecuente se hace con un
sesgo hacia la región fija.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
34 / 52
Predicción de genes
1
Predicción de genes en eucariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
35 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Los programas basados en homología toman ventaja del hecho de que
las estructuras de los exones y las secuencias de exones entre especies
están altamente conservadas. Los marcos codificantes pueden
traducirse y alinearse contra las proteínas homólogas más cercanas
para encontrar regiones emparejadas casi perfectamente.
El inconveniente de esta técnica es la confianza que se tiene en las
secuencias de la base de datos y más aún, la presencia de estas. En
caso de no existir, no se puede emplear esta técnica.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
36 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Algunos programas en la red basados en homología:
GenomeScan - Combina los resultados de GENSCAN con las búsquedas
de similitud de BLASTX.
EST2Genome - Basado enteramente en el enfoque de alineamiento de
secuencias (con programación dinámica) para establecer los límites de
intrones y exones. Es especialmente bueno para encontrar exones
pequeños y exones en splicings alternativos.
SGP-1 - Alinea dos secuencias de ADN de organismos relacionados.
Traduce los exones potenciales a proteínas y hace un alineamiento por
pares.
TwinScan Muy parecido a GenomeScan.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
37 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
En lugar de usar las propiedades estadísticas de los exones, el
problema se puede ver de la siguiente manera: Dada una proteína
objetivo y una secuencia genómica, se necesita encontrar las
subcadenas (substring) en la secuencia genómica cuya concatenación
se ajusta mejor al objetivo.
El enfoque por fuerza bruta busca todas las similitudes locales entre
las secuencias y entrega un exón candidato. El mejor subconjunto de
subcadenas que no se traslapan corresponde al mejor candidato a ser
un exón.
En el enfoque de programación dinámica, cada exón se modela con un
intervalo ponderado en la secuencia genómica, descrito por tres
parámetros (l,r,w). w refleja la probabilidad de el intevalo sea un exón,
l y r son las posiciones de inicio y de fin del exón.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
38 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Definamos una cadena como un conjunto de intervalos ponderados
que no se traslapan. El peso total de una cadena es la suma de pesos
de los intervalos.
Un posible algoritmo puede recibir un conjunto de n intervalos
ponderados, creando un grafo G de 2n vertices, donde n de ellos
representan las posiciones de inicio y las n restantes las posiciones de
fin.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
39 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Existirán 3n-1 aristas, n de ellas conectan a li y ri con peso wi . Las
2n-1 restantes tienen peso 0 y conectan vértices adyacentes, en el
siguiente algoritmo si representa el camino más largo hasta el vértice
vi .
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
40 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
EXONCHAINING(G , n)
1
2
3
4
for i ← 1 to2n
si ← 0
for i ← 1 to 2n
if vértice vi en G corresponde al extremo derecho del intervalo I .
5
j ← índice del vértice del extremo izquierdo del intervalo I
6
w ← peso del intervalo I
7
si ← max(sj + w , si−1 )
8
9
10
else
si ← si−1
return s2 n
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
41 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Un defecto de éste enfoque es que los puntos finales de los exones
candidatos no están muy bien definidos. Más importante, la primer
cadena de intervalos óptima puede ser similar a un sufijo de una
proteína mientras que el segundo intervalo puede ser similar a un
prefijo. En este caso los exones supuestos no se pueden combinar en
un alineamiento válido. (Splicing tradicional).
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
42 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
En 1966, Mikhail Gelfand et al propusieron el algoritmo spliced
alignment (programación dinámica). El primer paso del algoritmo es
seleccionar los posibles exones de ciertos sitios (dinucleótidos AG y
GT) o de hallar todas las subcadenas similares a una proteína objetivo.
Dado un conjunto de exones candidatos y una proteína objetivo, se
exploran todas las posibles cadenas del exón candidato que se parezca
más a la proteína.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
43 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Sea G = g1 ...gn la secuencia genómica, T = t1 ...tm la secuencia
objetivo (proteína) y B el conjunto de exones candidatos.
El objetivo es encontrar una cadena de exones candidatos en la
secuencia genómica que mejor se ajusta a la secuencia objetivo. El
problema del spliced alignment se puede ver como encontrar un
camino en un grafo acćlico dirigido. Los vértices del grafo
corresponden a exones y las aristas sólo conectan vértices que no se
traslapan. Los vértices están etiquetados con la cadena del posible
exón, por tanto, un camino en el grafo deletrea la cadena final. El
peso de un camino en el grafo está definido por el alineamiento entre
la secuencia objetivo y la cadena del camino.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
44 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Figura : Un ejemplo de grafo de spliced alignment. El grafo es acíclico, las aristas
solo conectan vértices que no se traslapan.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
45 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
La recurrencia que usa el algoritmo define el puntaje de similitud entre
el prefijo i del grafo y el prefijo j de la secuencia objetivo. La dificultad
yace en que típicamente hay muchos prefijos que contienen la posición
i (muchos prefijos i).
Sea B = gleft ...gi ...gright un exón candidato que contenga la posición i
en la secuencia genómica G. Definase el prefijo-i de B como
B(i) = gleft ...gi y end(B) = right (right se usa como índice)
Si la cadena Γ = (B1 , B2 , ..., B) termina en el bloque B, se define
Γ ∗ (i) como la concatenación de todos los exones candidatos en la
cadena hasta B, más todos los caracteres en B hasta i.
Γ ∗ (i) = B1 ◦ B2 ... ◦ B(i)
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
46 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Finalmente, sea S(i, j, B) = maxs(Γ ∗ (i), T (j)) de todas las cadenas
Γ que terminan en B
Esto es, dados i, j y un exón candidato B que cubre la posicione
i, S(i, j, B) es el puntaje del spliced alignment óptimo entre el prefijo i
de G y el prefijo j de T . En la siguiente recurrencia se usa σ y δ como
penalización por huecos y matriz de puntaje respectivamente.

 S(i − 1, j, B) − σ
S(i, j − 1, B) − σ
S(i, j, B) = max

S(i − 1, j − 1, B) + δ(gi , tj )
Si i no es la posición inicial.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
47 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Si i es la posición inicial.

 S(i, j − 1, B) − σ
max(S(end(B 0 ), j − 1, B 0 ) + δ(gi , tj )
S(i, j, B) = max

max(S(end(B 0 ), j, B 0 ) + σ
Siendo B’ todos los bloques que preceden a B
Esta matriz tridimensional tendrá el puntaje óptimo del spliced
alignment en maxB S(end(B), m, B)
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
48 / 52
Predicción de genes
1
Predicción de genes en eucariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
49 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
Estos programas trabajan reteniendo las predicciones en común de los
algoritmos de homología y ab initio. Eliminan las predicciones
inconsistentes, con lo cual mejora la especificidad al costo de más baja
sensibilidad.
GeneComber - Es un programa web que combina HMMGene y
GenScan.
DIGIT - Use las predicciones de tres programas ab initio FGENESH,
GENSCAN y HMMgene.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
50 / 52
Predicción de genes
1
Predicción de genes en eucariotas
Predicción de genes
Introducción
Categorías de los programas de predicción de genes
Predicción de genes en procariotas
Determinación convencional de marcos abiertos de lectura
Predicción de genes usando Modelos de Markov y Modelos Ocultos de Markov
Evaluación del desempeño
Predicción de genes en eucariotas
Programas
Programas
Programas
Evaluación
de predicción de genes ab initio
basados en homología
basados en consenso
del desempeño
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
51 / 52
Predicción de genes
Predicción de genes en eucariotas
Predicción de genes en eucariotas
La complejidad adicional de los organismos eucariotas tiene como
consecuencia que sea necesario redefinir la sensibilidad y la
especificidad al nivel de exones y genes.
La sensibilidad al nivel de los exones y de los genes es la proporción de
exones o genes correctamente predichos de entre los exones o genes
que sí están presentes. Al mismo nivel, la especificidad es la proporción
de exones o genes predichos de todas las predicciones. En lugar de
usar el CC se calcula un promedio de sensibilidad y especificidad.
Jesús Alejandro Hernández Mejía (Cinvestav)
Predicción de Genes
2 de Julio de 2013
52 / 52