el algoritmo de programación dinámica. el sistema de puntuación la puntuación del alineamiento...
Post on 02-Apr-2015
111 Views
Preview:
TRANSCRIPT
El algoritmo de programación dinámica
El algoritmo de programación dinámica
El sistema de puntuación
La puntuación del alineamiento resulta de sumar las puntuaciones de cada posición, en función de que los
residuos coincidan, sean distintos o haya indels.
Para saber cuál es el mejor alineamiento entre dos secuencias es necesario establecer un sistema de
puntuación. Cada uno de los posibles alineamientos recibe una puntuación y se considera alineamiento
óptimo aquél que consigue la puntuación más elevada.
El sistema de puntuación consta de dos componentes: (1) una matriz de sustitución que asigna una puntuación
a cada una de las sustituciones posibles y (2) una penalización por la introducción de indels.
El algoritmo de programación dinámica
Matrices de sustitución
El algoritmo de programación dinámica
Margaret Dayhoff (1925 – 1983)
Matrices PAM (aminoácidos)
El algoritmo de programación dinámica
PAM 250
El algoritmo de programación dinámica
Ventajas e inconvenientes de PAM
El algoritmo de programación dinámica
Gonnet recalculó la matriz PAM en 1992
El algoritmo de programación dinámica
Gonnet PAM250
El algoritmo de programación dinámica
Steven y Jorja Henikoff
PROSITEDatabase of protein families and domains
(BLOcks SUbstitution Matrix)
El algoritmo de programación dinámica
BLOSUM 62
basic
small hydrophobic
aromatic
acid hydrophylic
small hydrophylic
ji
ijij pp
pS 2log2
El algoritmo de programación dinámica
Ventajas e inconvenientes de BLOSUM
El algoritmo de programación dinámica
Based on an explicit evolutionary model
Derived from small, closely related proteins with ~15% divergence
Higher PAM numbers to detect more remote sequence similarities
Errors in PAM 1 are scaled 250X in PAM 250
Based on empirical frequencies
Uses much larger, more diverse set of protein sequences (30-90% ID)
Lower BLOSUM numbers to detect more remote sequence similarities
Errors in BLOSUM arise from errors in alignment
PAM vs. BLOSUM (1)
El algoritmo de programación dinámica
• Built from global alignments
• Built from small amount of data
• Counting is based on minimum replacement or maximum parsimony
• Useful in finding global alignments and remote homologs
• Higher PAM series means more divergence
• Designed to track evolutionary origins of proteins
• Built from local alignments
• Built from vast amount of data
• Counting based on groups of related sequences counted as one
• Useful in finding local alignments
• Lower BLOSUM series means more divergence
• Designed to find conserved domains of proteins
PAM vs. BLOSUM (2)
El algoritmo de programación dinámica
¿PAM o BLOSUM?
El algoritmo de programación dinámica
Otras matrices
El algoritmo de programación dinámica
Matriz de identidad
El algoritmo de programación dinámica
Matriz de sustitución de codones
El algoritmo de programación dinámica
Cadenas laterales de los aminoácidos
El algoritmo de programación dinámica
Matriz de hidrofobicidad User matrix
Otros tipos de matrices
El algoritmo de programación dinámica
Matrices PAM (nucleótidos)
El algoritmo de programación dinámica
Modelo de Jukes-Cantor (uniforme)
A G T C
A 0.99
G 0.00333 0.99
T 0.00333 0.00333 0.99
C 0.00333 0.00333 0.00333 0.99
Mutation probability matrix (PAM-1)
El algoritmo de programación dinámica
Modelo de Kimura (sesgado)
A G T C
A 0.99
G 0.006 0.99
T 0.002 0.002 0.99
C 0.002 0.002 0.006 0.99
Mutation probability matrix (PAM-1)
Transition (A↔G) (C↔T)
Transversion (A↔T) (A↔C) (G↔T) (G↔C)
(purina↔purina) (pirimidina↔pirimidina)
(purina↔pirimidina) (pirimidina↔purina)
El algoritmo de programación dinámica
Gap penalties
El algoritmo de programación dinámica
A veces no me interesa que haya indels en el alineamiento (regiones muy
conservadas y con funciones muy delicadas que no tolerarían ningún
cambio). Puedo usar un programa que no admita indels o, alternativamente, colocar
una penalización infinita a los indels.
¿Indels? No, gracias
El algoritmo de programación dinámica
Suele ser un valor negativo muy elevado (G = -11; G = -). En la práctica, evita la introducción de indels en el alineamiento. La penalización se contabiliza sólo una vez (cuando se abre el indel) y es independiente de su tamaño.
Penalización constante
El algoritmo de programación dinámica
Se puede aplicar una penalización lineal. Cada posición ocupada por un indel sufre una penalización,
que es siempre la misma.
Penalización lineal
G = - n go
El algoritmo de programación dinámica
Desde un punto de vista evolutivo, es más realista suponer que la naturaleza ha insertado/eliminado fragmentos en la
secuencia de una sola vez. Por eso se introduce una penalización para la inclusión de un indel (gap open penalty)
y otra penalización (menos costosa) que dependa de la longitud del indel (gap extension penalty).
Penalización afín
La inserción/eliminación es mucho menos probable que cualquier sustitución de aa, por radical que ésta sea. Por tanto, la go debe estar muy penalizada para que se introduzcan indels
donde sea preciso, y no por toda la secuencia
Una vez que se ha introducido un indel en un punto de la secuencia, su extensión (ge) es mucho más probable y
debe estar mucho menos penalizada.
El algoritmo de programación dinámica
Dos modelos de penalización afín (1)
Modelo linealModelo convexo
El algoritmo de programación dinámica
En la penalización afín hay dos maneras distintas de penalizar la extensión del indel :
Modelo convexo: Para todo n>1, p(n+1) - p(n) < p(n) - p(n-1)
(Cada tramo adicional del indel penaliza menos que el anterior. Es el modelo que más se ajusta a la realidad, pero desde el punto de
vista computacional es muy difícil incluirlo en el algoritmo )
Modelo lineal: Para todo n >1, p(n+1) - p(n) = p(n) - p(n-1)
(La penalización es proporcional a la longitud del indel)
G = go + nge G = go + (n-1)ge
G = go + k log (n)
Dos modelos de penalización afín (2)
El algoritmo de programación dinámica
Algunas recomendaciones
Es importante seleccionar una penalización apropiada en función de la matriz de puntuación
elegida para que no se excluyan los indels, pero que tampoco se propaguen por todo el alineamiento.
No hay una mecanismo formal para calcular el valor de la penalización. La mayor parte de los programas hacen sus
propias recomendaciones, que están basadas en métodos de ensayo y error y no garantizan que para tu caso concreto sean
las más adecuadas. Deberás hacer varias pruebas.
Algunos valores típicos:
Matriz gap opening gap extension
BLOSUM 62 -12 - 3 / -12BLOSUM 50 -15 - 8 / -15PAM 250 -15 - 5 / - 15
top related