1 ALINEAMIENTOS SIMPLE Y MÚLTIPLE Juan José Nieto Lunes, 11 de Julio de 2005

2 ALINEAMIENTO SIMPLE Consiste en establecer un segmento entre dos secuencias biológicas donde el número de coincidencias sea máximo

3 INDELS Inserción: INSERT Se asigna una base demasiado pronto Eliminación: DELETED Queda sin asignar una base Se introduce una nueva letra en el alfabeto DNA: El “hueco” (gap)-

4 Comparación Secuencia 1: M A R I A Secuencia 2: M I R I A M Secuencia 3: M A R I O Secuencia 4: A R I A D N A

5 Comparación MR I A Secuencia 1: M A R I A MR I A Secuencia 2: M I R I A M 4 coincidencias

6 Comparación MAR I Secuencia 1: M A R I A MAR I Secuencia 3: M A R I O 3 coincidencias

7 Comparación Secuencia 1: M A R I A Secuencia 4: A R I A D N A 0 Coincidencias

8 Comparación A R I A Secuencia 1: M A R I A A R I A Secuencia 4: - A R I A D N A 4 Coincidencias

9 Comparación Secuencia 5: J O S E Secuencia 6: P E P E

10 Comparación E Secuencia 5: J O S E E Secuencia 6: P E P E 1 coincidencia

11 Comparación DNA - Comparación DNA - Leucina T Secuencia : T T A T Secuencia : C T G 1 coincidencia

12 ALINEAMIENTO SIMILITUD  Cuantitativo HOMOLOGÍA  Cualitativo

13 Clasificación Alineamientos

14 Por número de secuencias Simple Múltiple

15 Por nivel de análisis Global Local

16 Programas BLAST (Basic Local Alignment Search Tool) http://www.ncbi.nlm.nih.gov FASTA http://www.ebi.ac.uk

17 BLAST blastp blastn blastx tblastn tblastx

18 Ejemplo g c t g a a c g c t a t a a t c

19 2 coincidencias gctgaacg ctataatc

20 Otro alineamiento (Muy malo) --------gctgaacg ctataatc--------

21 Otro alineamiento (1 coincidencia) ----gctgaacg ctataatc----

22 Otro alineamiento (malo) gctga-a--cg --ct-ataatc

23 Otro alineamiento (bueno) Otro alineamiento (bueno) 5 coincidencias gctg-aa-cg -ctataatc-

24 ¿Cuántos alineamientos posibles hay? Problema combinatorio No se permite alinear dos huecos Hay un número finito de alineamientos

25 Número de alineamientos Primera secuencia: 8 letras Segunda secuencia: 8 letras Hay 265 729 alineamientos posibles

26 ¿Cómo elegir el mejor alineamiento? Hay que dar un valor a cada alineamiento Elegiremos el (los) que tengan mayor puntuación. Por ej.: Coincidencia  +1 puntos No coincidencia  0 puntos número de coincidencias Nos da el número de coincidencias

27 Otra puntuación Por ej.: Coincidencia  +2 puntos No coincidencia  -1 punto

28 2 coincidencias Puntuación: -2 puntos gctgaacg ctataatc

29 Otro alineamiento -10 puntos ----gctgaacg ctataatc----

30 Otro alineamiento - 11 puntos gctga-a--cg --ct-ataatc

31 Otro alineamiento 5 puntos gctg-aa-cg -ctataatc-

32 Algoritmo (teórico) Paso 1 : Considerar todos los alineamientos posibles Paso 2 :Determinar un valor para ese alineamiento Paso 3 :Guardar el valor máximo

33 Problema El número de operaciones crece e una forma “exagerada”

34 Número de alineamientos de dos secuencias de longitud n,m n = m = 8  265 729 alineamientos n = m = 10  8 097 453 alineamientos

35 Fórmula del número de alineamientos posibles para dos secuencias de longitud n y m: f(n,m)

36 Fórmula de recurrencia f(n+1, m+1) = f(n,m+1) + f(n+1,m) + f(n,m)

37 Demostración Se basa en que el final de un alineamiento es: (-, letra), (letra, - ) ó (letra, letra) A. Torres, A. Cabada, J.J. Nieto “An exact formula for the number of alignments between two DNA sequences” DNA SEQUENCE (2003)

38 Consecuencias f(n+1,n+1) > 3 n f (107, 107 ) > 10 80 Una secuencia “pequeña” tiene 200-500 nucleótidos Una proteína sobre 200-400 aminoácidos

39 Alineamiento global: Algoritmo de Neddleman&Wunsch (1970)

40 Ejemplo gctgaacg ctataatc

41 gctgaacg c11 t1 a11 t1 a11 a11 t1 c11

42 ¿Cómo se puede determinar el alineamiento óptimo? Aunque no tengamos ni idea, sabemos una cosa: El alineamiento tiene que tener una de las tres terminaciones siguientes g-g -cc

43 gctgaacg c11 t1 a11 t1 a11 a11 t1 c11

44 Terminación cg c-

45 gctgaacg c11 t1 a11 t1 a11 a11 t1 c11

46 gctgaa c1 t1 a11 t1 a11 a11 t1

47 Simplificación del problema original Secuencia 1: g c t g a a Longitud 6 Secuencia 2: c t a t a a t Longitud 7

48 Posibles terminaciones a-a -tt

49 gctgaa c1 t1 a11 t1 a11 a11 t1

50 Terminación a- at

51 gctgaa c1 t1 a11 t1 a11 a11 t1

52 4 últimas posiciones del alineamiento a-cg atc-

53 gctga c1 t1 a1 t1 a1

54 gctga c1 t1 a1 t1 a1

55 Posibles terminaciones a-a -aa

56 5 últimas posiciones del alineamiento aa-cg aatc-

57 gctg c1 t1 a t1

58 gctg c1 t1 a t1

59 Posibles terminaciones g-g -tt

60 Terminación correspondiente a la última submatriz tg t-

61 gctg c1 t1 a t1

62 7 últimas posiciones del alineamiento tgaa-cg t -aatc-

63 gc c1 t a

64 gc c1 t a

65 Posibles terminaciones c-c -aa

66 Terminación correspondiente a la última submatriz gc-- -cta

67 Alineamiento Final 5 coincidencias g c - - t g a a - c g - c t a t - a a t c -

68 Alineamiento Final 5 coincidencias g c - - t g a a - c g - c t a t - a a t c -

69 Observación importante Hemos valorado positivamente las coincidencias, pero no hemos penalizado la introducción de huecos ni las no coincidencias

70 Alineamiento global PROGRAMACIÓN DINÁMICA 1.- Función de similitud 2.- Los indels se penalizan con un peso 3.- Se construye una matriz 4.- Se recupera la solución

71 Programación Dinámica 1.- Coincidencia: +1 No coincidencia: 0 2.- Introducción de “huecos”: 0

72 Ejemplo Programación dinámica g g a t c g a g a a t t c a g t t a

73 ggatcga g a a t t c a g t t a

74 ggatcga 00000000 g0 a0 a0 t0 t0 c0 a0 g0 t0 t0 a0

75 ggatcga 00000000 g0 a0 a0 t0 t0 c0 a0 g0 t0 t0 a0

76 Cálculo de los elementos de la matriz H(i-1,j-1)H(i,j-1) H(i-1,j)H(i,j)

77 Entradas matriz H(i,j) es el máximo entre:  H(i-1,j-1)+c(x i,y i )  H(i-1,j)-w  H(i,j-1)-w

78 ggatcga 00000000 g0 a0 a0 t0 t0 c0 a0 g0 t0 t0 a0

79 ggatcga 00000000 g01 a0 a0 t0 t0 c0 a0 g0 t0 t0 a0

80 ggatcga 00000000 g01111111 a01 a01 t01 t01 c01 a01 g01 t01 t01 a01

81 ggatcga 00000000 g01111111 a01 a01 t01 t01 c01 a01 g01 t01 t01 a01

82 ggatcga 00000000 g01111111 a011 a01 t01 t01 c01 a01 g01 t01 t01 a01

83 ggatcga 00000000 g01111111 a011 a01 t01 t01 c01 a01 g01 t01 t01 a01

84 ggatcga 00000000 g01111111 a0112 a01 t01 t01 c01 a01 g01 t01 t01 a01

85 ggatcga 00000000 g01111111 a01122222 a01122223 t01123333 t01123333 c01123444 a01123445 g01223455 t01223455 t01223455 a01233456

86 ggatcga 00000000 g01111111 a01122222 a01122223 t01123333 t01123333 c01123444 a01123445 g01223455 t01223455 t01223455 a01233456

87 Alineamiento Programación dinámica g g a - t - c - g - - a g - a a t t c a g t t a

88 Alineamiento Programación dinámica Alineamiento Programación dinámica 6 coincidencias g g a - t - c - g - - a g - a a t t c a g t t a

89 Ejemplo Programación dinámica gctgaacg ctataatc

90 ctataatc 000000000 g0 c0 t0 g0 a0 a0 c0 g0

91 ctataatc 000000000 g000000000 c011111111 t012222222 g012222222 a012333333 a012334443 c012334445 g012334445

92 ctataatc 000000000 g000000000 c011111111 t012222222 g012222222 a012333333 a012334443 c012334445 g012334445

93 Alineamiento Final Programación dinámica 5 coincidencias / 5 puntos - c t a t a a t c - g c t g - a a - c g

94 ctataatc 000000000 g000000000 c011111111 t012222222 g012222222 a012333333 a012334443 c012334445 g012334445

95 Alineamiento Final Programación dinámica 5 coincidencias / 5 puntos - c t - a t a a t c - g c t g a - a - - c g

96 Programación Dinámica 1.- Coincidencia: +2 No coincidencia: -1 2.- Introducción de “huecos”: -1

97 ctataatc 0-2-3-4-5-6-7-8 g -2-3-4-5-6-7-8 c-210-2-3-4-5 t-303210-2-3 g-42210 -2-3 a-5-21433210 a-6-30335543 c-7-4224446 g-8-5-2113335

98 ctataatc 0-2-3-4-5-6-7-8 g -2-3-4-5-6-7-8 c-210-2-3-4-5 t-303210-2-3 g-42210 -2-3 a-5-21433210 a-6-30335543 c-7-4224446 g-8-5-2113335

99 Alineamiento Final Programación dinámica 5 coincidencias / 4 puntos - c t - a t a a t c - g c t g a - a - - c g

100 M. Tuberculosis 1-100 cta ttgaccgatgaccccggttcaggcttc accacagtgtggaacgcggtcgtctc cgaacttaacggcgaccctaaggttg acgacggacccagcagtgatg

101 BlastN http://www.ebi.ac.uk BlastN http://www.ebi.ac.uk c t a t

102 BlastN http://www.ebi.ac.uk BlastN http://www.ebi.ac.uk c t a t a a t

103 c t a t a a t c t a t a a t EMBL:HS216E10Z83840Human DNA sequence from clone CTA-216E10 on chromosone 22.....122320 EMBL:CHCRRU573U57326 Chlamudomonas reinhardtii RpoC2 protein......10826

104 Alineamiento Múltiple

105

106 FIN