universitat de barcelona - home - esquema del tema...rico en genes: el 80%–90% de la secuencia es...

�

�

�

�

Modelos de Markov ocultosPrediccion de genes

Alex Sanchez i Mireia Vilardell

Departament d’Estadıstica U.B.

Estadıstica i Bioinformatica

MMO en Biologia Computacional Alex Sanchez�

�

�

�

Esquema del tema

Introduccion: Genes y prediccion de genes

Prediccion con modelos tradicionales: Glimmer, geneid

Prediccion con HMM (1): Conceptos basicos

Extensiones del modelo: SemiHMM y Genscan

Comparacion de programas de prediccion

Departament d’Estadıstica U.B. 1


�

�

�

1. Introduccion

1.1. El problema de la identificacion de genes

El problema de la identificacion de los genes se puede describircomo el problema de deducir la secuencia de aminoacidoscodificada por una determinada region de ADN

Es un problema difıcil pero muy relevante puesto que ...

• Es necesario para anotar los datos procedentes de losproyectos de secuenciacion

• Ayuda a entender los mecanismos implicados en lacodificacion–decodificacion de la informacion biologica

El problema es mas simple en organismos inferiores(procariotas) que en los superiores (eucariotas) cuya estructuragenomica es mas compleja



�

�

�Figura 1: Modelos de transcripcion y traslacion en procariotas yeucariotas



�

�

�

1.2. Estructura de los genes en procariotas

El genoma de los procariotas (“sin nucleo celular”) suele serrico en genes: El 80 %–90 % de la secuencia es codificante

De forma simplificada un gen procariota es una secuencia decodones que

• Empieza con un codon de inicio, (ATG),

• Continua con un numero multiplo de tres de nucleotidos

• Acaba con un codon de stop (TAA / TAG / TGA)



�

�

�Figura 2: Un gen procariota



�

�

�

1.3. Estructura de los genes en eucariotas

En los organismos superiores los genes no son ni contınuos nicontiguos

Los genes suelen estar fragmentados en cierto numero defragmentos codificantes conocidos como exones separados porgrandes fragmentos no codificantes conocidos como intrones.

Existen una diversidad de senales, algunas mas claras queotras, que es preciso localizar e identificar para la prediccion delos genes



�

�

�

Figura 3: Estructura de un gen eucariota



�

�

�

1.4. Las senales de especificacion de los genes

Durante el camino del ADN a la secuencia de aminoacidos losgenes son ensamblados por un proceso en tres etapas conocidocomo splicing

Durante este proceso se eliminan los intrones antes de traducirel ADN a proteınas

Distintas senales que indican como debe actuar la maquinariacelular que regula el proceso se hallan codificadas en lasecuencia original del ADN

1. En la transcripcion intervienen elementos promotores ysenales de fin de transcripcion

2. En el splicing participan los sitios dadores y aceptores

3. En la traduccion intervienen los codones de iniciacion o deparada



�

�

�

Figura 4: De la secuencia de ADN a la de Aminoacidos



�

�

�

2. Prediccion de genes (1)

2.1. Prediccion en procariotas

El problema principal suele ser identificar cual de dos o maspautas abiertas de lectura contiene un gen (se supone que solouna)

Una pauta abierta de lectura es una secuencia de codones queempieza con un codon de inicio (ATG) y acaba en un codon destop (TAA / TAG / TGA) sin que haya ningun otro codon destop entre ellos

Existen senales de inicio y final que es preciso identificar ydistinguir del “ruido de fondo”



�

�

�

2.2. Prediccion con modelos de markov

El programa GeneMark, (Borodovsky et al., 1993) utilizacadenas de Markov de orden 5 para identificar genesmicrobianos.

Esto representa analizar 2 codones cada vez

Los genomas bacterianos suelen ser lo bastante largos comopara proporcionar buenos estimadores de 46 = 4096probabilidades de transicion necesarias

Un modelo de orden ocho seria preferible, pero el numero deprobabilidades a estimar es excesivo



�

�

�

ALgoritmo simplificado de GenMark

De forma simplificada el algoritmo que utiliza GeneMark es elsiguiente:

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 6posibles pautas de lectura (3 forward, 3 backward)

4. Si la pauta de lectura con mayor puntuacion es la pautaabierta, llamesele “un gen”

5. Si hay pautas abiertas superpuestas puntuese las regionessuperpuestas separadamente.



�

�

�

2.3. Prediccion en eucariotas (1)

Identificacion de genes mediante senales

Un metodo habitual de prediccion consiste en:

• Construir un conjunto de exones potenciales, identificados atraves de senales de inicio/aceptores y de donores/stop

• Puntuarlos mediante un modelo estadıstico apropiado

• Ensamblar los genes mediante programacion dinamica

Se elegiran como candidatos aquellos genes cuya puntuaciontotal sea mas elevada



�

�

�

2.4. Modelos estadısticos de puntuacion

En analisis de secuencias biologicas son comunes los sistemasde puntuacion en donde se compara la puntuacion que seasigna a una secuencia bajo un modelo concreto con la que leasigna un modelo nulo o “background”.

Por motivos computacionales dichas puntuaciones suelenexpresarse como logaritmos de razones de verosimilitudes(“log-likelihood ratios scores”, “LLR scores” o “LODs”)

Aparecen sistemas de puntuacion basados en LLRs en:

• Matrices PAM o BLOSUM

• Identificacion de islas CpG

• Identificacion de motivos mediante matrices de pesosposicionales (PWM)



�

�

�

2.5. El sistema de puntuacion de geneid

El programa de prediccion de genes geneid utiliza LLRs en lapuntuacion de los exones potenciales

Un gen, concebido como una sucesion de exones e intronesalternados, puede representarse de forma simplificada como:

S = e1i1e2i2e3i3e4i4....eN

Sea ei = si1s

i2s

i3...s

ini

un exon potencial que consta de trespartes diferenciadas:

−−−︸︷︷︸eia:Inicio/Aceptor

−−−−−−−−−−−−−−︸︷︷︸eiM :Parte codificante

−−−︸︷︷︸eid:Stop/Donor

geneid puntua cada parte separadamente utilizando un modelopara los extremos y otro para la parte codificante.



�

�

�

Modelo de puntuacion de un exon

Sea eia el punto de inicio o un “acceptor site” y eid el punto destop o un “donor site”. El exon potencial se puntua:

LE(ei) = LA(eia) + LD(eid) + LM (ei)

=nA∑j=1

Asijj +

nD∑j=1

Dsijj +

LI l

(ei1..,5

)+

ni−5∑j=1

LF l(eij...j+5

) ,

LA(eia) y LD(eid) son las puntuaciones de los extremos delexon, que se obtienen mediante LLRs basados en matrices depesos posicionales para los sitios dadores o aceptores

LM (ei) es el potencial de codificacion, que se calcula medianteun modelo de Markov de orden 5



�

�

�

2.6. Modelo de puntuacion (1) Sitios aceptores y

donores

El calculo LA(eia) y LD(eid) esta basado en matrices de pesosposicionales

Asijj , Dsi

jj son elementos de esta PWM, determinadas a partirde 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 = logPA

ij

QAij

, (respectivament, Dij , Bij)



�

�

�

Matrices de pesos posicionales

PAij (respectivamente, PD

ij , PBij ) representan la probabilidad

de observar el nucleotido i (i ∈ A,C, T,G) en la posicion j

(j ∈ −3,−2, ..., 5) en un acceptor site (respectivament, donor ostart), y por tanto se estima a partir de la frecuencia relativade nucleotids i que ocupen la posicion j en los acceptor sites“reales”, es decir conocidos (respectivament, donor o start).

QAij (respectivamente, QD

ij , QSij ) representan la probabilidad

de observar el nucleotido i (i ∈ A,C, T,G) en la posicion j

(j ∈ −3,−2, ..., 5) entorno de cualquier dinucleotido AG

(respectivament GT para los donors o ATG para los startcodons). Representa pues el modelo nulo, o mas exactamente“background”.



�

�

�Figura 5: Matrices de pesos posicionales



�

�

�

Modelo de puntuacion (2) Potencial de codificacion

El potencial de codificacion consta de dos componentes:

F j(h) = F j(s1s2s3s4s5s6) es la probabilidad (de transicion) deobservar dentro de un exon el hexamero h = s1s2s3s4s5s6

con el nucleotido s1 en la posicion j (j = 1, 2, 3 correspondientea las tres posibles pautas de lectura) suponiendo que s1 seencuentre en la posicion j en el pentamero s1s2s3s4s5.

Ij(p) es la probabilidad inicial para cada pentamero p en cadaposicion dentro de los exones para las pautas de lectura 1,2,3.

F 0(h) i I0(p) son las probabilidades de transicion inicialescorrespondientes a los intrones



�

�

�

Ensamblado de los genes

El modelo anterior permite puntuar cada uno de los posiblesexones de un gen

Como las senales son muy debiles el numero de exonespotenciales es muy alto, la mayoria de ellos superpuestos entresi

Para escoger un conjunto “optimo” que configura un gen seutiliza un algoritmo de programacion dinamica que realiza elensamblado maximizando la suma de las puntuaciones deconjuntos de exones compatibles con un gen (i.e. sinsuperposicion, sin stop codons en medio etc...)



�

�

�Departament d’Estadıstica U.B. 22


�

�

�Figura 6: El numero de exones potenciales es muy alto



�

�

�

3. Prediccion de genes con MOM

Los MOM resultan especialmente adecuados para la prediccionde genes por su capacidad para modelizar estructurasgramaticales, es decir, estructuras en las que aparecenrestricciones relativas

• al tipo de elementos que las constituyen

• al orden en que aparecen estos elementos

Los genes tienen una estructura gramatical sencilla: No se tratatan solo de conjuntos de caracteres (nucleotidos), palabras(exones /intrones) o frases (genes): Hay una estructura en elsentido que ciertas expresiones no tienen sentido, no sonposibles. Por ejemplo, en genes eucariotas

1. Las frases nunca acaban en un intron

2. Un exon nunca sigue a otro exon



�

�

�

3.1. MOM para prediccion de genes procariotas

Los genes procariotas tienen una gramatica particularmentesencilla

• Codon de inicio

• Region codificante

• Codon de parada

Un MOM para predecir genes de tal tipo debera contemplarestados para los tres tipos de regiones



�

�

�Figura 7: Un MMO para genes procariotas



�

�

�

3.2. MOM para prediccion de genes eucariotas

La estructura de los genes eucariotas es compleja. De formasimplificada contempla

• Codon de inicio

• Region codificante: Un cierto numero de exones (≥ 1) eintrones (≥ 0) terminados por un exon

• Codon de parada

Los MOM desarrollados para genes eucariotas suelen constarde varios modelos encadenados, unos para modelizar las senalesde inicio o finalizacion y otros para la region codificante.



�

�

�

Figura 8: Para los sitios aceptores se construye un MMO sencillo.Excepto en casos raros el intron acaba con un AG, sombreado. Elmodelo contemplara no tan solo estos dos nucleotidos con probabil-idades de emision 1, sino 16 bases anteriores y tres bases siguientes.Puesto que no hay huecos el modelo sera equivalente a una matrizde pesos.



�

�

�Departament d’Estadıstica U.B. 29


�

�

�

Figura 9: Para las regiones codificantes se construye otro MMO. Losestados uno, dos y tres del modelo representan respectivamente elprimer, segundo y tercer codon Cualquier region codificante puedeser representada por este modelo porque del estado tres se puedevolver al uno En la parte inferior se muestra un modelo sencillo enel que los tres primeros estados coinciden con un codon de inicio,los tres siguientes con el modelo de region codificante de la partesuperior y los tres ultimos con un codon de parada (solo se muestrauno de los tres posibles estados de parada)



�

�

�

Figura 10: Los modelos se encadenan en un modelo general. Una “x”indica un estado para DNA no codificante y una “c” un estado paraDNA codificante (solo se muestra uno de los tres posibles estados deparada)



�

�

�Figura 11: Un modelo combinado que contempla el splicing



�

�

�

3.3. Identificacion de genes con MMO

Los MMO como los anteriores implican una estructuradeterminada para el gen

Una secuencia que no cumpla las restricciones impuestasrecibira 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 observacionesdel camino mas probable que cumplan las reglasgramaticales impuestas por el modelo:

ATG→ Ex → Int → Ex → Int ...→ TAA → Fin



�

�

�

Figura 12: Prediccion de genes: Dada una secuencia observada laprediccion del gen se obtiene aplicaandole el Algoritmo de Viterbi



�

�

�

En la practica

Los MMO que se utilizan en los programas “reales” deprediccion de genes son mucho mas complejos que el ejemploanterior.

1. VEIL utiliza un modelo simple con muchos estados

2. HMMGene Utiliza CHMM: MMO con clases

3. Genie usa GHMM: MMO generalizados: Los estados delmodelo general son, a su vez MMO completos

4. GENSCAN (Burge & Karlin) usa SHMM: MMO concapacidad de incluir la longitud de los exones e intrones...


universitat de barcelona - home - esquema del tema...rico en genes: el 80%–90% de la secuencia es...

Documents