3_Alineamientos de Pares

Alineamiento de pares de secuenciasRodrigo Santamara

S

Alineamiento de pares de secuenciasIntroduccinDefiniciones Ejemplo

Algoritmos Matrices de puntuacin

S2

Objetivo

S Determinar si una secuencia de nucletidos o aminocidos

(un gen o una protena) est relacionada con otraS Esto nos permite determinarS Si evolucionaron desde un ancestro comn S Si tienen funciones comunes S En el caso de protenas, si tienen formas similares

3

Homologa

S Dos secuencias son homlogas si comparten un ancestro

comn

S No hay grados, o se es homlogo o no (soy un 30% tu padre) S Dos protenas homlogas suelen tener una estructura 3D

similarS Dos protenas o genes homlogos suelen tener secuencias

parecidas

4

Ortologa y Paraloga

S Ortlogo: secuencias homlogas en diferentes diferentes especies que

vienen de un ancestro comn

S P. ej.: el gen de la mioglobina en ratas y humanos tiene un ancestro comn

hace 80 millones de aos (MYA)

S Parlogo: secuencias homlogas pero debidas a un mecanismo

distinto a la evolucin

S Tpicamente, duplicacin gentica

S Simplificacin (no totalmente equivalente) S Ortlogo: homlogo entre diferentes especies S Parlogo: homlogo dentro de una misma especie

5

Similitud e Identidad

S Similitud: grado de coincidencia entre dos secuenciasS El grado de similitud entre dos secuencias es de un 45%

S Identidad: coincidencia total entre dos secuenciasS Aunque muchas veces se usa como sinnimo de similitud

S Analoga: grado muy alto de similitud entre dos secuencias S La homologa no siempre garantiza analogaS La -globina y la neuroglobina slo comparten un 22% de sus

secuencias a pesar de ser homlogas6

Alineamiento de pares

S Colocacin de dos secuencias para que se maximice su similitud ROJO ROSSO "+2" ROUGE "+2" RED "+1" ROJO ROSSO" ** * "+3 (75%)" ROJO ROUGE "" ** +2 (50%)"

ROJO RED" * "+1 (25%)"

S Las secuencias son largas y la capacidad de combinacin altaS Necesidad de mtodos algortmicos para realizar el alineamiento7

Huecos (gaps)

S Separaciones aadidas artificialmente a una secuencia para

maximizar su alineamiento con otra(s).S Representan posibles mutaciones sufridas durante la evolucin

que han causado divergencia entre las secuencias:S Inserciones S Deleciones

S Un hueco puede ocurrir en medio o en los extremos de la

secuencia8

Alineamiento global y local

S Alineamiento global: las secuencias se alinean a lo largo de

toda su longitud, intentando alinear secuencias completasS til para secuencias muy parecidas y de longitud similar

S Se introducen huecos para igualar las longitudes de secuencia

S Alineamiento local: slo se alinean la partes ms parecidas

de la secuencia

S Favorece encontrar patrones similares dentro de la secuencia S Un alineamiento local es una combinacin de muchos

alineamientos globales de secuencias cortas.9

Alineamiento de pares. EjemploS Un ejemplo biolgico: -globina (NCBI NP_00508) y -globina

(NP_000509) en humano

S Protenas homlogas con estructura 3D similar.

S Algoritmo BLAST de pares del NCBI para protenasS http://blast.ncbi.nlm.nih.gov/Blast.cgi 1. Enter query sequence: 1. introducir NP_000508 o su secuencia FASTA 2. Seleccionar align two or more sequences 2. Enter subject sequence: introducir NP_000509 o su FASTA 3. Click BLAST

10

Alineamiento de pares. Ejemplo

Query y Sbjct: secuencias. Ambas se alinean para maximizar su similitud Coincidencias: lnea entre Query y Sbjct Letra: coincidencia idntica +: coincidencia conservada (aminocidos bsicos, cidos, hidrfobos) Espacio en blanco: no hay coincidencia Score: valor del algoritmo de alineamiento Identities/Positives: porcentaje de coincidencias idnticas/conservadas Gaps: porcentaje de huecos incluidos en el alineamiento

Alineamiento de pares de secuenciasIntroduccin AlgoritmosDiagramas de puntos Alineamiento global Alineamiento local

Matrices de puntuacin

S13

Algoritmos de alineamiento

S Procedimientos de comparacin entre dos secuencias

mediante alineamientos ptimosS Una secuencia por s sola no es muy informativaS Necesitamos compararla con otras para descubrir relacionesS Funcionales: dos secuencias tienen la misma funcin o similar S Estructurales: dos secuencias de aminocidos (protenas) tienen la

misma estructura 3DS Evolutivas: dos secuencias proceden de un ancestro comn

14

Tipos de algoritmos de alineamientoS Diagramas de puntos S Algoritmos dinmicosS Alineamiento globalS Needleman and Wunsch (1970)

S Alineamiento localS Smith and Waterman (1981)

15

Diagramas de puntos (dot plots)S Es el algoritmo ms sencilloS No requiere computacin (data de 1970)S

Aunque se puede programar

S No requiere hiptesis biolgicas S Verificacin visual

S Se coloca una secuencia en el eje X y otra en el eje YS En cada lugar donde las secuencias coincidan se dibuja un punto S Las secuencias similares aparecern en forma de lneas diagonales

16

Dot plots: ejemploTCCGTCCATTGATTACAAAAGTCC

Cada vez que haya una coincidencia en un nucletido, colocamos un punto. Por ejemplo, en el caso del primer nucletido de la secuencia horizontal (T)

TCCGACTTGAGATTACAGAAGTCG


Continuamos con secuencias de 2, 3, 4, etc. Se suele establecer un umbral mnimo, o tamao de ventana (p. ej. 3)



Los puntos suelen sustituirse con lneas


Dot plots: Dotlet

S Applet Java para clculo y visualizacin de dot plotsS Applet: pequeo programa que se carga en un navegador y que

se ejecuta en la mquina cliente S Java: lenguaje de programacinS Fcil de usarS Regla general: buscar una seal clara S Veremos varios ejemplos S URL: http://myhits.isb-sib.ch/cgi-bin/dotlet20

Identificadores UniProt Protena de mosca y humano

Repeticiones de secuenciaScore: medida de similitud

Tamao de ventana

Umbrales x%-y%: sec. similares de score mayor que y% se muestran en blanco, menores que x% en negro, intermedias en grises

Frecuencias: nmero de secuencias idnticas con tamao n% respecto a la longitud total

Dot plot

log frecuencias: para distinguir mejor

21

Refinando el resultado podemos encontrar dominios similares entre ambas protenas

22

Globina del caracol Biomphalaria glabrata (cdigo NCBI de protenaCAJ44466)

Estructura interna de la protena: repeticiones de dominios

Hay un dominio que se repite 13 veces

23

Estructura interna de la protena: repeticiones de dominios

24

Cuatro bloques grandes ricos en leucina Seis bloques (ms uno) con dominios EGF

Repeticin de dos dominios en la protena SLIT de Drosophila melanogaster (P24014):

http://myhits.isb-sib.ch/util/dotlet/doc/repeats.html

Dotplot: consideraciones

S Comparando una secuencia consigo mismaS El dot plot es simtrico S El nmero de repeticiones de un patrn viene dado por el nmero

de diagonales por arriba o por abajo S La longitud del patrn repetido lo da la longitud de la lneaS Ahora veamos algunos ejemplos msS Regiones de baja complejidad S Exones e intrones S Conservacin entre especies

26

Dotlet

Conservacin entre especies: la globina de glabrata son 13 repeticiones de la citoglobina humana

Lieb et al. Red blood with blue-blood ancestry: Intriguing structure of a snail hemoglobin. PNAS, 2006

27

Las regiones de baja complejidad (periodicidad de uno o pocos aminocidos/nucletidos) aparecen como rectngulos, como por ejemplo en esta protena del P. Falciparum (UniProt P69192)

Identificacin de exones: comparamos la secuencia de un gen (horizontal) con su producto. Los exones sern las coincidencias entre ambos En este caso se ha seleccionado el gen de la calmodulina del E. Nidulans (Uniprot J05545) y su producto (P19533). Notad los cambios en los parmetros para optimizar la claridad de la representacin

29

Dotlet

S Permite detectar fcilmenteS Dominios internos en una secuencia S Dominios conservados entre dos secuencias S Zonas de baja complejidad S Exones e intrones S Etc.

S LimitacionesS Complejidad computacional O(n2) S Y si hay huecos?30

Necesidad de otros algoritmos

S Queremos el mejor alineamiento de todos los posibles S El que nos da una puntuacin mejor S El nmero de posibles alineamientos permitiendo huecos

para dos secuencias de longitud n esS Para n=30 1017

S Programacin dinmica: el problema se divide en

subproblemas, de manera que la solucin a los subproblemas simplifica la solucin del problema global31

Programacin dinmicaS Alineamiento global: Needleman-Wunsch (NW)S 1970, PMID: 5420325

S Alineamiento local: Smith-Waterman (SW)S 1981, PMID: 7265238

32

Puntuaciones

S Estos algoritmos funcionan en base a un sistema de

puntuaciones de cun parecidas son dos secuencias

S Por ejemplo S +1 por cada elemento igual (match) S -1 por cada elemento desigual (mismatch) S -1 por cada hueco introducido (gap) S Esta es una puntuacin muy simple que se usar slo para ilustrar el funcionamiento de los algoritmos NW y SWS Las puntuaciones se refinarn con PAM y BLOSUM ms adelante33

Alineamiento global Needleman-Wunsch: inicioS Creamos una matriz, con unaC0

O

E

L

A

C

A

N

T

H

secuencia en horizontal y la otra en vertical.S La primera fila y columna

-1

-2

-3

-4

-5

-6

-7

-8

-9

-10

P E L I C A N34

-1

-2

contienen valores de distancia al origen (gap scores)S Asegura el alineamiento

-3

-4

hacia atrs y hasta el origen

-5

-6

-7

NW: llenado o induccinS Para cada celda se calculan tresPC MM=-1 C0

valores, que son la suma de una celda adyacente ms el match/ mismatch (MM) de la celda actual S MM + celda superior S MM + celda izquierda S MM + celda superior izquierda

0-1=-1 -1-1=-2 -1-1=-2 E

O

L

A

C

A

N

T

H

-1

-2

-3

-4

-5

-6

-7

-8

-9

-10

P E L I C A35

-1

-1

-2

-3

-4

-5

-6

-7

-8

-9

-10

S Para cada celda S Se le asigna el mximo de los

-2

-2

-2

-1

-2

-3

-4

-5

-6

-7

-8

-3

-3

-3

-2

0

-1

-2

-3

-4

-5

-6

tres valores S Se le asigna la direccin a la celda que propici ese valor S En caso de que sean valores iguales, se elige un criterio de desempate

-4

-4

-4

-3

-1

-1

-2

-3

-4

-5

-6

-5

-3

-4

-4

-2

-2

0

-1

-2

-3

-4

-6

-4

-4

-5

-3

-1

-1

1

0

-1

-2

N

-7

-5

-5

-5

-4

-2

-2

0

2

1

0

NW: trace-backC O

E

L

A

C

A

N

T

H

S Seguimos la ruta con mejor score S Comenzando en la esquinaP E L I C A N

0

-1

-2

-3

-4

-5

-6

-7

-8

-9

-10

inferior derechaS Siguiendo las flechas S desplazamiento de la

-1

-1

-2

-3

-4

-5

-6

-7

-8

-9

-10

-2

-2

-2

-1

-2

-3

-4

-5

-6

-7

-8

-3

-3

-3

-2

0

-1

-2

-3

-4

-5

-6

cadena vertical respecto a la horizontalS desplazamiento de la

-4

-4

-4

-3

-1

-1

-2

-3

-4

-5

-6

-5

-3

-4

-4

-2

-2

0

-1

-2

-3

-4

horizontal respecto a la verticalS no hay desplazamiento36

-6

-4

-4

-5

-3

-1

-1

1

0

-1

-2

-7

-5

-5

-5

-4

-2

-2

0

2

1

0

COELACANTH" -PELICAN--"

Needleman-Wunsh: ejemplo real

Alineamiento local y globalGlobalS tiles cuando las secuencias

LocalS til con secuencias de distinto

tienen un tamao muy parecidoS Un alineamiento local hace

tamao pero que se espera que tengan regiones comunesS Los algoritmos tienen un coste

mltiples alineamientos globales sobre subsecuencias

computacional ms alto

Global " " Local " "

"FTFTALILLAVAV" "F-TAL-LLA-AV" "FTFTALILL-AVAV" "--FTAL-LLAAV--"38

Alineamiento local Smith-WatermanS Modificacin del algoritmo NW S La matriz se construye igual excepto que:S La primera fila y columna son 0s, en vez de -1,-2,-3,-4 S Mismatch es -1 y match 1S Si algn valor de celda queda negativo, lo ponemos a 0

S El trace-back comienza en la puntuacin ms alta y termina

cuando llegue a un 0

39

Smith-Waterman1 O vs E -1 + max(0,0,0) -1 0 2 L vs L 1 + max(0,1,0) 2 1 2

COELACANTH" -PELICAN--"

40

Smith-Waterman: ejemplo real

41

Alineamiento de pares de secuenciasIntroduccin Algoritmos Matrices de puntuacinPAM BLOSUM

S42


S Necesitamos mtodos de puntuacin ms sofisticados, con

sentido biolgico:S Gentico: coste de mutacin de un aminocido en otro S Qumico: similitud en las caractersticas de los aminocidos S Evolutivo: frecuencia evolutiva de cambio en aminocidosS Lod scores S PAM S BLOSUM

43

Thr ACG Glu GAA GAC S Matriz de coste de mutacin 3 3

ACA ACC 2 3 3 2

ACU 3 3

S Nmero mnimo de cambios de base requeridos para convertir un

aminocido en otro distinto (entre 1 y 3)44

S Matriz de similitud de caractersticas qumicasS El coste de mutacin tiene en cuenta el cdigo gentico, pero no tiene45

en cuenta la presin selectiva en los cambios de un aminocido a otro

Construccin de las matrices a partir de resultados experimentales

46


S Matriz con puntuaciones (lod scores) para todas las

sustituciones de aminocidos posiblesS Las puntuaciones representan estimaciones de la probabilidad

de sustitucin respecto a una sustitucin aleatoria S Se basa en las evidencias conocidas de sustituciones evolutivasS Los lod scores son nmeros reales, peroS Usualmente se representan mediante nmeros enteros (raw

scores) multiplicndolos antes por un factor de escala

47

Matrices de puntuacin: historiaS 1965: Emile Zuckerkandl y Linus

Pauling disean la primera matriz de puntuaciones para distintas secuencias de globina S Rojo: sustituciones que nunca ocurren S Blanco: sustituciones que ocurren en con una frecuencia menor al 20% S Con nmero si entre 21 y 39% S Gris: sustituciones que ocurren con una frecuencia del X% (>=40%) S Con parntesis si se tienen pocas evidencias para esa sustitucin48

Matrices de puntuacin: historia

S 1978: Dayhoff et al. estudiaron 1572

sustituciones en 71 grupos de protenas muy parecidas entre s S Accepted Point Mutation (PAM): sustitucin de un aminocido por otro, que ha sido aceptada por la seleccin natural para una determinada protena matriz de Dayhoff con una base de datos de 500 alineamientos (BLOCKS) entre protenas poco parecidas entre s

S 1992: Henikof y Henikof mejoran laMargaret Dayhoff

49

Matriz de DayhoffS Se reconstruye un rbol filogentico para cada uno de los 71

grupos de protenas (parecidas entre s, >=85% de similitud)S Y se determinan cuntos reemplazos (mutaciones aceptadas)

hay respecto al ancestro comn

50

ALEU

Aij

1572 mutaciones aceptadas (PAMs) estudiadas entre los distintos aminocidos, multiplicadas por 10 Por ejemplo, 20.7 de las 1572 PAMs ocurren entre Leu y Met Leu tiene un total de 142.8 mutaciones relacionadas51

Matriz de DayhoffPara Ala se toma un valor arbitrario de 100

mj

S

Mij probabilidad de que el aminocido j cambie al aminocido i en un intervalo evolutivo dado - constante de proporcionalidad (para Dayhoff, ~0.013) MMET-LEU = mLEUAMET-LEU/ALEU = 0.01340207/1428 = 0.08%

! m j Aij M ij = Aj

SMutabilidad relativa segn Dayhoff et al. 1978

S

52

Matriz con probabilidades de mutacin PAM1 1 PAM se define como la unidad de divergencia evolutiva en la que han ocurrido un 1% de mutaciones entre dos secuencias de protenas53

PAMn

S Podemos multiplicar la matriz PAM1 por s misma n veces para obtener

las probabilidades de sustitucin si hay un n% de probabilidades de que cada aminocido de la cadena haya mutado.S S

til para estudiar sustituciones entre aminocidos en protenas muy distintas, con probabilidad de sustitucin muy baja PAM60, PAM80, PAM100, PAM250

S Multiplicacin de matrices

54

qij

Matriz con probabilidades de mutacin PAM250 Para conseguir esta matriz, se multiplica la matriz PAM1 por s misma 250 veces

Matriz de puntuacin: lod scoresS Las matrices PAM calculadas no se utilizan directamente en los

algoritmos de alineamiento, requieren de una normalizacin previa para facilitar los clculos sustitucin de un aminocido por otro

S Lod (log odd) score: puntuacin del logaritmo de la frecuencia deS Las propiedades del logaritmo permiten sumar los lod scores, en

vez de multiplicarlos, durante el alineamiento, lo cual es computacionalmente menos costosoS

log(mn)=log(m)+log(n)

S Los lod scores son simtricos, simplificando las matrices. S Los lod scores suelen simplificarse a enteros (raw scores),

simplificando los clculos

56

lod scores en Dayhoffqij Sij = 10 ! log10 piS Sij lod score: logaritmo de la

frecuencia con la que el aminocido i se convierte en el aminocido j aparicin del aminocido i S Es una normalizacin de la mutabilidad relativa por j en PAMn

S pi frecuencia normalizada de

S qij probabilidad de sustitucin de i57

Lod scores: ejemploS El lod score de la sustitucin de Alanina (A) en Arginina (R) en PAM250 es: S SA,R=10xlog10(qAR/pA)=10xlog10(0.06/0.087)=-1.61 ~ -2 S Significado: la posibilidad de que haya una sustitucin de A por R en dos

cadenas (en un alineamiento regido por el estudio evolutivo de Dayhoff en PAM250) es 10-0.161 ~ un 70% de la posibilidad de que se d esa correspondencia aleatoriamenteS

Y en SA,A, que es igual a 2? 2=10xlog10(x) x=100.2=1.58

58

lod score PAM250

Es una matriz simtrica Debido a la normalizacin y redondeo al entero ms cercano Simplifica los clculos de los algoritmos de alineamiento Se dan lod scores simplificados al entero ms cercano (raw scores) Simplifican los clculos de los algoritmos de alineamiento Puede introducir pequeos errores (asumibles)

Qu PAM uso?

S El uso de una matriz PAM u otra depende de la similitud

entre las secuenciasS Para secuencias muy parecidas PAM10 puede dar buenos

alineamientos S Para secuencias muy distintas PAM250 puede ser mejorS A priori no siempre sabemos la similitud de las secuenciasS Puede ser necesario repetir los alineamientos con varias

matrices y quedarse con la que d el mejor alineamiento

60

BLOSUM

S BLOcks amino acid SUbstitution MatricesS Se construyen a partir de la base de datos BLOCKS, que

contiene segmentos alineados sin huecos, correspondientes a las regiones de protenas ms conservadasS BLOCKS contena inicialmente 500 patrones, ahora ~2000

S Cada matriz BLOSUM se refiere a un % de similitud en las

secuencias de partidaS BLOSUM45, BLOSUM62, BLOSUM80

61

BloqueS Ejemplo de bloque:

62

Clculo BLOSUMA" S En BLOSUM no conocemos el rbol filogentico: cualquier A" secuencia se considera un ancestro posible de las dems A" Pares posibles f AA = 6 + 5 + 4 + 3+ 2 +1 = 21 f AK = 7 A" A" f AA 21 f AK 7 Probabilidades de qAA = = = 0.75 A" qAK = = = 0.25 los pares f AA + f AK 21+ 7 f AA + f AK 21+ 7 A" K" Probabilidad de que A o qAS 0.25 qKK estn en un par

pA = qAA +

2

= 0.75 +

2

= 0.875 pK =

2

= 0.125

Probabilidad esperada de que ocurra AA o AK

eAA = pA ! pA = 0.76525

eAK = 2 ! pA ! pK = 0.21875

lod score

qij sij = 2 ! log 2 eij

sAA = 2 ! log 2

qAA " #0.06 eAA63

sAK = 2 ! log 2

qAK " 0.39 eAK

BLOSUM62Segn Henikoff & Henikoff (1992) BLOSUM62 es mejor alternativa que PAM y otros BLOSUM para un alineamiento genrico. Es utilizada como matriz por defecto por la mayora de los programas de alineamiento y de bsquedas en bases de datos

64

PAM vs BLOSUM

S PAM: basada en familias de protenas muy relacionadasS til para alinear secuencias parecidas

S BLOSUM: basada en observaciones de alineamientos entre

secuencias muy distintasS til para alinear secuencias distintas

65

La dimensin desconocidaS Hasta qu punto dos protenas

pueden divergir de forma detectable?S PAM250 considera que hay un

250% de probabilidades de que cada aminocido haya mutado equivale a una similitud del ~20% S El rea de similitud entorno al 20% se llama la twilight zone o dimensin desconocidaS Las secuencias pueden estar

relacionadas, pero no podemos detectarlo mediante el alineamiento66

Alineamiento de protenas vs alineamiento de ADNS Por qu no hablamos de matrices de puntuacin para

ADN?

S Normalmente el alineamiento de protenas nos da ms

informacin:

S Muchos cambios de un nucletido de un codn no varan el

aminocido resultante ms estable S Muchos aminocidos comparten propiedades biofsicas S Muchas protenas comparten estructura o regiones estructurales S El ADN sufre distintas modificaciones pos-translacionales que pueden influir en la protena que codifica

67

Matrices de puntuacin para nucletidosS No obstante, existen matrices para nucletidos

A T C GMatriz utilizada por BLAST

A T C G! 2" -7 2 " -7 -5 2" -5 -7 -7 2 "

Matriz PAM1 para nucletidos La transicin (mutacin entre purinas A-G, o entre pirimidinas C-T) es ms comn que la transversin (de purina a pirimidina)68

Resumen

S

La bioinformtica se basa en la comparacin de datos. Para maximizar la calidad de la comparacin de dos secuencias, necesitamos alinearlas. La comparacin de secuencias nos ayuda a inferir funciones, relaciones, dominios, etc. Para realizar el alineamiento, debemos decidir cmo evaluar las diferencias entre las secuencias (matriz de puntuacin) y qu estrategia usar para maximizar la similitud (algoritmo)

S

S

El algoritmo puede ser global (NW) o local (SW). NW alinea la secuencia completa a la vez y es til para secuencias similares en longitud. SW es una evolucin de NW y es til para secuencias ms variables, encontrando en general mejores soluciones, a costa de una mayor complejidad computacional. Las matrices de puntuacin ms usadas son PAM y BLOSUM, ambas basadas en evidencias evolutivas. Las matrices tienen distintas versiones, que corresponden a distintas suposiciones sobre la distancia evolutiva entre las dos secuencias a alinear

S

69

Preguntas para debate

S Al calcular los lod scores crees que los errores que introduce este

clculo adicional son asumibles? Prueba a calcular SR,A como se calcul SA,R en la diapositiva 58

S Si quieres comparar dos protenas, hay una matriz ideal que

utilizar? Hay algn modo de conocer cul es la mejor matriz de puntuacin a utilizar? dominio que evoluciona lentamente y otro que lo hace rpidamente. Para compararla con otra protena, usaras dos alineamientos distintos (por ej. con matrices PAM40 y PAM250) o uno solo, con una matriz intermedia?

S Muchas protenas tienen varios dominios. Imagina una que tiene un

70

Lecturas adicionales

S Pevsner, 2009: Ch 3 Pairwise Sequence Alignment S Yi-Kuo Yu and Stephen F. Altschul, The construction of amino acid

substitution matrices for the comparison of proteins with non-standard compositions, Bioinformatics. 2005 Apr 1;21(7):902-11,S

PMID: 15509610

S Eddy SR., Where did the BLOSUM62 alignment score matrix come

from? Nat Biotechnol. 2004 Aug;22(8):1035-6.S PMID: 15286655

71

72

Genome Valence es un proyecto de Ben Fry para visualizar el proceso de alineamiento de pares con BLAST Se representan las dos secuencias a alinear, que se van rompiendo en pedazos y unindose si se alinean http://benfry.com/genomevalence/

73

Documents

3_Alineamientos de Pares