Para qué nos sirve comparar secuencias?

Para inferir la posible función de una proteína nueva.

Para la secuenciación de fragmentos muy largos de ADN(ordenamiento de contigs).

Para estudios filogenéticos.

...fácil para el hombre,difícil para la computadora.

MSLFLGVRVRAEEAGARVQQNVPSGTDTGDPQSKPLGDWAAGTMDPESSIFIEDAIKYF KEKVSTQNLLLLTDNEAWNGFVAAAELPRNEADELRKALDNLARQMIMKDKNWHDKG QQYRNWFLKEFP RLKSKLEDNTRRLRALADGVQKVHKGTTIANVVSGSLSISSGILTLVG MGLAPFTEGGSLVLLEPGMELGITAALTGITSSTIDYGKKWWTQAQAHDLVIKSLDKLKE

LLLPCIPLASTATRATPEQLRKCKFQQPWSKEKVSTQNLLLLTDNEAWNGFVAAAELPRN EADELRKALDNLARQMIMKDKNWHDKGQQYRNWFLKEFP RLKSKLEDNTRRLRALAD GVQKVHKGTTIANVVSGSLSISSGILTLVGMGLAPFTEGGSLVLLEPGMELGITAALTGITS STIDYGKKWWTQAQAHDLVIKSLDKLKEFLDCYHEKSD FPTYWIVIVGIINILSCTFF SITI YPTFNFGWNSPNALGY PQEPDEHIPL

MEELQDDYEDMMEENLEQEEYEDPDIPESQMEEPAAHDTEATATDYHTTSHPGTHKVYVELQELVMDEKNQELRWMEAARWVQLEENLGENGAWGRPHLSHLTFWSLLELRRVFTKGTVLLDLQETSLAGVANQLLDRFIFEDQIRPQDREELLRALLLKHSHAGELEALGGVKPAVLTRDPSQPLLPQHSSLETQLFCEQGDGGTEGHSPSGILEKI PPDSEATLVLVGRADFLEQPVLGFVRLQEAAELEAELPVPIRFLFVLLGPEAPHIDYTQLGRAAATLMS ERVFRIDAYM

MSLFLGVRVRAEEAGARVQQNVPSGTDTGDPQSKPLGDWAAGTMDPESSIFIEDAIKYF KEKVSTQNLLLLTDNEAWNGFVAAAELPRNEADELRKALDNLARQMIMKDKNWHDKG QQYRNWFLKEFP RLKSKLEDNTRRLRALADGVQKVHKGTTIANVVSGSLSISSGILTLVG MGLAPFTEGGSLVLLEPGMELGITAALTGITSSTIDYGKKWWTQAQAHDLVIKSLDKLKE

LLLPCIPLASTATRATPEQLRKCKFQQPWSKEKVSTQNLLLLTDNEAWNGFVAAAELPRN EADELRKALDNLARQMIMKDKNWHDKGQQYRNWFLKEFP RLKSKLEDNTRRLRALAD GVQKVHKGTTIANVVSGSLSISSGILTLVGMGLAPFTEGGSLVLLEPGMELGITAALTGITS STIDYGKKWWTQAQAHDLVIKSLDKLKEFLDCYHEKSD FPTYWIVIVGIINILSCTFF SITI YPTFNFGWNSPNALGY PQEPDEHIPL

MEELQDDYEDMMEENLEQEEYEDPDIPESQMEEPAAHDTEATATDYHTTSHPGTHKVYVELQELVMDEKNQELRWMEAARWVQLEENLGENGAWGRPHLSHLTFWSLLELRRVFTKGTVLLDLQETSLAGVANQLLDRFIFEDQIRPQDREELLRALLLKHSHAGELEALGGVKPAVLTRDPSQPLLPQHSSLETQLFCEQGDGGTEGHSPSGILEKI PPDSEATLVLVGRADFLEQPVLGFVRLQEAAELEAELPVPIRFLFVLLGPEAPHIDYTQLGRAAATLMS ERVFRIDAYM

...fácil para la computadora, difícil para el hombre!

Alineamiento global

r, s : cadenas originalesr´, s´: cadenas aumentadas (con posibles gaps)

Un alineamiento global de las cadenas r y s es un alineamiento tal que:• long(r´) = long(s´)• para cada posición i se cumple que, o bien s´[i] no es un espacio o bien r´[i] no es un espacio.

Score

Match = +1Mismatch= -1Espacio= -2

GA–CGGATTAGGATCGGAATAG

r :s :

Score(r,s) = 9 x 1 + 1 x (-1) + 1 x (-2) = 6

Similitud(r,s) = max Score (r,s)alig

Una función de score es una función que confiere un valor a un alineamiento.

Para alinear s[1...i] con r[1...j] tenemos las siguientes alternativas:

-alinear s[1...i] con r[1...j-1] y encolumnar un espacio con r[j]-alinear s[1...i-1] con r[1...j-1] y encolumnar s[i] con r[j]-alinear s[1...i-1] con r[1...j] y encolumnar s[i] con un espacio

Sim(s[1...i], r[1...j] ) = max

Sim(s[1...i], r[1...j-1]) - 2

Sim(s[1...i-1], r[1...j-1]) + score(s[i],r[j])

Sim(s[1...i-1], r[1...j]) - 2

En la matriz...

M(i, j) = max

M(i, j-1) - 2

M(i-1, j-1) + score(s[i],r[j])

M(i-1, j) - 2

-4 -6-20

-1 -31-2

0 -2-1-4

-2 -1-3-6

-4 -1-5-8

A

A

A

C

A G CMatriz de similitud parael alineamiento entre AAAC y AGC

Algoritmo para calcular la similitud entre dos cadenas

Entrada: secuencias r y sSalida: similitud(r,s)

Para i = 0 hasta long(r) hacer M[i,0] = i x score de un espacio

Para j = 0 hasta long(s) hacer M[0,j] = j x score de un espacio

Para i = 0 hasta long(r) hacer Para j = 0 hasta long(s) hacer M[i,j] = max de ( M[i-1] + Score de un espacio, M[i-1,j-1] + Score (s[i],r[j]), M[i,j-1] + Score de un espacio)

Devolver M[long(r) , long(s) ]

Alineamiento local

Un alineamiento local de las cadenas r y s es un alineamiento global entre una subcadena de r con una subcadena de s.

Para el alineamiento local la primera fila y la primera columna de la matrizde similitud M se inicializan con ceros.

M(i, j) = max

M(i, j-1) - 2

M(i-1, j-1) + score(s[i],r[j])

M(i-1, j) - 2

0

Gaps

Función de penalización de gaps:

w(k) = c + g.k (k = long. del gap)

a[i,j] = máximo score de un alineamiento entre r[1...i] y s[1...j ] que termina con r[i] encolumnado con s[j]

b[i,j] = máximo score de un alineamiento entre r[1...i] y s[1...j ] que termina con un espacio encolumnado con s[j]

c[i,j] = máximo score de un alineamiento entre r[1...i] y s[1...j ] que termina con r[i] encolumnado con un espacio

a [i, j] = score(s[i],r[j]) + maxa[i-1, j-1]

b[i-1, j-1]

c[i-1, j-1]

b [i, j] = maxa[i, j-1] – (c + g)

b[i, j-1] – g

c[i, j-1] – (c + g)

c [i, j] = maxa[i-1, j] – (c + g)

b[i-1, j] – (c + g)

c[i-1, j] – g

Para 1 i long(r) y para 1 j long(s):

a[0,0] = 0a[i,0] = - para 1 i long(r) a[0,j] = - para 1 j long(s)

b[i,0] = - para 1 i long(r)b[0,j] = -(c + g.j) para 1 j long(s)

c[i,0] = -(c + g.j) para 1 i long(r)c[0,j] = - para 1 j long(s)

Similitud(r,s) = max (a [m,n], b [m,n], c [m,n]) con m = long (r) n = long(s)