Download MOM para la prediccion de genes

'
$
Modelos de Markov ocultos
Predicción de genes
Alex Sánchez i Mireia Vilardell
Departament d’Estadı́stica U.B.
Estadı́stica i Bioinformàtica
&
MMO en Biologia Computacional
'
%
Alex Sánchez
$
Esquema del tema
Introducción: Genes y predicción de genes
Predicción con modelos tradicionales: Glimmer, geneid
Predicción con HMM (1): Conceptos básicos
Extensiones del modelo: SemiHMM y Genscan
Comparación de programas de predicción
&
Departament d’Estadı́stica U.B.
%
1
MMO en Biologia Computacional
'
1.
Alex Sánchez
$
Introducción
1.1.
El problema de la identificación de genes
El problema de la identificación de los genes se puede describir
como el problema de deducir la secuencia de aminoácidos
codificada por una determinada región de ADN
Es un problema difı́cil pero muy relevante puesto que ...
• Es necesario para anotar los datos procedentes de los
proyectos de secuenciación
• Ayuda a entender los mecanismos implicados en la
codificación–decodificación de la información biológica
El problema es más simple en organismos inferiores
(procariotas) que en los superiores (eucariotas) cuya estructura
genómica es más compleja
&
Departament d’Estadı́stica U.B.
2
MMO en Biologia Computacional
'
%
Alex Sánchez
$
Figura 1: Modelos de transcripción y traslación en procariotas y
eucariotas
&
Departament d’Estadı́stica U.B.
%
3
MMO en Biologia Computacional
'
1.2.
Alex Sánchez
$
Estructura de los genes en procariotas
El genoma de los procariotas (“sin nucleo celular”) suele ser
rico en genes: El 80 %–90 % de la secuencia es codificante
De forma simplificada un gen procariota es una secuencia de
codones que
• Empieza con un codon de inicio, (ATG),
• Continua con un número múltiplo de tres de nucleótidos
• Acaba con un codon de stop (TAA / TAG / TGA)
&
%
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
4
Alex Sánchez
$
Figura 2: Un gen procariota
&
Departament d’Estadı́stica U.B.
%
5
MMO en Biologia Computacional
'
1.3.
Alex Sánchez
$
Estructura de los genes en eucariotas
En los organismos superiores los genes no son ni contı́nuos ni
contiguos
Los genes suelen estar fragmentados en cierto número de
fragmentos codificantes conocidos como exones separados por
grandes fragmentos no codificantes conocidos como intrones.
Existen una diversidad de señales, algunas más claras que
otras, que es preciso localizar e identificar para la predicción de
los genes
&
%
6
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 3: Estructura de un gen eucariota
&
Departament d’Estadı́stica U.B.
%
7
MMO en Biologia Computacional
'
1.4.
Alex Sánchez
$
Las señales de especificación de los genes
Durante el camino del ADN a la secuencia de aminoácidos los
genes son ensamblados por un proceso en tres etapas conocido
como splicing
Durante este proceso se eliminan los intrones antes de traducir
el ADN a proteı́nas
Distintas señales que indican como debe actuar la maquinaria
celular que regula el proceso se hallan codificadas en la
secuencia original del ADN
1.
En la transcripcion intervienen elementos promotores y
señales de fin de transcripción
2.
En el splicing participan los sitios dadores y aceptores
3.
En la traducción intervienen los codones de iniciación o de
parada
&
%
8
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 4: De la secuencia de ADN a la de Aminoácidos
&
Departament d’Estadı́stica U.B.
%
9
MMO en Biologia Computacional
'
2.
Alex Sánchez
$
Predicción de genes (1)
2.1.
Predicción en procariotas
El problema principal suele ser identificar cual de dos o más
pautas abiertas de lectura contiene un gen (se supone que sólo
una)
Una pauta abierta de lectura es una secuencia de codones que
empieza con un codon de inicio (ATG) y acaba en un codon de
stop (TAA / TAG / TGA) sin que haya ningún otro codon de
stop entre ellos
Existen señales de inicio y final que es preciso identificar y
distinguir del “ruido de fondo”
&
%
10
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
2.2.
Alex Sánchez
$
Predicción con modelos de markov
El programa GeneMark, (Borodovsky et al., 1993) utiliza
cadenas de Markov de orden 5 para identificar genes
microbianos.
Esto representa analizar 2 codones cada vez
Los genomas bacterianos suelen ser lo bastante largos como
para proporcionar buenos estimadores de 46 = 4096
probabilidades de transición necesarias
Un modelo de orden ocho seria preferible, pero el número de
probabilidades a estimar es excesivo
&
Departament d’Estadı́stica U.B.
%
11
MMO en Biologia Computacional
'
Alex Sánchez
$
ALgoritmo simplificado de GenMark
De forma simplificada el algoritmo que utiliza GeneMark es el
siguiente:
1.
Entrenar un modelo de orden 5 con genes conocidos
(=pautas de lectura largas, “hits” en bases de datos)
2.
Entrenar un modelo de orden 0 como modelo nulo
3.
Puntuar cada pauta abierta de lectura siguiendo las 6
posibles pautas de lectura (3 forward, 3 backward )
4.
Si la pauta de lectura con mayor puntuación es la pauta
abierta, llamésele “un gen”
5.
Si hay pautas abiertas superpuestas puntúese las regiones
superpuestas separadamente.
&
%
12
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
2.3.
Alex Sánchez
$
Predicción en eucariotas (1)
Identificacion de genes mediante señales
Un método habitual de predicción consiste en:
• Construir un conjunto de exones potenciales, identificados a
traves de señales de inicio/aceptores y de donores/stop
• Puntuarlos mediante un modelo estadı́stico apropiado
• Ensamblar los genes mediante programación dinámica
Se elegirán como candidatos aquellos genes cuya puntuación
total sea más elevada
&
Departament d’Estadı́stica U.B.
%
13
MMO en Biologia Computacional
'
2.4.
Alex Sánchez
$
Modelos estadı́sticos de puntuación
En análisis de secuencias biológicas son comunes los sistemas
de puntuación en donde se compara la puntuación que se
asigna a una secuencia bajo un modelo concreto con la que le
asigna un modelo nulo o “background”.
Por motivos computacionales dichas puntuaciones suelen
expresarse como logaritmos de razones de verosimilitudes
(“log-likelihood ratios scores”, “LLR scores” o “LODs”)
Aparecen sistemas de puntuación basados en LLRs en:
• Matrices PAM o BLOSUM
• Identificación de islas CpG
• Identificación de motivos mediante matrices de pesos
posicionales (PWM)
&
%
14
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
Alex Sánchez
$
El sistema de puntuación de geneid
2.5.
El programa de predicción de genes geneid utiliza LLRs en la
puntuación de los exones potenciales
Un gen, concebido como una sucesión de exones e intrones
alternados, puede representarse de forma simplificada como:
S = e1 i1 e2 i2 e3 i3 e4 i4 ....eN
Sea ei = si1 si2 si3 ...sini un exon potencial que consta de tres
partes diferenciadas:
−−−
eia :Inicio/Aceptor
− − − − − − − − − − − − −−
eiM :P arte codif icante
−−−
eid :Stop/Donor
geneid puntua cada parte separadamente utilizando un modelo
para los extremos y otro para la parte codificante.
&
Departament d’Estadı́stica U.B.
%
15
MMO en Biologia Computacional
'
Alex Sánchez
$
Modelo de puntuación de un exon
Sea eia el punto de inicio o un “acceptor site” y eid el punto de
stop o un “donor site”. El exon potencial se puntua:
LE (ei ) = LA (eia ) + LD (eid ) + LM (ei )


nA
nD
n
i −5
Asij j +
Dsij j + LI l ei1..,5 +
LF l eij...j+5  ,
=
j=1
j=1
j=1
LA (eia ) y LD (eid ) son las puntuaciones de los extremos del
exon, que se obtienen mediante LLRs basados en matrices de
pesos posicionales para los sitios dadores o aceptores
LM (ei ) es el potencial de codificación, que se calcula mediante
un modelo de Markov de orden 5
&
%
16
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
2.6.
Alex Sánchez
$
Modelo de puntuación (1) Sitios aceptores y
donores
El calculo LA (eia ) y LD (eid ) esta basado en matrices de pesos
posicionales
Asij j , Dsij j son elementos de esta PWM, determinadas a partir
de secuencias en las que se conocen las posiciones de los genes
(y por tanto de los aceptores, donores, y sitios de start y stop).
Se definen como:
Aij = log
PijA
, (respectivament, Dij , Bij )
QA
ij
&
Departament d’Estadı́stica U.B.
%
17
MMO en Biologia Computacional
'
Alex Sánchez
$
Matrices de pesos posicionales
PijA (respectivamente, PijD , PijB ) representan la probabilidad
de observar el nucleótido i (i ∈ A, C, T, G) en la posición j
(j ∈ −3, −2, ..., 5) en un acceptor site (respectivament, donor o
start), y por tanto se estima a partir de la frecuencia relativa
de nucleótids i que ocupen la posición j en los acceptor sites
“reales”, es decir conocidos (respectivament, donor o start).
D
S
QA
ij (respectivamente, Qij , Qij ) representan la probabilidad
de observar el nucleótido i (i ∈ A, C, T, G) en la posición j
(j ∈ −3, −2, ..., 5) entorno de cualquier dinucleótido AG
(respectivament GT para los donors o AT G para los start
codons). Representa pues el modelo nulo, o más exactamente
“background”.
&
%
18
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 5: Matrices de pesos posicionales
&
Departament d’Estadı́stica U.B.
%
19
MMO en Biologia Computacional
'
Alex Sánchez
$
Modelo de puntuación (2) Potencial de codificación
El potencial de codificación consta de dos componentes:
F j (h) = F j (s1 s2 s3 s4 s5 s6 ) es la probabilidad (de transición) de
observar dentro de un exon el hexámero h = s1 s2 s3 s4 s5 s6
con el nucleótido s1 en la posición j (j = 1, 2, 3 correspondiente
a las tres posibles pautas de lectura) suponiendo que s1 se
encuentre en la posición j en el pentámero s1 s2 s3 s4 s5 .
I j (p) es la probabilidad inicial para cada pentámero p en cada
posición dentro de los exones para las pautas de lectura 1,2,3.
F 0 (h) i I 0 (p) son las probabilidades de transición iniciales
correspondientes a los intrones
&
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
%
20
Alex Sánchez
$
Ensamblado de los genes
El modelo anterior permite puntuar cada uno de los posibles
exones de un gen
Como las señales son muy débiles el número de exones
potenciales es muy alto, la mayoria de ellos superpuestos entre
si
Para escoger un conjunto “óptimo” que configura un gen se
utiliza un algoritmo de programación dinámica que realiza el
ensamblado maximizando la suma de las puntuaciones de
conjuntos de exones compatibles con un gen (i.e. sin
superposición, sin stop codons en medio etc...)
&
Departament d’Estadı́stica U.B.
%
21
MMO en Biologia Computacional
'
Alex Sánchez
$
&
%
22
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
Alex Sánchez
$
&Figura 6: El número de exones potenciales es muy alto
Departament d’Estadı́stica U.B.
%
23
MMO en Biologia Computacional
'
3.
Alex Sánchez
$
Predicción de genes con MOM
Los MOM resultan especialmente adecuados para la predicción
de genes por su capacidad para modelizar estructuras
gramaticales, es decir, estructuras en las que aparecen
restricciones relativas
• al tipo de elementos que las constituyen
• al orden en que aparecen estos elementos
Los genes tienen una estructura gramatical sencilla: No se trata
tan sólo de conjuntos de caracteres (nucleótidos), palabras
(exones /intrones) o frases (genes): Hay una estructura en el
sentido que ciertas expresiones no tienen sentido, no son
posibles. Por ejemplo, en genes eucariotas
1.
Las frases nunca acaban en un intron
2. Un exon nunca sigue a otro exon
&
%
24
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
3.1.
Alex Sánchez
$
MOM para predicción de genes procariotas
Los genes procariotas tienen una gramática particularmente
sencilla
• Codon de inicio
• Region codificante
• Codon de parada
Un MOM para predecir genes de tal tipo deberá contemplar
estados para los tres tipos de regiones
&
Departament d’Estadı́stica U.B.
%
25
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 7: Un MMO para genes procariotas
&
%
26
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
3.2.
Alex Sánchez
$
MOM para predicción de genes eucariotas
La estructura de los genes eucariotas es compleja. De forma
simplificada contempla
• Codon de inicio
• Region codificante: Un cierto número de exones (≥ 1) e
intrones (≥ 0) terminados por un exón
• Codon de parada
Los MOM desarrollados para genes eucariotas suelen constar
de varios modelos encadenados, unos para modelizar las señales
de inicio o finalización y otros para la región codificante.
&
Departament d’Estadı́stica U.B.
%
27
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 8: Para los sitios aceptores se construye un MMO sencillo.
Excepto en casos raros el intron acaba con un AG, sombreado. El
modelo contemplará no tan sólo estos dos nucleótidos con probabilidades de emisión 1, sino 16 bases anteriores y tres bases siguientes.
Puesto que no hay huecos el modelo será equivalente a una matriz
de pesos.
&
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
%
28
Alex Sánchez
$
&
Departament d’Estadı́stica U.B.
%
29
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 9: Para las regiones codificantes se construye otro MMO. Los
estados uno, dos y tres del modelo representan respectivamente el
primer, segundo y tercer codon Cualquier región codificante puede
ser representada por este modelo porque del estado tres se puede
volver al uno En la parte inferior se muestra un modelo sencillo en
el que los tres primeros estados coinciden con un codon de inicio,
los tres siguientes con el modelo de región codificante de la parte
superior y los tres últimos con un codon de parada (solo se muestra
uno de los tres posibles estados de parada)
&
Departament d’Estadı́stica U.B.
30
MMO en Biologia Computacional
'
%
Alex Sánchez
$
Figura 10: Los modelos se encadenan en un modelo general. Una “x”
indica un estado para DNA no codificante y una “c” un estado para
DNA codificante (solo se muestra uno de los tres posibles estados de
parada)
&
Departament d’Estadı́stica U.B.
%
31
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 11: Un modelo combinado que contempla el splicing
&
%
32
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
3.3.
Alex Sánchez
$
Identificación de genes con MMO
Los MMO como los anteriores implican una estructura
determinada para el gen
Una secuencia que no cumpla las restricciones impuestas
recibirá probabilidad cero bajo este modelo
Si se desea localizar los genes en un fragmento de genoma
• Aplicar el algoritmo de Viterbi a la secuencia
• Identificar como genes aquellas sucesiones de observaciones
del camino más probable que cumplan las reglas
gramaticales impuestas por el modelo:
ATG→ Ex → Int → Ex → Int ...→ TAA → Fin
&
Departament d’Estadı́stica U.B.
%
33
MMO en Biologia Computacional
'
Alex Sánchez
$
Figura 12: Predicción de genes: Dada una secuencia observada la
predicción del gen se obtiene aplicaandole el Algoritmo de Viterbi
&
%
34
Departament d’Estadı́stica U.B.
MMO en Biologia Computacional
'
Alex Sánchez
$
En la practica
Los MMO que se utilizan en los programas “reales” de
predicción de genes son mucho más complejos que el ejemplo
anterior.
1.
VEIL utiliza un modelo simple con muchos estados
2.
HMMGene Utiliza CHMM: MMO con clases
3.
Genie usa GHMM: MMO generalizados: Los estados del
modelo general son, a su vez MMO completos
4.
GENSCAN (Burge & Karlin) usa SHMM: MMO con
capacidad de incluir la longitud de los exones e intrones...
&
Departament d’Estadı́stica U.B.
%
35