View
97
Download
0
Category
Preview:
Citation preview
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 1/300
ALINEAMIENTO DE SECUENCIAS
INTRODUCCION A TECNICAS DE MINERIADE DATOS
Mg. Samuel Oporto Díaz
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 2/300
Mapa Conceptual – Minería de Datos
DataObjetivo
DataPre-procesada
Data Transformada Patrones
Fuentes de datos Pre-procesamientoExploración y
transformaciónReconocimiento de
PatronesEvaluación eInterpretación
DatacrudaDHW
DBMS
Texto
Evaluación yEntendimien
to
Muestreo ySelección
• Muestreo• Selección
Limpieza deDatos
• Limpieza dedatos
• Datos que noexisten
• Datos no
clasificados• Identificación de
Transformaciónde Datos
• Reducción deDimensionalidad
• Creación deCaracterísticas
• Normalización de
Datos• Variables
Correlacionadas
Reportes yVisualización
Modelado• Descripción• Clasificación• Regresión• Agrupamient
o• Asociación
• Secuenciación
•
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 3/30033 /39/39
Tabla de Contenido
• Introducción 4
• Pre-procesamiento 9• Reducción de Datos 26
• Selección de Instancias 36
• Selección de Características 40
• Ejemplo
– Planteamiento del Problema 49
– Procedimiento de solución 53
– Algoritmos 58 – Fuentes de Datos 64
– Diseño de Experimentos 66
– Resultados Experimentales 68
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 4/30044 /39/39
INTRODUCCION
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 5/30055 /39/39
PREGUNTAS
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 6/30066 /39/39
Alineamiento de secuencias
Fernán Agüero
Instituto de Investigaciones BiotecnológicasUniversidad Nacional de General San Martín
<fernan at iib.unsam.edu.ar>
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 7/30077 /39/39
Análisis comparativo
Finches of the Galápagos Islands observed byCharles Darwin on the voyage of HMS Beagle
El alineamiento de
secuencias es similar aotros tipos de análisiscomparativo.
En ambos es necesariocuantificar las similitudesy diferencias (scoring)entre un gruporelacionado de entidades.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 8/30088 /39/39
Para qué alinear?• Para poder comparar dos secuencias
– Dos proteínas o genes con función similar pero provenientes de distintosorganismos
• Analizar variación, conservación de residuos importantes para la función
• Detectar patrones que sirvan para detección diferencial (diagnóstico)
– Dos proteínas distintas pero con una región o dominio similar
• Proteína X de función conocida contiene un dominio Y
• Proteína Z de función desconocida también tiene un dominio Y. Puedo decir algoacerca de su probable función?
– Un mRNA y el gen correspondiente: detección de la organización génica
• El mRNA contiene secuencias derivadas de los exones solamente
• El gen contiene tanto intrones como exones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 9/30099 /39/39
Homología vs similitud• Homología entre dos entes biológicos implica una herencia
compartida
• Homología es un término cualitativo
• Se es homólogo o no se es
• Similitud implica una apreciación cuantitativa o una cuantificacióndirecta de algún caracter
• Podemos usar una medida de similitud para inferir homología
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 10/3001010 /39/39
Análisis comparativo
Los algoritmos que
alinean secuenciasmodelan procesosevolutivos
GATTACCA
GATG ACCA GATTACCA
inserción
GATTG ATCA
GATTACCA GATTATCA GATTACCA
GATC ATCA
sustitución deleción
GAT _ ACCA
Deriva de un ancestro comúna través de cambiosincrementales debido aerrores en la replicación delDNA, mutaciones, daño ocrossing-over desigual.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 11/3001111 /39/39
Análisis comparativo
Algoritmos de alineamiento
modelan procesos evolutivos
GATTACCA
GATGACCA GATTACCA
Deriva a partir de un ancestrocomún a través de cambioincremental. GATCATCA GATTGATCA
GATTACCA GATTATCA GATTACCA
GATACCA
Sólo las secuencias actuales son conocidas, lassecuencias ancestrales se postulan.
GATCATCA GATTGATCA
GATTACCA
GATACCA
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 12/300
1212 /39/39
Análisis comparativo
La palabra homología implica una herencia común(un ancestro común), el cual puede ser inferido apartir de observaciones de similitud de secuencia.
Algoritmos de alineamiento
modelan procesos evolutivos
GATTACCA
GATGACCA GATTACCA
Deriva a partir de unancestro común a través decambio incremental.Mutaciones que no matan alindividuo pueden pasar a lapoblación.
GATCATCA GATTGATCA
GATTACCA GATTATCA GATTACCA
GATACCA
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 13/300
1313 /39/39
Alineamientos
• Qué es un alineamiento?
– El procedimiento de comparación de dos (o más) secuencias demanera de lograr que una serie de caracteres individuales opatrones de caracteres que se encuentren en el mismo orden enambas secuencias queden “alineados” verticalmente.
– AATTGGCCGTACGT – AATTGGCCGTACGT
• Cómo alineamos dos secuencias?
– a mano o con la ayuda de un programa – usando un método/algoritmo
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 14/300
1414 /39/39
Definición de alineamiento: tipos
Alineamientos locales:
Alineamiento global:
Alineamiento:
Todas las bases se alinean con otra base o con ungap (“-”)
Cada base se usa a lo sumo una vez
No hay necesidad de alinear todas las bases
Align BILLGATESLIKESCHEESE and GRATEDCHEESE
G-ATESLIKESCHEESE or G-ATES & CHEESE
GRATED-----CHEESE GRATED & CHEESE
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 15/300
1515 /39/39
Alineamientos buenos y malos?Cuál es el ‘mejor’ alineamiento?
GCTACTAGTT------CGCTTAGC
GCTACTAGCTCTAGCGCGTA TAGC
GCTACTAG-T-T--CGC-T-TAGCGCTACTAGCTCTAGCGCGTATAGC
0 mismatches, 5 gaps
3 mismatches, 1 gap
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 16/300
1616 /39/39
Cómo decidir cuál es el mejor?• Respuesta: el más significativo desde el punto de vista
biológico• Pero: necesitamos una medida objetiva
• sistemas de puntaje (scoring)
– reglas para asignar puntos – el más simple: match, mismatch, gap
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 17/300
1717 /39/39
Un primer ejemplo de scores
G- ATESLIKESCHEESE
GRATED-----CHEESE
Score
(10 * 1) + (1 * 0) + (6 * (-1)) = +4
Ejemplo de sistema de score
match = +1 mismatch = 0 gap = -1
Usando otro sistema de score
Score
(10 * 2) + (1 * 0) + (6 * (-1)) = +14
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 18/300
1818 /39/39
Puedo comparar scores?
• Primera conclusión importante:
– no tiene sentido comparar scores de distintos alineamientos
– a menos que el sistema de scoring utilizado sea el mismo en los
distintos alineamientos
– Es importante especificar el sistema de puntaje!
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 19/300
1919 /39/39
Gap penalties
1- Abrir un gap es costoso
GCTACTAGTT------CGCTTAGCGCTACTAGCTCTAGCGCGTATAGC
GCTACTAG-T-T--CGC-T-TAGCGCTACTAGCTCTAGCGCGTATAGC
Penalty = 5 * (-5) + 6 * (-1) = -31
Penalty = 1 * (-5) + 6 * (-1) = -11
2 - Extender un gap es menos costoso
gap opening penalty = -5gap extension penalty = -1
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 20/300
2020 /39/39
Dot plots: introducciónDot-plot: Fitch, Biochem. Genet. (1969) 3, 99-108.
A
C
G
T
C G T A C C G T
0 0 0 1 0 0 0 0
1
0
0
0 0 0 1 1 0 0
1 0 0 0 0 1 0
0 1 0 0 0 0 1
Eje horizontal: secuencia 1
E j e
v e r t i c a l :
s e c u e n c i a
2
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 21/300
2121 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 22/300
2222 /39/39
Dot Matrix Plot
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 23/300
2323 /39/39
Dot Matrix Plot
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 24/300
2424 /39/39
Dot Matrix Plot
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 25/300
2525 /39/39
Similitud local
FXII F2 E F1 E K Catalytic
PLAT F1 E K CatalyticK
Dominios mezclados confunden alos algoritmos de alineamiento.
Módulos en el factor XII de coagulación y en el activadorde plasminógneos – tissue plasminogen activator (PLAT)
F1,F2 Fibronectin repeatsE EGF similarity domainK Kringle domainCatalytic Serine protease activitiy
Módulos en ordenreverso
Módulosrepetidos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 26/300
2626 /39/39
Dot plots: ejemplo
T i s
s u e P l a s m i n o g e n A c
t i v a t o r ( P L A T )
Coagulation Factor XII (F12)
K
K
Catalytic
C a t a l y t i c
K
EF1EF2
E
F 1
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 27/300
2727 /39/39
Dot plots: ejemplo (cont.)
T i s
s u e P l a s m i n o g e n A c
t i v a t o r ( P L A T )
Coagulation Factor XII (F12)
K
K
Catalytic
C a t a l y t i c
K
EF1EF2
E
F 1
Dominios repetidosmuestran un patróncaracterístico.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 28/300
2828 /39/39
Dot plots: path graphs
90 137
7 2
2 3
90 137
7 2
2 3
PLAU 90 EPKKVKDHCSKHSPCQKGGTCVNMP--SGPH-CLCPQHLTGNHCQKEK---CFE 137
PLAT 23 ELHQVPSNCD----CLNGGTCVSNKYFSNIHWCNCPKKFGGQHCEIDKSKTCYE 72
Dominios EGF conservados en la urokinse plasminogenactivator (PLAU) y el tissue plasminogen activator(PLAT)
Dot plots sugierencaminos (paths) através del espacio dealineamientos posibles.
Path graphs sonrepresentacionesmás explícitas deun alineamiento.
Cada path es unalineamiento único.
P th h t l j i
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 29/300
2929 /39/39
Path graphs: encontrar el mejor camino
Rutear una llamada telefónica desdeNY a San FranciscoLos problemas queinvolucran encontrar lamejor ruta o camino(Best-path problems)son comunes encomputación científica.
El algoritmo paraencontrar el mejorcamino entre dosextremos y pasando porvarios puntos se llama
‘dynamic programming’
D i i i t d ió
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 30/300
3030 /39/39
Dynamic programming: introducción
G A T A C T A
G A T T A C C A
Construir unalineamiento óptimoentre estas dossecuencias
Utilizando lassiguientes reglas descoring:
Match:
Mismatch:Gap:
+1
-1-1
Un ejemplo:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 31/300
3131 /39/39
Dynamic programming: ejemplo
G A T A C T A G A
TT A
CC A
Ordenar las dossecuencias en una
matriz bidimensional
Los vértices de cadacelda se encuentranentre letras (bases).
Needleman & Wunsch(1970)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 32/300
3232 /39/39
(cont.)
G A T A C T A G A
TT A
CC A
El objetivo esencontrar la ruta(path) óptimo
Desde aquí
Hasta acá
Dynamic programming: paths posibles
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 33/300
3333 /39/39
Dynamic programming: paths posibles
G A T A C T A G A
TT A
CC A
Cada path corresponde aun alineamiento único
Cuál es el óptimo?
Dynamic programming: scores: match
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 34/300
3434 /39/39
Dynamic programming: scores: match
G A T A C T A G A
TT A
CC A
El score para unaruta (path) es lasuma incremental de
los scores de suspasos (diagonales olados).
A alineada con A Match = +1
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 35/300
3535 /39/39
mismatch
G A T A C T A G A
TT A
CC A
A alineada conT
Mismatch = -1
El score para unaruta (path) es lasuma incremental de
los scores de suspasos (diagonales olados).
Dynamic programming: scores: gaps
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 36/300
3636 /39/39
Dynamic programming: scores: gaps
G A T A C T A G A
TT A
CC A
T alineada con NADA
Gap = -1
T alineada con NADA
El score para unaruta (path) es lasuma incremental de
los scores de suspasos (diagonales olados).
Dynamic programming: paso a paso (1)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 37/300
3737 /39/39
Dynamic programming: paso a paso (1)
G A T A C T A G A
TT A
CC A
Extender el path paso por paso
0 -1
+1-1
G
G
–
G
G
–
+1 -1 -1
Dynamic programming: paso a paso (2)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 38/300
3838 /39/39
Dynamic programming: paso a paso (2)
G A T A C T A G A
TT A
CC A
0
+1-1
-2
-2
-1
Recordar el mejorsubpath que lleva acada punto en lamatriz.
Incrementar el path paso a paso
Dynamic programming: paso a paso (3)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 39/300
3939 /39/39
G A T A C T A G A
TT A
CC A
0
-1
-2
0 +2
+1
-1
-20
Dynamic programming: paso a paso (3)
Recordar el mejorsubpath que lleva acada punto en lamatriz.
Incrementar el path paso a paso
Dynamic programming: paso a paso (4)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 40/300
4040 /39/39
G A T A C T A G A
TT A
CC A
0 -2
0 +2
+1
-1
-20
-2
-1
Dynamic programming: paso a paso (4)
Recordar el mejorsubpath que lleva acada punto en lamatriz.
Incrementar el path paso a paso
Dynamic programming: paso a paso (5)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 41/300
4141 /39/39
G A T A C T A G A
TT A
CC A
0
+1
-1
-2-1
-3-2
-3
-2
+3
-1
-1
0
0
+1
+1
+2
Dynamic programming: paso a paso (5)
Recordar el mejorsubpath que lleva acada punto en lamatriz.
Incrementar el path paso a paso
Dynamic programming: paso a paso (6)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 42/300
4242 /39/39
G A T A C T A G A
TT A
CC A
0
+1
-1
-1
-2
-2 0
0
+1+2
-5-4
-5
-4
-3
-3
-1 -3-2
-10
+1
+2
0
+1-1
+2
-3 -1
-2
+1 +3
+2 +1
+2+3
Dynamic programming: paso a paso (6)
Recordar el mejorsubpath que lleva acada punto en lamatriz.
Incrementar el path paso a paso
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 43/300
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 44/300
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 45/300
4545 /39/39
obtenido
G A T A C T A G A
TT A
CC A
Imprimir el alineamiento
A
A
-
T
T
T
A
A
C
C
T
C
A
A
G
G
Dynamic programming: Smith-Waterman
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 46/300
4646 /39/39
Dynamic programming: Smith-Waterman
• El método fue modificado (Smith-Waterman) para obtener
alineamientos locales
• El método garantiza la obtención de un alineamiento óptimo(cuyo score no puede ser mejorado)
• La complejidad es proporcional al producto de las longitudesde las secuencias a alinear
G
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 47/300
4747 /39/39
Gracias aHugues Sicotte (NCBI)
(slides DP, HMS Beagle)
Marcelo Viegas(slides Dot Matrix)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 48/300
4848 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 49/300
4949 /39/39
Algoritmos de alineamiento optimo
para pares de secuencias
Ali i t ó ti
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 50/300
5050 /39/39
Alineamientos óptimos
• Una vez fijado un sistema de puntuación
– Matriz de substitución (Identidad, PAMxx, BLOSUM…) – Coste de la apertura y de la extensión de “gaps”
• Se define el alineamiento óptimo entre dos secuencias comoaquel cuya puntuación és máxima entre todos los posiblesalineamientos.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 51/300
5151 /39/39
Un algoritmo exhaustivo para obtener
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 52/300
5252 /39/39
Un algoritmo exhaustivo para obtener alineamientos óptimos
• Una posible aproximación para encontrar el alineamientoóptimo es la búsqueda exhaustiva: – Construir todos los posibles alineamientos
– Calcular la puntuación de cada uno
– El alineamiento óptimo es el que obtenga el valor más grande(puede haber más de uno!)
• El número de alineamientos posibles es muy alto: Si S, T constan de unos 20 caracteres pueden hacer falta más de240 operaciones!!!
U lt ti l bú d h ti
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 53/300
5353 /39/39
Una alternativa a la búsqueda exhaustiva:La programación dinámica (PD)
• La programación dinámica es una técnica de diseño de
algoritmos consistente en – Considerar, en primer lugar, los casos más sencillos de unproblema
– Resolverlos
– Combinarlos par a obtener la solución de casos más
complicados – Hasta resolver el caso completo original
Veamos un ejemplo
Có tili ió di á i
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 54/300
5454 /39/39
Cómo utilizar programación dinámica paraobtener el alineamiento óptimo?
• Se obtiene un alineamiento óptimo para una subsecuencia, – P.ej. el primer carácter de cada secuencia por la izquierda.
• El alineamiento óptimo de la subsecuencia inicial se mantendráen el alineamiento óptimo final
– cualquier otro puntuaría menos que éste disminuiría la puntuación
total• Tras alinear la primera subsecuencia ya no hace falta trabajar conella Se pasa a la subsecuencia siguiente y así se va iterandohasta el final
– el coste de cada paso es bajo
– el resultado final se obtiene de acumular los resultados de cada paso
El algoritmo de Needleman y Wünsch:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 55/300
5555 /39/39
g y Alineamiento basado en programación
dinámica
Un alineamiento puede representarse como
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 56/300
5656 /39/39
p pun camino en una matriz (de puntuaciones)
T C G C A
T
C
C A
T C G C A
T
C
C
A
TCGCA TC-CA
TCGCA T-CCA
Un alineamiento puede representarse como
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 57/300
5757 /39/39
T C G C A
T
C
C A
s22
El significado de cada punto enla matriz es el siguiente: Todos
los caracteres hasta el punto se
han alineado,
Puede ser, sin embargo quehaya muchos caminos que
llevan al punto
La posición etiquetada “s22” representa TC alineado con TC
--TC -TC TCTC-- T-C TC
p pun camino en una matriz (de puntuaciones)
Calculo de la matriz de puntuaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 58/300
5858 /39/39
Calculo de la matriz de puntuaciones• Cualquier posición de la matriz sólo
puede alcanzarse de tres maneras
posibles: – En diagonal lo que significa
emparejando el carácter de fila y decolumna
– En vertical que significa insertando
uno o más gaps en la secuenciahorizontal (S1)
– En horizontal que representainsertar uno o más gaps en lasecuencia vertical (S2)
T C G C A
T
C
C
A s43
S2
S1
Calculo de la matriz de puntuaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 59/300
5959 /39/39
Calculo de la matriz de puntuaciones• Para llenar la matriz de
puntuaciones
– Consideramos todas las manerasde llegar hasta cada celda de lamatriz
– Nos quedamos con la(s) queconsiguen la puntuación más alta:
Puede haber más de una
T C G C A
T
C
C
A s43
S2
S1
Cálculo de la matriz de puntuaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 60/300
6060 /39/39
Cálculo de la matriz de puntuaciones
• La matriz de puntuaciones (Score Matrix ), P, se llena de arribaabajo y de izquierda a derecha mediante el siguiente
procedimiento1. Se llena la fila 0 y la columna cero con el coste de abrir un gap y
extenderlo tantos caracteres como posición en la fila (columna) seencuentre la celda
2. Se va llenando la matriz de izquierda a derecha y de arriba abajo. Encada celda se coloca la puntuación máxima resultante de considerar
todas las posibles maneras de acceder a aquella celda3. La direccion (o direcciones) que han dado lugar a la máxima
puntuación se anota por separado en la matriz de reconstrucción quese utilizará para reconstruir el alineamiento
Fórmulas de cálculo
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 61/300
6161 /39/39
Fórmulas de cálculo• Utilizamos la notación siguiente:
– S(i,j): Puntuación para coincidencia o no
– W k = a+b·k : Penalización afín para un “gap” de longitud k
• Con esta notación la puntuación de la fila y la columna 0:
– P(0,0)=0; P(0,k)=-W k, P(k,0)=-W k,
• Y la puntuación de cada celda de la tabla:
{ }{ }
−−−−
+−−
=−
≥
≥
columnaladeanterioresceldas,),(max
filaladeanterioresceldas,),(max
diagonalenanterior celda,),()1,1(
max),(
1
1
y y
x x
W y ji P
W j xi P
jiS ji P
ji P
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 62/300
6262 /39/39
Matriz de reconstrucción (Traceback)• Para reconstruir el alineamiento, al mismo tiempo que se llena la matriz
de puntuaciones, se llena la matriz de reconstrucción, T de la siguiente
forma: – T(i,j)=0 , si el máximo viene de la diagonal
– T(i,j)=+y , si el máximo viene de un desplazamiento vertical de y celdas. A
veces tan sólo se indica que viene de arriba (“↑”)
– T(i,j)=-x , si el máximo viene de un desplazamiento horizontal de x celdas. A
veces tan sólo se indica que viene de la izquierda (“←”)
• Si hay empate anotamos todos los valores iguales
R t ió d l li i t
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 63/300
6363 /39/39
Reconstrucción del alineamiento
• Para reconstruir el alineamiento se busca, en la matriz de
puntuaciones, la celda de la última fila o columna con la puntuaciónmás grande
• Se escoge la misma celda en la matriz de reconstrucción y se varetrocediendo según los valores indicados en ésta
• Este procedimiento puede dar más de un alineamiento óptimo
Ejemplo
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 64/300
6464 /39/39
Ejemplo
Smith-Waterman
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 65/300
6565 /39/39
Algoritmo de alineamiento local
0
0
0
0 0 0 0 0
..
..
P[i,0]= 0 ; per i= 0…m
a[0,j]= 0 ; per j= 0…n
Si el mejor alineamiento hasta un ciertopunto tiene un valor negativo esmejor empezar uno nuevo en lugar deextender el viejo
Matriz de puntuaciones:No se penalizan los gaps de
las bandas derecha y izquierda{ }
{ }
−−
−−
+−−
=−≥
≥
0
,),(max
,),(max
,),()1,1(
max),(
1
1
y y
x x
W y ji P
W j xi P
jiS ji P
ji P
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 66/300
6666 /39/39
Complementos
Nomenclatura para el estudio de
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 67/300
6767 /39/39
psecuencias de caracteres
• Cadena: Lista ordenada de caracteres de un alfabeto: GATTACA
• Prefijo: Caracteres consecutivos cogidos desde el inicio: G,GAT, GATTA,
• Sufijo: Caracteres consecutivos cogidos desde el final:
A,CA,TACA,...• Subcadena: Caracteres consecutivos desde los extremos o el
medio: GAT,TACA,ATTA...
• Subsecuencia: Caracteres ordenados no necesariamenteconsecutivos: GAAA,TTC,...
Ejemplo de programación dinámica
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 68/300
6868 /39/39
Ejemplo de programación dinámicaNúmeros de Fibonacci
Sub Fib(n, tab())
Dim j as integer
Redim tab(n)
tab[1] = 1tab[2] = 1;
for j = 3 to n
tab[j]=tab[j-1] + tab[j-2]
next jEnd Sub
Empecemos resolviendo los
problemas más sencillos
Utilicemos las soluciones parcialespara resolver problemas más
grandes
1
1
2
35
8
13
21
34
55
89
….
tab
Tornar
Gaps en el inicio del alineamiento
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 69/300
6969 /39/39
Gaps en el inicio del alineamiento
Si el dot-plot tiene este aspecto El alineamiento es:
A T C G A A T C G A
* * │ │ │C X ▬ ▬ C G A
G XA X
Si el dot-plot tiene este aspecto El alineamiento es:
G T C ▬ ▬ G C T
│ │ │
T * T A G C TA *G XT XC X
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 70/300
7070 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 71/300
7171 /39/39
Alineamiento de secuencias
Contenido
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 72/300
7272 /39/39
Contenido
1. Conceptos básicos
2. Métodos gráficos de alineamiento3. Puntuación de los alineamientos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 73/300
7373 /39/39
1. Conceptos básicos
Introducción
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 74/300
7474 /39/39
Introducción
• El alineamiento de secuencias es probablemente la
herramienta más utilizada en bioinformática• Su objetivo es alinear dos o más secuencias (de DNA oproteínas) de forma que puedan destacarse las regionessimilares entre las moléculas
• Al determinar si una secuencia desconocida es similar, enalgún sentido, a secuencias conocidas (e idealmente deestructura y función conocidas) podremos identificarla ypredecir su estructura y función
Aplicaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 75/300
7575 /39/39
Aplicaciones
• Mediante un alineamiento global entre genomas se puede
–identificar repeticiones internas (G1 vs G1) o – encontrar secuencias conservadas entre especies (G1 vsG2)
• Para predecir la función de una proteína desconocida suelebuscarse dominios funcionales comunes,
– mediante alineamientos locales entre dos secuencias – mediante alineamientos múltiples entre conjuntos de
secuencias
• Para buscar una secuencia en una base de datos para lo
que alinea por separado distintos fragmentos y se cuantificael grado de similitud alcanzado
• …
Métodos de alineamiento
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 76/300
7676 /39/39
Métodos de alineamiento
• Existen muchos programas disponibles en WWW para
alinear secuencias y buscarlas en las BD• Si se pretende que el resultado de dichos programas sea útilno deben ser “cajas negras”
• La correcta elección del programa ( método) y de sus
parámetros es muy importante – Una elección inadecuada puede conllevar la no detección desimilitudes relevantes
Visión global de los métodos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 77/300
7777 /39/39
Visión global de los métodos
• Alineamiento de dos secuencias
– Métodos gráficos: Dotplot . Es intuitivo, pero difícil decuantificar
– Algoritmos óptimos de alineamiento global (NW) o local(SW)
Obtienen el mejor alineamiento posible con programacióndinámica
Son demasiado exigentes para ser prácticos en búsquedasextensivas
• Alineamientos múltiples
• Algoritmos heurísticos para búsqueda en bases dedatos FASTA, BLAST
– Dan soluciones buenas, no necesariamente óptimas
– Pueden ser mucho más rápidos
Alineamiento de secuencias
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 78/300
7878 /39/39
Alineamiento de secuencias
• Es el procedimiento consistente en comparar dos (“ pairwise”)
o más (“multiple” ) secuencias buscando los caracteres opatrones que aparezcan en el mismo orden en lassecuencias
• Podemos distinguir entre alineamientos
– Globales: Alineamiento de secuencias completas – Locales : Alineamiento de subsecuencias
Ejemplos de alineamientos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 79/300
7979 /39/39
Ejemplos de alineamientos
2 Secuencias no alineadas
L G P S S K Q T G K G S S R I W D NL N I T K S A G K G A I M R L G D A
Alineam iento globalL G P S S K Q T G K G S ▬ S R I W D N
│ │ │ │ │ │ │L N ▬ I T K S A G K G A I M R L G D A
Alineam iento local▬ ▬ ▬ ▬ ▬ ▬ ▬ T G K G ▬ ▬ ▬ ▬ ▬ ▬ ▬ ▬
│ │ │
▬ ▬ ▬ ▬ ▬ ▬ ▬ A G K G ▬ ▬ ▬ ▬ ▬ ▬ ▬ ▬
Ejemplo de alineamiento múltiple
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 80/300
8080 /39/39
Ejemplo de alineamiento múltiple
I M A G I N A B L E
I M P R A C T I C A B LE
I L E G I B L E
I M▬ ▬
A G▬
I N A BL
EI M P R A C T I C A B L E
I N F ▬ A L ▬ I ▬ ▬ B L E
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 81/300
8181 /39/39
2. Métodos gráficos de alineamiento
Los Dotplots
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 82/300
8282 /39/39
Los Dotplots
• Se obtienen disponiendo dos secuencias S y T en losmárgenes horizontal y vertical de una tabla
• y marcando con una cruz (un punto) todas las posiciones enque coinciden los caracteres de S y T
– Si son idénticas se observa una diagonal definida
– Cuanto más diferentes sean, más difusa será – La aparición de patrones permite revelar estructuras en
las secuencias
Umbral de severidad (“Stringencyth h ld”)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 83/300
8383 /39/39
threshold”)• Para facilitar la visualización, se opta a menudo por mostrar
únicamente las diagonales formadas por un número mínimo
de puntos (umbral de severidad)
• Si el umbral de severidad es alto
– Eliminamos el ruido de fondo (“filtrado alto”)
– Solo detecta similitudes muy altas
• Si es bajo
– Hay ruido de fondo
– Detecta relaciones distantes
Ejemplo de dotplot 1: Una secuencia conll i
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 84/300
8484 /39/39
ella misma
Ejemplo de dotplot 2: Secuencias que handi id
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 85/300
8585 /39/39
divergido
Ejemplo de dotplot 3:I i “d l i ”
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 86/300
8686 /39/39
Inserciones y “deleciones”
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 87/300
8787 /39/39
3. Puntuación de los alineamientos
Sistemas de puntuación
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 88/300
8888 /39/39
p
• Para cuantificar la similitud entre dos cadenas, S y T, definimos sistemas de puntuaciones de forma que para cadaalineamiento se pueda calcular un número tal que, a mayor valor, mayor sea su significación (biológica)
• Pueden ser esquemas sencillos como por ej
– Coincidencia , S[i]=T[i] 1,
– No coincidencia, S[i]#T[i] 0,
– Inserción de espacios (gaps) -1,
• o bien sistemas más complejos basados en afinidades
químicas o en frecuencias de emparejamiento observadas
Puntuación de un alineamento
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 89/300
8989 /39/39
• Una vez establecido un sistema de puntuación la puntuación de una pareja de caracteres s,t alineados se define como p(s,t)
• La puntuación (score) de un alineamiento entre S i T :
• Un alineamiento es óptimo si su puntuación es la más
grande posible
( )∑∀ iiT iS p ][],[
Ejemplo
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 90/300
9090 /39/39
j p
S= A T G C A G T
T= A T A A G Tp(s,t) 1 1 0 0 0 0 Σ = 2
S= A T G C A G TT= A T A A ▬ G Tp(s,t) 1 1 0 0 -1 1 1 Σ = 3
S= A T G C A G TT= A T ▬ A A G Tp(s,t) 1 1 -1 0 1 1 1 Σ = 4
Ejemplo
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 91/300
9191 /39/39
j p
P untuac ión con esquem a s imple
S = T T Y G A P P W C S
T= − T G Y A P P P W S
p(s ,t) -1 1 0 0 1 1 1 0 0 1 Σ = 4
S = T T Y G A P P W C S
T= T G Y A P P P W S −p(s ,t) 1 0 1 0 0 1 1 1 0 -1 Σ = 4
El sentido de las puntuaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 92/300
9292 /39/39
p
• Los dos alineamientos del ejemplo anterior puntúan igual.Sin embargo
– a) conserva residuos comunes (A, P, S, T)
– b) conserva residuos menos habituales (W, Y)
• El sistema de puntuar los emparejamientos entre AA debería
reflejar su relación química y biológica – Residuos similares/distintos deberían puntuar alto/bajo
pues el cambiar uno por otro afectará poco/mucho lafunción de la proteína
Matrices de puntuación (scoring) o desubstitución (substitution)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 93/300
9393 /39/39
substitución (substitution)
• Una forma usual de definir el sistema de puntuación esutilizando una matriz de substitución
• Es una tabla que contiene las puntuaciones que asignamosa cada pareja posible de caracteres,
(sirve para las coincidencias y las no-coincidencias)
• El término “substitución” refleja que lo que se pretende alpuntuar un emparejamiento es valorar el coste evolutivo decambiar un residuo por otro
Matrices para alinear ADN
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 94/300
9494 /39/39
p
• Suele utilizarse una matriz identidad – P(i,i)=1, p (i,j)=0
o alguna variante de ésta – P(i,i)=0.9, p (i,j)=-0.1
Matrices para proteínas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 95/300
9595 /39/39
• No hay una matriz única que se pueda usar siempre
• Según la familia de proteínas y el grado de similitudesperado se usará una u otra
• Las más utilizadas PAM y BLOSUM
– PAM: Percent Accepted Mutation Matrix
• Derivadas de alineamientos globales de secuenciaspróximas
• PAM40 PAM250. A mayor nº mayor distanciaevolutiva
– BLOSUM• Derivadas de alineamientos locales de secuencias
distantes
• BLOSUM90 BLOSUM45 El nº representa porcentaje
de identifdad
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 96/300
9696 /39/39
Penalización por “gaps”
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 97/300
9797 /39/39
• En un sistema de puntuación es importante definir el costede insertar o eliminar un residuo, lo que en el alineamientoaparece como un hueco (“gap”)
• Suele penalizarse distinto – el primer hueco (“gap opening”)
– que los restantes (“gap extension”) que parten de él
• La variación de estos parámetros puede tener efectosimportantes en el alineamiento final
Efecto del valor de la penalización
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 98/300
9898 /39/39
Coste deapertura de
gap
Coste deextensión del
gapComentario
Grande Grande Pocas inserciones o eliminaciones
Bueno para proteínas muy relacionadas
Grande Pequeño Algunas inserciones grandes
Bueno si puede que se hayan insertadodominios completos
Pequeño Grande Muchas inserciones pequeñasBueno si se trata de proteínas distantes
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 99/300
9999 /39/39
4. Algoritmos de alineamiento óptimo
para pares de secuencias
Un algoritmo exhaustivo para obtener alineamientos óptimos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 100/300
100100 /39/39
alineamientos óptimos• Un algoritmo para obtener el alineamiento óptimo es:
– Construir todos los posibles alineamientos – Calcular la puntuación de cada uno
– El alineamiento óptimo es el que obtenga el valor másgrande (puede haber más de uno!)
• El número de alineamientos posibles es muy alto: Si S, T constan de unos 20 caracteres pueden hacer falta más de240 operaciones!!!
Una alternativa a la búsqueda exhaustiva:La programación dinámica (PD)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 101/300
101101 /39/39
La programación dinámica (PD)• La programación dinámica es una técnica de diseño de
algoritmos consistente en
– Considerar, en primer lugar, los casos más sencillos deun problema
– Resolverlos
– Combinarlos para obtener la solución de casos más
complicados – Hasta resolver el caso completo original
Veamos un ejemplo
Algoritmos de alineamiento óptimo
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 102/300
102102 /39/39
• Los dos más conocidos son
– Needleman y Wunsch (1970) para alineamientos globales – Smith y Waterman (1981), una variante para
alineamientos locales
• Sirven para alinear tanto DNA como proteínas
• Cada algoritmo retorna los alineamientos con la máximapuntuación posible para una matriz de substitución y un
coste de “gaps” dados
• El alineamiento obtenido no tiene necesariamente un
significado biológico
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 103/300
103103 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 104/300
104104 /39/39
2004
Bioinformática y Genómica
Fernán Agüero
Instituto de Investigaciones Biotecnológicas
Universidad Nacional de General San Martín
Un breve repaso histórico
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 105/300
105105 /39/39
• La aparición de las secuencias completas del genoma humano y cientos deotros genomas es el producto de un siglo de investigación dirigido acomprender la información genética.
• Comienzos del siglo XX: redescubrimiento de las leyes de Mendel
• Durante el primer cuarto de siglo, la biología descubrió que la base celular de lainformación eran los cromosomas
• Durante el segundo cuarto de siglo, se descubrió que la base molecular de la
información era el DNA• Durante el tercer cuarto de siglo, se definieron los mecanismos que utilizan las
células para leer esta información y se desarrollaron las herramientas de DNArecombinante
• Durante el ultimo cuarto de siglo, los biólogos se volcaron a colectar información genética - primero de genes, luego de genomas completos.
Información biológica
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 106/300
106106 /39/39
En que estamos hoy …
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 107/300
107107 /39/39
En que estamos hoy …
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 108/300
108108 /39/39
• El resultado: de ser una ciencia puramente experimental (con base en ellaboratorio) la biología está siendo transformada en una ciencia de lainformación
• La información acumulada no sólo es información genética (secuencias deDNA) – expresión de RNAs
– interacción entre proteínas
– estructuras tridimensionales
– Anulación sistemática de genes (knockouts, RNAi) que produce información defenotipos
– …
• Cada vez más diversos estudios comienzan con el análisis de bases de datospara luego formular hipótesis o diseñar experimentos
• Cada vez más el trabajo de laboratorio termina en la acumulación decolecciones masivas de datos que deben ser luego analizados
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 109/300
109109 /39/39
Paradigma central de la bioinformática
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 110/300
110110 /39/39
GeneticInformation
MolecularStructure
BiochemicalFunction
Symptoms(phenotype)
Genómica, Bioinformática y Medicina
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 111/300
111111 /39/39
Molecular Epidemiology
Molecular Diagnostics
Genomics
Bioinformatics
Identify Targets
Drug Design
Genetic Therapy
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 112/300
112112 /39/39
Información biológica en formatoelectrónico
Bases de datosFernán Agüero
Instituto de Investigaciones Biotecnológicas
UNSAM
conceptos básicos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 113/300
113113 /39/39
Qué es una base de datos? Una colección de datos
Cómo colecciono los datos? Decisión del usuario. Diseño dela base de datos.
Procesador de texto? (Word) Si. Permite sólo búsqueda yordenamiento simples.
Planilla de Cálculo? (Excel) También. Como los datos estánen columnas independientes, sepuede ordenar en formas máscomplejas. Las búsquedassiguen siendo simples.
Puedo usar:
Introducción: conceptos básicos: registros
U l ió d i t ( d )
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 114/300
114114 /39/39
• Una colección de registros (records).• Cada registro tiene varios campos.
• Cada campo contiene información específica.• Cada campo contiene datos de un tipo
determinado. – Ej: dinero,texto, números enteros, fechas, direcciones
• Cada registro tiene una clave primaria. Unidentificador único que define al registro sinambigüedad.
gi Accession version date Genbank Division taxid organims Number of Chromosomes
6226959 NM_000014 3 01/06/2000 PRI 9606 homo sapiens 22 diploid + X+Y
6226762 NM_000014 2 12/10/1999 PRI 9606 homo sapiens 22 diploid + X+Y
4557224 NM_000014 1 04/02/1999 PRI 9606 homo sapiens 22 diploid + X+Y
41 X63129 1 06/06/1996 MAM 9913 bos taurus 29+X+Y
Planilla
Versión simple deuna base de datos
Tipos de datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 115/300
115115 /39/39
• Cada campo de una base de datos contiene un tipo particular de datos – 021204
• Es un numero?• Es texto?
• Es una fecha?
• Ejemplo de una busqueda: buscar todos los registros en donde el valor almacenado sea mayor que 021204 – Es obvio que para poder comparar los valores almacenados tenemos que
saber qe tipo de valores estamos comparando. – Si es una fecha: 021204 (2.Dic.2004) > 211203 (21.Dic.2003)
– Si es un numero: 021203 < 211203
– Si es texto: 021203 ≠ 211203, las comparaciones < y > pueden dar distintos resultados (evaluan orden o longitud)
Tipos de datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 116/300
116116 /39/39
• Numericos (enteros, decimales)
•Texto• Fechas (DD/MM/YYYY, HH:MM:SS)
• Logicos (boolean) = verdadero / falso
• Geometricos (punto, linea, circulo, poligonos, etc.)
primariagi Accession version date Genbank Division taxid organims Number of Chromosomes
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 117/300
117117 /39/39
6226959 NM_000014 3 01/06/2000 PRI 9606 homo sapiens 22 diploid + X+Y
6226762 NM_000014 2 12/10/1999 PRI 9606 homo sapiens 22 diploid + X+Y
4557224 NM_000014 1 04/02/1999 PRI 9606 homo sapiens 22 diploid + X+Y
41 X63129 1 06/06/1996 MAM 9913 bos taurus 29+X+Y
gi = Genbank Identifier: Clave única : Clave primaria
Cambia con cada actualización del registro correspondiente a la secuencia
Accession Number: Clave secundaria
Refiere al mismo locus y secuencia, a pesar de los cambios en la secuencia.
Accession + Version es equivalente al gi (representa un identificador único)
Ejemplo: AF405321.2 Accession: AF405321 Version: 2
relacionalesgi Accession version date Genbank Division taxid organims Number of Chromosomes
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 118/300
118118 /39/39
6226959 NM_000014 3 01/06/2000 PRI 9606 homo sapiens 22 diploid + X+Y
6226762 NM_000014 2 12/10/1999 PRI 9606 homo sapiens 22 diploid + X+Y
4557224 NM_000014 1 04/02/1999 PRI 9606 homo sapiens 22 diploid + X+Y
41 X63129 1 06/06/1996 MAM 9913 bos taurus 29+X+Y
gi Accession version date Genbank Division taxid
6226959 NM_000014 3 01/06/2000 PRI 9606
6226762 NM_000014 2 12/10/1999 PRI 9606
4557224 NM_000014 1 04/02/1999 PRI 9606
41 X63129 1 06/06/1996MAM 9913
taxid organims Number of Chromosomes
9606 homo sapiens 22 diploid + X+Y
9913 bos taurus 29+X+Y
Base de datos relacional:
Normalizar una base de datos para sub-elementos repetidos,repartiendola en bases de datos menores, relacionadas a través de unidentificador único (clave primaria).
informacion
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 119/300
119119 /39/39
Lutzomyia cruzi cytochrome b; best similarity to gi|12345685696
Sarcocystis cruzi 16SRNA gene5695
Candida albicans hypothetical protein in region 21922..245685694
Trypanosoma cruzi chromosome 3, ORF 1234, similar to gi|12345|
AF934567 caseine kinase (Candida albicans)
5693
annotationgi
1234568Cytochrome bLutzomyia cruzi5696
78651216S RNA geneSarcocystis cruzi5695
Hypothetical protein in region 21922..24568Candida albicans5694
12345Chromosome 3, ORF 1234Trypanosoma cruzi5693
similar to AnnotationOrganismgi
índices
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 120/300
120120 /39/39
• Para facilitar las búsquedas en una base de datos, seconstruyen índices.
• Un índice es una lista de claves primarias asociadas a undeterminado campo (o grupo de campos)
Genbank divPRI 6226959;6226762;4557224;É
MAM 41;É AccessionNM_000014 6226959;6226762;4557224;X63129 41;
gi Accession version date Genbank Division taxid organims Number of Chromosomes
6226959 NM_000014 3 01/06/2000 PRI 9606 homo sapiens 22 diploid + X+Y
6226762 NM_000014 2 12/10/1999 PRI 9606 homo sapiens 22 diploid + X+Y
4557224 NM_000014 1 04/02/1999 PRI 9606 homo sapiens 22 diploid + X+Y
41 X63129 1 06/06/1996 MAM 9913 bos taurus 29+X+Y
Indices (cont)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 121/300
121121 /39/39
• Un ejemplo más complejo: buscar todos los records quecontengan la palabra ‘kinase’ en la descripción de la
secuencia
gi acc def
214734 L07770 Xenopus laevis rhodopsin mRNA, complete cds.
123456 AF43567 Mus musculus casein kinase mRNA, partial cds.
•Indexar la columna ‘def’
word list of GIs
casein 1234,3245,43678,123456 ...
kinase 432,5678,32456,123456 ...
laevis 36314,214734, ...
mus 23467,98732,123456,312456,567983 ...musculus 23467,98732,123456,567983 ...
rhodopsin 214734,223466,873212,23587,2942,12932 ...
xenopus 28462,36314,98476,214734 ...
Indexar es costoso
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 122/300
122122 /39/39
• El proceso de indexación es costoso en términos computacionales,pero se realiza una única vez (en realidad cada vez que se actualizan
los datos)
• Desde el punto de vista de la base de datos, los índices no son otracosa que nuevas tablas relacionadas con la tabla que contiene elcampo indexado
• Ejemplo más obvio: buscadores de páginas de internet (Google, Altavista). Visitan páginas e indexan los términos que encuentran
– kewyword: url1, url2, url3, url4, etc.
indexadas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 123/300
123123 /39/39
• Buscadores de páginas en internet
• PubMed / Entrez / SRS
• BLAST
Importante: no se busca en el total de los datos disponibles, sino sobreun subset pre-computado.
Schemas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 124/300
124124 /39/39
• La distribución de los datos en campos dentro de una tabla y de lasrelaciones entre tablas y sus campos es lo que se llama el diseño o
schema
Schemas (cont)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 125/300
125125 /39/39
RDBMS
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 126/300
126126 /39/39
• Relational Database Management Systems – Comerciales
• Oracle, Sybase
– Open source, gratuitos
• PostgreSQL, MySQL
• Todos usan SQL (standard query language) para – crear tablas, índices, etc.
– ingresar datos
– consultar
Búsquedas simples
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 127/300
127127 /39/39
• Los motores de búsqueda ofrecen búsquedas simples
• No imponen restricciones
• El usuario tipea palabras libremente
• Usan estrategias para intentar “adivinar” la intención delusuario (sobre qué campo de la base de datos buscar)
Ejemplo: term mapping - Entrez (PubMed)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 128/300
128128 /39/39
• Entrez busca en una serie de listas para ver si la palabra queingresaron se encuentra en alguna
• MeSH (Medical Subject Headings): vocabulario controlado utilizado para
indexar artículos en PubMed.
• Journals: nombre completo del journal, abreviaturas usadas en MEDLINE y
números ISSN.
• Lista de frases: cientos de miles de frases generadas a partir de MeSH y otros
vocabularios controlados similares.
• Indice de autores: apellido e iniciales.
• Stopwords: palabras comunes, presentes en casi todos los registros de la base
de datos (a, an, by, of, the … )
Búsquedas simples: pros / cons
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 129/300
129129 /39/39
• Ventajas
– rápidas de formular
– no hay que leer el manual
– ni hacer un curso
• Desventajas
– poco selectivas
Búsquedas avanzadasP i t i i t b l i ió
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 130/300
130130 /39/39
• Presuponen un cierto conocimiento sobre la organizaciónsubyacente de los datos
• Hay que especificar sobre qué campos buscar:
⇒hay que conocer los campos
• Entrez: se especifican entre corchetes
• Tags predefinidos (hay que conocerlos)– Escherichia coli[organism]
–review[publication type]
– attenuator[feature key]
• SRS: formulario avanzado (no hay que conocer términos otags)
Búsquedas avanzadas: Entrez
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 131/300
131131 /39/39
• Entrez provee además
– Límites: especie de formulario avanzado que les
permite limitar la búsqueda a un campo determinado,
sin tener que conocer los tags)
– History: una historia de las búsquedas que van
realizando. En cualquier momento pueden combinar
búsquedas o volver sobre alguna de ellas
– Preview/Index: les permite probar una búsqueda
(preview) y ver el número de registros que selecciona
o ver los índices y el número de registros asociados a
cada uno de ellos – Details: permite analizar la traducción que realizó
Entrez de la búsqueda que realizamos (uso de
sinónimos, límites, etc)
Operadores lógicos
E bú d i l d i i
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 132/300
132132 /39/39
• En búsquedas simples o avanzadas siempre tienen adisposición operadores lógicos para encadenar términos
• AND (unión) – human AND genome
– +human +genome
– human && genome
• OR (intersección) – human OR genome
– human || genome
• NOT (subconjunto)
– human NOT genome
Orden de los términos en un query
El d d l té i i t t
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 133/300
133133 /39/39
• El orden de los términos es importante
• Un query se evalúa de izquierda a derecha – human NOT genome no es lo mismo que genome NOT human
• Si el query tiene muchos términos pueden forzar el orden deevaluación usando paréntesis – human AND cancer AND (cell OR science OR nature)
– casein kinase NOT (human OR mouse)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 134/300
134134 /39/39
Bases de datos biológicas: DNA• Nucleotide databases:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 135/300
135135 /39/39
Nucleotide databases:
– Genbank: International Collaboration• NCBI (USA), EMBL (Europe), DDBJ (Japan and Asia)
– Organism specific databases
• FlyBase
• ChickBASE
• pigbase
• SGD (Saccharomyces Genome Database)
Bases de datos biológicas: proteínas• Protein Databases:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 136/300
136136 /39/39
– NCBI:• Genpept: Translated Proteins from Genbank Submissions
– EMBL
• TrEMBL: Translated Proteins from EMBL Database
– SwissProt:
• recibe secuencias peptídicas
• cura y anota secuencias provenientes de TrEMBL
(Gratuita para uso académico. Restricciones sobre los
descubrimientos hechos utilizando la base de datos. La
versión de 1998 es gratuita y libre de todas las restricciones.)
• http://www.expasy.ch (última versión no-gratuita)
• NCBI tiene la última versión gratuita.
Bases de datos biológicas: estructura• Structure databases:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 137/300
137137 /39/39
– PDB: Protein structure database.• http://www.rscb.org/pdb/
– MMDB: NCBI’s version of PDB with entrez links.• http://www.ncbi.nlm.nih.gov
– SCOP: structural classification of proteins• family, superfamily, fold
– CATH: structural classification of proteins• class, architecture, topology, homology
– FSSP: fold classification based on structure-structure alignment
• Genome Mapping Information: – http://www.il-st-acad-sci.org/health/genebase.html
–NCBI(Human) – Genome Centers:
• Stanford, Washington University, UCSC
– Research Centers and Universities
Bases de datos biológicas: literatura• Literature databases:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 138/300
138138
/39/39
Literature databases:
– NCBI: Pubmed: All biomedical literature.• www.ncbi.nlm.nih.gov
• Abstracts and links to publisher sites for – full text retrieval/ordering
– journal browsing.
– Publisher web sites.
• Pathways Database: – KEGG: Kyoto Encyclopedia of Genes and Genomes:
www.genome.ad.jp/kegg/kegg/html
Bases de datos biológicas: GenBank• Es un Banco: no se intenta unificar datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 139/300
139139
/39/39
Es un Banco: no se intenta unificar datos. – No se pueden modificar las secuencias sin el consentimiento del
autor (submitter). – No se intenta unificar (puede haber más de una secuencia para
un locus/gen).
– Puede haber registros de diversas calidades de secuencia ydiferentes fuentes ==> Se separan en varias divisiones de
acuerdo a:• Secuencias de alta calidad en divisiones taxonómicas.
– PRI -> Primates
– MAM -> Mamíferos
– INV -> Invertebrados
• Secuencias de baja calidad en divisiones uso-específicas. – GSS -> Genome Sequence Survey
– EST -> Expressed Sequence Tags
– HTG -> High Troughput Sequencing (unfinished contigs, BACs,cosmids, chromosomes).
GenBank
• Redundante
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 140/300
140140
/39/39
• Redundante
• Con errores
• Dificil de actualizar
• Para poder corregir, mejorar y mantener actualizada la
anotación de los registros, el NCBI creó RefSeq (coleccióncurada de registros de GenBank) – toma records de GenBank y los actualiza/corrije
– unifica para reducir redundancia
– Accession numbers del tipo XX_123456
Bases de datos primarias• Una base de datos primaria es un repositorio de datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 141/300
141141
/39/39
p pderivados de un experimento o de conocimiento
científico.
– Genbank (Repositorio de secuencias nucleotídicas)
– Protein DB, Swissprot
– PDB – Pubmed (literatura)
– Genome Mapping
– Kegg (Kyoto Encyclopedia of Genes and Genomes, base
de datos de vías metabólicas)
Bases de datos secundarias• Una base de datos secundaria contiene información
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 142/300
142142 /39/39
Una base de datos secundaria contiene informaciónderivada de otras fuentes (primarias, entre otras).
– Refseq (Colección curada de GenBank en NCBI) – Unigene (Clustering de ESTs en NCBI)
• Las bases de datos organismo específicas son en
general una mezcla entre primaria y secundaria.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 143/300
143143 /39/39
Análisis y anotación de genomas
Fernán Agüero
Historia• Primer proyecto de secuenciación de un genoma:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 144/300
144144 /39/39
Primer proyecto de secuenciación de un genoma:Escherichia coli (US + Japón). Comenzó en 1992 y
terminó en 1997. 4.6 MB• Primer genoma (eubacteria): Haemophilus influenzae
(1995). 1.83 MB
• Primer genoma (archaea): Metanococcus jannaschii
(1996). 1.6 MB
Qué es un genoma?
• Una colección de
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 145/300
145145 /39/39
• Una colección de – genes
• que codifican productos proteicos
• que codifican RNAs
– pseudogenes
– regiones no codificantes
• regulatorias (expresión)
• estructurales
– attachment a matriz nuclear
– mitosis / meiosis
– elementos repetitivos
Qué es anotar?
• Agregar información de la manera más
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 146/300
146146 /39/39
• Agregar información, de la manera más
confiable y actualizada que se pueda paradescribir una secuencia
• Información asociada a coordenadas
genómicas (comienzo..fin), a distintosniveles
• Interpretar la información cruda de secuencia
en un marco biológico
Anotación genómica
D i l d t ió
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 147/300
147147 /39/39
• Dos niveles de anotación
– Estructural: encontrar genes y otros sitios conrelevancia biológica. Armar un modelo del genoma:
cada gen/sitio es un objecto asociado a una posición
en el genoma
– Funcional: los objetos son utilizados en búsquedas (y
experimentos). El objetivo es atribuir información
biológica relevante a los objetos.
Más niveles de anotación
• Organismo: fenotipo: morfología fisiología
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 148/300
148148 /39/39
• Organismo: fenotipo: morfología, fisiología,
comportamiento, respuestas ambientales
• Celula: vías metabólicas, cascadas de señalización,
localización subcelular.
• Molecula: sitios de binding, actividad catalítica,
estructura tridimensional
• Dominio
• Motif
• Residuo
De donde proviene la anotación?
• Fuentes utilizadas en la anotación:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 149/300
149149 /39/39
• Fuentes utilizadas en la anotación:
– publicaciones que reportan nuevas secuencias
– reviews que actualizan periódicamente la anotación de familias o
grupos de proteínas
– expertos externos
– análisis de secuencia
Anotación genómica
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 150/300
150150 /39/39
transcription
RNA processing
translation
AAAAAAA
Genomic DNA
Unprocessed RNA
Mature mRNA
Nascent polypeptide
folding
Reactant A Product BFunction
Active enzyme
ab initio gene
prediction
Functionalidentification
Gm3
Comparative gene
prediction
Annotation & functional genomicsLa anotación del genoma es esencial en el desarrollo deestrategias funcionales (functional genomics)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 151/300
151151 /39/39
GeneKnockout
Expression Microarray
RNAi phenotypes
proteome based functional genomics
estrategias funcionales (functional genomics)
Anotación: busqueda de genes• Buscar genes en el genoma
– RNA
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 152/300
152152 /39/39
RNA
• ribosomal RNAs ⇒BLASTN
• tRNAs ⇒tRNAscan – protein coding
• ab initio gene prediction⇒ORFs, codon usage, frecuencia dehexámeros, modelos, etc.)
• similarity ⇒BLASTX, otros
• Buscar regiones no codificantes
– regulatorias
• ab initio ⇒Gibbs sampling
• similarity ⇒patterns, profiles
– repetitivas
• similarity
• ab initio
• En todos los casos ⇒ literatura!
Integrar resultados
BLASTX
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 153/300
153153 /39/39
Secuenciagenoma
BLASTX
BLASTN
RepeatMasker
tRNASCan
gene prediction
DB
flatfiles
Visualización
Genome annotation: C. elegans
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 154/300
154154 /39/39
Resumir resultados de análisis• Guardar el reporte crudo de un BLAST (lista de hits,
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 155/300
155155 /39/39
p (alineamientos) es demasiado
• Prácticamente cualquiera de los análisis que se realizansobre DNA o proteínas para anotar un genoma puedenresumirse en:– secuencia start end
– cromosoma1 1723 3456
• Este formato básico es la base del formato GFF (Sanger)
secuencia metodo programa start end frame score extra
Contig1 similarity blastx 100 1000 +1 132 gi|12345|AF34093 casein kinase ...
Contig1 cds glimmer 85 1201 +1 1321 ORF0001; overlap with ORF0002
Contig1 similarity blastn 80 1300 . 136 gi|54321|AF09990 complete genome
Anotación: herramientas
• Artemis
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 156/300
156156 /39/39
Artemis – http://www.sanger.ac.uk/Software/Artemis
– Permite visualizar
• secuencia, con sus traducciones virtuales (6)
• tracks de anotación (entries)
• plots (built-ins y creados por el usuario)
– Lee secuencias en formato FASTA, EMBL, GenBank
– Lee features en formato EMBL, GenBank, GFF, MSPcrunch,BLAST
Artemis: main window
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 157/300
157157 /39/39
Feature list
Sequence view
Sequence view
Artemis: plots
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 158/300
158158 /39/39
%GC plot
AA propertiesplot para unCDS
Artemis: display de análisis
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 159/300
159159 /39/39
Frameplot
BLASTX
BLASTN
Artemis:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 160/300
160160 /39/39
Artemis: zoom
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 161/300
161161 /39/39
Artemis: spliced genes
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 162/300
162162 /39/39
Artemis: comparar análisis
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 163/300
163163 /39/39
ACT: Artemis Comparison Tool
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 164/300
164164 /39/39
Nature Genetics 35 (2003)
Comparative analysis of the genome
sequences of Bordetella pertussis,
Bordetella parapertussis and
Bordetella bronchiseptica.
ACT: Artemis Comparison Tool
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 165/300
165165 /39/39
Otras estrategias
• Artemis se usa para anotar genomas bacterianos o para
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 166/300
166166 /39/39
pequeños proyectos (cósmidos, BACs, etc.)
• En genomas más grandes, la tendencia es a distribuir laanotación
• Los tracks de anotación son generados en distintos centros
• Ejemplo: UCSC Genome Browser (genoma humano, ratón).
Anotación automática: TrEMBL
• La anotación de TrEMBL (translated EMBL) se hace por
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 167/300
167167 /39/39
( ) p
métodos automáticos.
– Requerimientos para anotar automáticamente
• Una base de datos de referencia bien anotada (ej. Swissprot)
• Una base de datos que sea altamente confiable (en el sentido
diagnóstico) en la asignación de proteínas a grupos o familias (ej CDD,
InterPro)
• Una serie de reglas de anotación
Transferencia directa de anotación
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 168/300
168168 /39/39
• Realizar una búsqueda en la
base de datos de referencia ytransferir la anotación
• Ejemplo: FASTA contra una
base de datos desecuencias y transferencia
de la línea DE del mejor hitTargetTarget
XDBXDB
Anotación a partir de múltiples fuentes
G l t
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 169/300
169169 /39/39
• Generalmente se usa
más de una base dedatos externa
• Hay que combinar los
resultados
TargetTarget
XDBXDB
Conflictos
• Contradicción
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 170/300
170170 /39/39
• Inconsistencia• Sinónimos
• Redundancia
Traducción de anotaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 171/300
171171 /39/39
• Es necesario utilizar un traductor para
mapear el lenguaje utilizado en labase de datos externa (XDB) allenguaje utilizado en la base de datostarget que queremos anotar
TargetTarget
XDBXDB
Traducciones: algunos ejemplos
ENZYME→ TrEMBL
CA L ALANINE D ALANINE
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 172/300
172172 /39/39
CA L-ALANINE=D-ALANINE
CC -!- CATALYTIC ACTIVITY: L-ALANINE=CC D-ALANINE.
PROSITE→ TrEMBL
/SITE=3,heme_iron
FT METAL IRON
Pfam→ TrEMBL
FT DOMAIN zf_C3HC4FT ZN_FING C3HC4-TYPE
equer m en os e un s s ema e ano ac nautomática
• Corrección
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 173/300
173173 /39/39
• Escalable
• Actualizable
• Poco redundante
• Completo
• Vocabulario controlado
Cómo funciona?
• Una proteína en TrEMBL es reconocida como un miembro
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 174/300
174174 /39/39
de cierto grupo o familia de proteínas
• Este grupo de proteínas en Swissprot comparten entre sí
partes de la anotación
• La anotación común es transferida automáticamente a la
proteína en TrEMBL y marcada como ‘annotated by
similarity’
Anotación: evidencias• Las anotaciones suelen estar acompañadas de TAGS que indican la
evidencia en la que se basa la anotación
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 175/300
175175 /39/39
q
• Ejemplos de algunos TAGS utilizados en TrEMBL:
– EMBL: la información fue copiada del original(EMBL/GenBank/DDBJ)
– TrEMBL: anotación modificada para corregir errores o paraadecuarse a la sintaxis propia de Swissprot
– Curator: juicio del curador– Similarity: por similitud con otra secuencia, a juicio del
curador
– Experimental: evidencia experimental de acuerdo a unareferencia, que usualmente es un paper.
– Opinion: opinión emitida por el autor de una referencia,usualmente con poca o ninguna evidencia experimental
– Rulebase: información derivada del uso de una regla deanotación automática
– SignalP: programa de predicción
Anotación: manual vs automática
• La anotación de un genoma ocurre en etapas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 176/300
176176 /39/39
– anotación automática
• correr todos los análisis sobre el genoma• generar un primer borrador con todos los datos organizados. Por
ejemplo en páginas web o integrando todos los datos en un displayunificado (Artemis)
– anotación manual: cura de los datos
• una persona (curador) revisa la anotación, gen por gen, verificando laanotación automática, agregando anotaciones manuales, corriendoeventualmente algún programa particular
Qué herramientas se usan?
• Oakridge Genome Annotation Channel
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 177/300
177177 /39/39
– http://compbio.ornl.gov/channel
• ENSEMBL – http://ensembl.ebi.ac.uk
• Artemis – http://www.sanger.ac.uk/Software/Artemis
• GeneQuiz – http://www.sander.ebi.ac.uk/genequiz
• Genome browsers: varios – cada consorcio/proyecto desarrolló el suyo: Apollo (FlyBase,
Drosophila), AceDB (C. elegans),
Anotación: fuentes de error
• Transferencia transitiva de anotaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 178/300
178178 /39/39
– gen1 mal anotado como ‘casein kinase’ presente en los bancos de
datos – gen2 con alta similitud con gen1, resulta anotado como casein
kinase
• Solución: – usar bases de datos curadas: por ejemplo Swissprot
– revisar la anotación de más de un hit
– verificar que las anotaciones de todos los hits concuerden
Anotación confiable: proyecto HAMAP
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 179/300
179179 /39/39
• High-quality Automated Microbial Annotation ofProteomes– Swissprot (Swiss Bioinformatics Institute-European
Bioinformatics Institute)
– CNRS Lyon
– INRIA Grenoble– INRA Toulouse
– CNRS Marseille
– Pasteur Institute
HAMAP
• Hay muchos genomas bacterianos terminados, pero va a haber
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 180/300
180180 /39/39
muchos más en los próximos años
• El número de proteínas bacterianas proveniente de estosgenomas llegará al millón muy rápidamente
•Pero el análisis funcional y una caracterización detallada van aexsitir sólo en unos pocos casos:
– todas las proteínas de organismos modelo (E. coli, B.
subtilis)
– proteínas involucradas en patogénesis (interés médico e
industrial)– proteínas involucradas en vías metabólicas específicas
(interés biotecnológico)
Prioridades del proyecto HAMAP
• Anotación de proteínas huérfanas
ó í
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 181/300
181181 /39/39
• Pre-anotación de proteínas pertenecientes a familias
grandes/complejas (transportadores ABC, HTH, sistemasde dos componentes, SDH)
• Anotación de alta calidad de proteínas pertenecientes afamilias bien caracterizadas
• Anotación manual de proteínas caracterizadasexperimentalmente en ese organismo
• Anotación manual de proteínas no caracterizadas quemuestren similitud con otras proteínas
Estrategia HAMAP
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 182/300
182182 /39/39
ORFans
HAMAP: ORFans
• No tienen similitud con otras proteínas (excepto tal vezotras proteínas de organismos muy cercanos)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 183/300
183183 /39/39
otras proteínas de organismos muy cercanos)
• No tienen hits contra InterPro (Prosite, PRINTS, Pfam,ProDom, SMART)
• Qué se hace:– Predicción de señales
– Predicción de regiones trans-membrana
– Predicción de coiled-coils
– Anotación de repeticiones
HAMAP: ORFan antes
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 184/300
184184 /39/39
HAMAP: ORFan después
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 185/300
185185 /39/39
HAMAP: large/complex families
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 186/300
186186 /39/39
HAMAP: anotación automática
• Transferencia automática de anotaciónUsando reglas específicas para cada famila de proteínas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 187/300
187187 /39/39
– Usando reglas específicas para cada famila de proteínas
– Usando reglas específicas para un organismo particular
• La transferencia de anotación puede ir acompañada deadvertencias para el curador
– Por ejemplo:• WARNING: this genome contains MF_00031 (ruvA) but not MF_00016
(ruvB)
HAMAP: ejemplo reglas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 188/300
188188 /39/39
HAMAP: Escherichia coli
• De acuerdo al análisis original: 4286 proteínas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 189/300
189189 /39/39
– 60 proteínas no detectadas (casi todas < 100 aa)
– 120 muy probablemente no existan
– 50 pares o tripletes de ORFs tuvieron que ser fusionados
– 719 con errores en la asignación del codón de inicio
– ~1800 todavía sin caracterización bioquímica (aproximadamenteuna asignación funcional por semana)
Chromosome browsers• UCSC Genome Browser
– provee un display rápido de cualquier región genómica
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 190/300
190190 /39/39
provee un display rápido de cualquier región genómica
– con varios “tracks” de anotación alineados al genoma – Por el momento sólo: Human & Mouse
• Annotation tracks – genes conocidos (RefSeq, GenBank)
– predicted genes (Genscan, FGENESH, GeneID, Acembly) – spliced ESTs
– CpG islands
– assembly gaps
– cobertura
– bandas cromosómicas
– elementos repetitivos
– etc
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 191/300
191191 /39/39
UCSC Genome browser • UCSC sólo genera la mitad de los tracks
• El resto proviene de la comunidad biomédica
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 192/300
192192 /39/39
El resto proviene de la comunidad biomédica
• El Genome Browser es una herramienta de visualización
• No saca conclusiones! Simplemente integra en formagráfica toda la información que posee sobre una región,
dejando la exploración y la interpretación al usuario.
UCSC Genome Browser: gene expression
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 193/300
193193 /39/39
splicing
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 194/300
194194 /39/39
transcription
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 195/300
195195 /39/39
UCSC Genoma browser: user tracks• Ustedes pueden agregar sus propios tracks
• Pueden ser públicos o privados
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 196/300
196196 /39/39
Pueden ser públicos o privados
• No necesitan saber programar • Tienen que proveer información en formato GFF (u otros
similares: GTF, BED)
chrom start end [name strand score]
chr1 1302347 1302357 SP1 + 800
chr1 1504778 1504787 SP2 – 980
Acknowledgements• Nicola Mulder, EBI
• Daniel Lawson Sanger Centre
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 197/300
197197 /39/39
• Daniel Lawson, Sanger Centre
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 198/300
198198 /39/39
2004
BioinformáticaHerramientas y aplicaciones
Fernán Agüero
Instituto de Investigaciones Biotecnológicas
Universidad Nacional de General San Martín
Entender la información genética• La información genética es redundante
• La información estructural es redundante
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 199/300
199199 /39/39
La información estructural es redundante
• Un gen, muchas funciones
• La información genética es unidimensional, pero la funcióndepende de la estructura tridimensional
• El reemplazo de 40% de los residuos de una proteína no
afectan la función
u erram en as provee a compu ac ncientífica
• Machine Learning (inteligencia artificial, aprendizajeautomático)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 200/300
200200 /39/39
)
– Distintos métodos ‘entrenables’ para reconocer o aprender disintascosas:
• Neural Networks
• Markov Models and Hidden Markov Models
• Nearest neighbor • Otros
– Predicción en proteínas
• SignalP, Net-O-Glyc, TMHMM, TmPred, PSORT
– Gene finding, Gene prediction
• Genscan, Glimmer, GeneMark, FGENESH
– Predicción de estructura secundaria
• nnpredict, PHDSec,
Qué herramientas provee la computación• Bases de datos
– Organizar datos de manera eficiente
– Posibilidad de realizar consultas complejas integrando y cruzando datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 201/300
201201 /39/39
Posibilidad de realizar consultas complejas, integrando y cruzando datos.
• Entrez, SRS, FlyBase• Oracle, Sybase, MySQL, PostgreSQL
• Teoría de la información – Medir la cantidad de información (en bits)
– Incertidumbre
• Sequence Logos
• Algoritmos – Métodos para tratar con distintos tipos de problemas
– Una vez que se aprende como solucionar un problema particular, la solución segeneraliza a toda una clase de problemas similares
• Dynamic programming Qué problema resuelve este algoritmo? El problema de encontrar elmejor camino entre muchos posibles.
• utilizado en métodos de alineamiento de secuencias (Smith-Waterman, Needleman-Wunsch,BLAST, FASTA), en métodos de predicción de genes, en ruteo de llamadas telefónicas através de distintas centrales, etc.
Bases de datos: conceptos básicosQué es una base de datos? Una colección de datos
Có l i l d t ? D i ió d l i Di ñ d l
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 202/300
202202 /39/39
Cómo colecciono los datos? Decisión del usuario. Diseño de la
base de datos.
Procesador de texto? (Word) Si. Permite sólo búsqueda y
ordenamiento simples.
Planilla de Cálculo? (Excel) También. Como los datos están encolumnas independientes, se puedeordenar en formas más complejas.Las búsquedas siguen siendo
simples.
Puedo usar:
Un sistema de manejo de base de datos
(Database Management System, DMS)
Ideal. Permite representar los datosen formas complejas. Flexible parareordenar y buscar con distintoscriterios
Un experimento bioinformático• Un experimento en la computadora no es distinto de cualquier
experimento en la mesada: – los resultados deben contestar una pregunta concreta
– deben ser reproducibles por otra persona que utilice el mismo método
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 203/300
203203 /39/39
• Identificar el problema – cuál es el mecanismo catalítico de la enzima X?
• Identificar las herramientas necesarias para resolver el problema – búsquedas de secuencias similares, alineamientos múltiples, detección de
profiles y motivos, modelado de la estructura tridimensional, evaluación delmodelo
• Definir criterios de satisfacción (éxito del experimento) – Prácticamente todos los métodos computacionales producen resultados. Una
búsqueda utilizando BLAST casi siempre produce algún hit
– Es necesario distinguir resultados significativos del ruido para no terminar comparando superoxido dismutasas con alcohol dehidrogenasas.
– Hay que entender cómo funcionan los programas, en qué algoritmos estánbasados, que puntos débiles tienen, etc.
Un experimento bioinformático …• Seleccionar el set de datos apropiados
– En el laboratorio, los materiales y reactivos son objetos físicos necesariosli i t G l t b d f
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 204/300
204204 /39/39
para realizar un experimento. Generalmente uno sabe cuando fueron
preparados, quien los preparo, como fueron preparados, etc.
– En bioinformática el mismo tipo de información es esencial. Las fuentes deinformación (bases de datos, por ej), fecha de ultima actualizacion, elcrtiterio y el metodo utilizado para extraer los datos que van a ser utilizadosen el experimento
El costo de un proyecto bioinformático es bajo
una vez que cubierto el gasto inicial en computadoras(y eventualmente software)
Un ejemplo concreto• Un investigador interesado en estudiar genes en involucrados en la interacción
hospedador-parásito, con especial interés en identificar aquellos productos que seansecretados
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 205/300
205205 /39/39
• Un sitio web reporta los resultados de un análisis sistemático de expresión (usandomicroarrays) de todos los genes del genoma en todos los estadíos del ciclo de vida delparásito
• El investigador puede bajar un archivo con un resumen de estos experimentos
• Las secuencias de todas las proteínas codificadas por el genoma se encuentrandisponibles en una base de datos.
• Lo que se necesita es contar con la capacidad de identificar genes que se expresen enlos estadíos del ciclo de vida que ocurren en el hospedador y extraer las secuencias deestos genes de la base de datos
• En ultima instancia el objetivo es analizar las secuencias de interés usando SignalP parapredecir la posible presencia de un péptido señal
Cuestiones a tener en cuenta:• Podemos hacer el trabajo ‘a mano’
– Abrimos el resumen con los datos de los experimentos con microarrays en unprocesador de texto
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 206/300
206206 /39/39
– buscamos los genes que muestran expresión en el estadio de interés – Construimos una lista de genes (accession numbers)
– Luego vamos a nuestra base de datos con secuencias genómicas y sus traduccionesy buscamos una por una las secuencias
– El ultimo paso es pasar todas las secuencias a un formato que entienda SignalP yingresarlas una por una en el formulario correspondiente.
• Hay tres problemas evidentes: – Si el número de genes que se expresan en nuestro estadio de interes es más que
‘unos cuantos’ el trabajo se vuelve tedioso y más que nada lento por el tiempo queinsume
– Peor aun, cada vez que aparezcan nuevos resultados de microarrays o seactualicen, hay que repetir todo el procedimiento
– El proceso de abrir el resumen con datos de microarrays (o la base de datos degenes) en un procesador de textos puede no ser factible si el tamaño de los archivosexcede los 5 o 10 MB
Programación en biología• Cualquier persona que tenga experiencia en el diseño y llevado a cabo de
experimentos para responder una pregunta puede programar una computadora
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 207/300
207207 /39/39
• Un experimento en el laboratorio comienza con una pregunta que evolucionahacia una hipótesis testeable
• Finalmente el experimento sirve para afirmar o descartar una afirmación
• En la computadora el programa que uno escriba debe estar diseñado demanera de producir resultados que respondan a este tipo de afirmaciones
• Aprender un lenguaje de programación puede resultar un desafío no trivial,pero es similar a aprender a utilizar una nueva herramienta, tecnología u otrolenguaje (inglés, francés)
Programación en biología• Ejemplos simples:
– automatizar tareas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 208/300
208208 /39/39
– identificar una o más tareas que uno quiere realizar
– escribir un programa que las realice en forma automática
• Analizar todas las proteínas de un genoma y seleccionar aquellas quesean (o parezcan) proteinasas
– Un archivo con todas las secuencias – Una base de datos de proteinas (Swissprot, GenPept)
– Un programa para buscar secuencias similares en bases de datos (BLAST)
– Una serie de instrucciones a seguir (un protocolo)
Automatizar búsquedas con BLAST
Secuencias
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 209/300
209209 /39/39
BLAST
Significativo?
Es una proteinasa? Guardar
NO
NO
SI
SI
Automatizar BLAST• Muy lindo el diagrama, pero: cómo se hace?
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 210/300
210210 /39/39
• Por cada secuencia de una lista de secuencias hay que: – correr la comparación (BLAST) contra una base de datos
– analizar el reporte que genera el programa y extraer dos tipos dedatos:
• score, expect, identidad, similitud (algún criterio cuantitativo que mesirva para tomar una decisión)
• descripción de la secuencia obtenida de la base de datos
>gi|32172429|sp|P25807|CYS1_CAEEL Gut-specific cysteine proteinase precursor>gi|32172419|sp|P07268|PRZN_SERSP Serralysin precursor (Extracellular metallo proteinase) (Zinc proteinase)
Programación• Todo lenguaje de programación provee construcciones para
tomar decisiones: – if A then do B, else do C
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 211/300
211211 /39/39
– if A > 100 then continue else exit
• Algunos lenguajes de programación proveen métodos paraejecutar otros programas
– salir al sistema operativo, ejecutar el programa X y tomar el output – blast secuencia vs swissprot
– system( “blast -i secuencia -d swissprot” )
• Lo más dificil: analizar el output y tomar los datos de interés
– para poder tomar decisiones (hacer comparaciones) tenemos quetener los datos en variables
Reportes de BLAST• Un reporte de BLAST tal como aparece en un navegador o al
ejecutar el programa en la línea de comando (Unix) esbasicamente un archivo de texto (un archivo plano o flatfile)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 212/300
212212 /39/39
basicamente un archivo de texto (un archivo plano o flatfile)
• Ningun reporte es igual a otro. Sin embargo hay patronessimilares (la apariencia de hecho es similar). Tenemos queentrenar a nuestro programa para reconocer patrones:
– la primer linea contiene información sobre el programa
– la quinta línea contiene información sobre la secuencia utilizadapara la búsqueda
– la décima línea contiene información sobre la base de datos
– la línea que comienza con ‘>’ indica el comienzo de la descripciónde un hit
– etc.
Anatomía de un reporte de BLASTHeader
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 213/300
213213 /39/39
Programa$programa = “TBLASTN” $version = “2.2.6”
Query$id = “GROU_DROME”
$accession = “P16371” $descripcion = “Groucho protein …” $longitud = “719”
Base de datos$database = “GenBank non-mouse …” $secuencias = “8104717”
Anatomía de un reporte de BLASTHit List
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 214/300
214214 /39/39
Anatomía de un reporte de BLAST
Subject
High scoring pairs (HSPs)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 215/300
215215 /39/39
j$gi = “132150256” $gb = “CB923560” $version = “1” $desc = “TcAmaPl03Run01_C08 …” Longitud = “653”
HSP info$score = “58.9” $expect = “7e-10” $identity = “24%” $similarity = “43%” $frame = “+1’
Anatomía de un reporte de BLASTFooter
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 216/300
216216 /39/39
Estadísticas para esta corrida
Base de datosParámetros estadísticosMatrizPenaltiesDetalles sobre lo que hizo el algoritmo
Nuevos formatos• Los reportes estaban diseñados con un usuario (humano) en mente
– Formato no estructurado
– Ideal para lectura
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 217/300
217217 /39/39
Ideal para lectura
• Cada vez más los reportes que producen distintos programas seencuentran en formatos estructurados más fáciles de analizar desde elpunto de vista de la computadora – XML
– ASN.1 – Tabulado
• Estos formatos no son amigables para un humano (no son fáciles deleer)
Representación de la información
flatfiles
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 218/300
218218 /39/39
procesamiento
resultados
Ayer
Representación de la información
flatfiles
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 219/300
219219 /39/39
procesamiento
resultados
DB
Hoy
Analizando un reporte de BLAST• Nuestro programa ya leyó el reporte
• Y almacenó los valores que le pedimos en distintas variables
• Ahora podemos hacerle hacer lo que querramos:
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 220/300
220220 /39/39
Ahora podemos hacerle hacer lo que querramos:
– (en pseudocódigo):
• if $score < 100 { read next report }
else { print $accession }
• if $description =~ “proteinase” { print $accession} else { read nextreport }
• if $score < 100 AND $description =~ “proteinase”
{ print $accession }
else { read next report }
Módulos de software reusables• Resumiendo:
– nuestro programa tiene que poder leer el reporte (FACIL)
– identificar dentro del reporte distintos elementos y almacenarlos en
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 221/300
221221 /39/39
p y
variables (MAS COMPLICADO) – tomar decisiones en base a los valores contenidos en las variables y
realizar acciones (imprimir algo en pantalla, almacenar datos en un archivo,base de datos, etc.) (Criterio del usuario)
• El criterio del usuario es lo que va a hacer que el programa sirva paraun fin u otro
• Es evidente que los pasos 1 y 2 van a ser necesarios para cualquier programas que intenten procesar reportes de BLAST – solo hay que programarlos una vez
– modulos reusables (subrutinas)
Bibliotecas de modulos reusables• Perl, Python, Java, C
– en general todos los lenguajes proveen bibliotecas de módulos reusables
– el módulo contiene código que realiza ciertas operaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 222/300
222222 /39/39
g q p
– no es necesario saber como funciona internamente el módulo para poder usarlo
– solo necesitamos saber que datos necesita (por ejemplo: una secuencia) yque resultados produce (un valor: 135, una respuesta: SI/NO)
•En el caso de aplicaciones biológicas – BioPerl
– BioPython
– BioJava
– Otros
Pipelines• Qué es un pipeline?
– Una línea automatizada de análisis
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 223/300
223223 /39/39
Seq
BLAST Pfam TMHMM SignalP etc
Base de datos
CGI
Web Page
IntegraciónY
Visualización
Almacenamiento
Fábrica de resultados
Pipelines: ejemplos• Sistemas de anotación automática de genomas
– Ensembl - http://www.ensembl.org
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 224/300
224224 /39/39
– UCSC Genome Browser - http://genome.ucsc.edu
– ORNL Genome Channel - http://compbio.ornl.gov/channel
– HAMAP - http://us.expasy.org/sprot/hamap
Estrategia HAMAP
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 225/300
225225 /39/39
ORFans
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 226/300
226226 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 227/300
227227 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 228/300
228228 /39/39
Consideraciones prácticas• La bioinformática es más barata que el trabajo en el laboratorio
• El equipamiento es significativamente más barato que el de un laboratorio debiología molecular
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 229/300
229229 /39/39
• Los materiales (programas) y reactivos (datos) son en general gratuitos ylibremente accesibles
• Almacenamiento – La cantidad y tipos de bases de datos que se planean instalar (ejemplo: GenBank actualmente
requiere 120 GB)
– La cantidad y tipo de datos que se planean generar
• Memoria y Procesador – Los requerimientos de los distintos métodos
– BLAST es principalmente memoria-intensivo
– HMMER es principalmente procesador-intensivo
Consideraciones prácticas• Backup
– CD
– Cinta
– Un segundo disco
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 230/300
230230 /39/39
• Software – Sistema operativo: unix
– Paquetes: BLAST, FASTA, etc
– Software de manejo de bases de datos: MySQL, PostgreSQL
– Lenguajes de proramación: Perl, Java, Python, C, C++
• Para un laboratorio chico una PC con un disco un poco más grande yun poco más de memoria que lo común pueden ser suficientes
Con respecto a la protozoología• Los genomas de varios protozoarios están terminados o cerca de
estarlo – Plasmodium falciparum, berghei, chabaudi, knowlesi
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 231/300
231231 /39/39
– Toxoplasma gondii – Trypanosomatidos (T. cruzi , T. brucei , L. major )
• Algunos otros se encuentran en distintos estados – Entamoeba hystolytica
– Theileria annulata
– Babesia bovis – Eimeria tenella
• En algunos casos hay proyectos post-genómicos en curso o reciéncomenzando – Proteomics
– Microarrays
– RNAi
Bibliografía sugerida• Developing Bionformatics Computer Skills
– O’Reilly & Associates
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 232/300
232232 /39/39
• Bioinformatics. Sequence and genome analysis.
– CSHL Press
• Bioinformatics, a practical guide to the analysis of genes and proteins
– Wiley InterScience
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 233/300
233233 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 234/300
234234 /39/39
Búsqueda en bases de datos
Similitud, homología.
Métodos heurísticos.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 235/300
235235 /39/39
Búsqueda en bases de datos
Perspectiva general
Búsqueda en BD frente al alineamiento desecuencias• Una de las aplicaciones más conocidas es buscar [nuevas] secuencias
en una BD.
• Esto suele hacerse alineando la secuencia contra todas las de la BD.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 236/300
236236 /39/39
– Proceso parecido al alineamiento por parejas. – Objetivos distintos: interesa más la puntuación que el alineamiento en si.
– Los parámetros que mejor distingan entre secuencias relacionadas y lasque no lo están no son necesariamente los mismos que proporcionan elmejor alineamiento.
Búsqueda en BD y predicción de la función deuna proteína o un gen• La búsqueda de secuencias en bases de datos puede verse como un
proceso de descubrimiento científico en el que.
– Se utiliza la información acumulada.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 237/300
237237 /39/39
– Para descubrir propiedades de nuevas secuencias.
• Obviamente como en toda investigación.
– Es preciso proceder con meticulosidad y racionalidad.
– Un proceso incorrecto o descuidado puede llevar a conclusiones erróneas oa omitir hallazgos.
¿Puede predecirse la función de una proteínao un gen?• La evolución es un proceso conservativo
– Cambian los residuos en una secuencia
– Pero se conservan las propiedades bioquímicas y los procesos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 238/300
238238 /39/39
fisiológicos
• Si somos capaces de encontrar en la BD secuenciashomólogas a la secuencia problema concluimos que lanueva secuencia “debe de tener” propiedades similares a la
secuencia conocida
Homología y similitud• Para inferir las propiedades de una nueva secuencia
precisamos de secuencias homólogas a ésta.
•
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 239/300
239239 /39/39
Sin embargo la homología no es observable, solo la similitud.• Debemos pues determinar… – Cual es la mejor forma de medir la similitud.
– Como determinar si de la similitud observada puede inferirse lahomología.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 240/300
240240 /39/39
Fuentes de información para la búsquedaen bases de datos
Fuentes de información• La búsqueda en BD se fundamenta en tres tipos distintos de
fuentes de información [conocimiento previo].
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 241/300
241241 /39/39
– El sistema de puntuación con el que se cuantifica el grado desimilitud.
– El algoritmo utilizado para realizar las comparaciones.
– La base de datos en donde se realiza la búsqueda.
El sistema de puntuación• La similitud se cuantifica con matrices de sustitución (PAM,
BLOSUM, etc…).
•
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 242/300
242242 /39/39
Se han obtenido analizando sustituciones conocidas de unos AA por otros entre secuencias con grados distintos dedivergencia y conservación de función. – Siempre es mejor usar una matriz adecuada que suponer
sustituciones equiprobables.
–Distintos grados de divergencia requieren distintas matrices depuntuación.
El algoritmo de búsqueda• Cada algoritmo (S-W, FASTA, Blast).
– Aprovecha de forma distinta la información.
– Imponiendo restricciones distintas sobre el modelo evolutivo.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 243/300
243243 /39/39
• SW: pocas restricciones. – Muy sensitivo pero poco selectivo.
– Lento.
• FASTA/Blast: restricciones heurísticas. – Pueden resultar en menor sensibilidad.
– Más selectivos y mucho más veloces.
La base de datos• Es la fuente más evidente de conocimiento preexistente.
• Una búsqueda adecuada en BD puede ahorrar muchas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 244/300
244244 /39/39
horas de trabajo en el laboratorio.
Suposiciones en que se basala búsqueda en las BD• La búsqueda en BD presupone que…
– Las secuencias buscadas tienen ancestros comunes con lasecuencia problema.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 245/300
245245 /39/39
– El camino evolutivo más adecuado es el que presupone un menor número de cambios.
• No todas las sustituciones son igualmente probables: Debemos usar matrices de sustitución que las ponderen adecuadamente.
• Las inserciones y eliminaciones son menos probables que lassustituciones
En la práctica …• La elección del algoritmo de búsqueda influye en
– La sensibilidad y
– La especificidad
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 246/300
246246 /39/39
de la búsqueda.
• La elección de la matriz de similitud determina el patrón y lacantidad supuesta de sustituciones en las secuencias que seespera descubrir en la búsqueda.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 247/300
247247 /39/39
Sensibilidad y especificidad
Exitos y fracasos en la búsqueda
• Supongamos que conociéramos TODAS las coincidencias entre una
i bl b d d t
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 248/300
248248 /39/39
secuencia problema y una base de datos.• En este caso podríamos distinguir si, dada una coincidencia, ésta es
cierta o falsa.
• Esto nos lleva a distinguir entre.
– Positivos verdaderos (True positives TP).
– Positivos Falsos . (False Positives, FP). – Negativos Verdaderos (True Negatives, TN).
– Negativos Falsos (False Negatives, FN).
Verdaderos/Falsos Positivos/Negativos
Realidad Coincidencia
Ci t
Coincidencia
F l
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 249/300
249249 /39/39
DetecciónCierta Falsa
Positivo:Se detecta coincidencia
Positivo verdadero Falso positivo
Negativo:
No se detecta lacoincidencia
Falso Negativo Negativo verdadero
Sensibilidad frente aEspecificidad (“Selectividad”)
S ibilid d TP /(TP FN)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 250/300
250250 /39/39
• Sensibilidad= TP /(TP+FN)
% de coincidencias bien identificadas
(% positivos entre las coincidencias)
• Especificidad = TP / (TP+FP)
% de positivos correctos
(% de correctos entre los positivos)
El compromiso entresensibilidad y especificidad• Si en una búsqueda colocamos el umbral alto
– Cuesta localizar los positivos Pocos FP – Pero tendremos más falsos negativos
Es decir un umbral alto suele conllevar una baja sensibilidad y una alta
ifi id d
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 251/300
251251 /39/39
especificidad• AL reves si colocamos un umbral bajo
– Tendremos muchos positivos Tambien más FP – Pero habran menos falsos negativos
Es decir un umbral bajo conlleva una alta sensibilidad y una baja especificidad
• Idealmente:mirar de lograr un equilibrio,
• O en todo caso decidir que error nos interesa más controlar en cadasituación
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 252/300
252252 /39/39
< 0.05
< 1.00
Low sensitivity,many false
negatives
High selectivity,
few false positives
Highsensitivity,
few false
negatives
L
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 253/300
253253 /39/39
< 1.00
Lowselectivity,
many false
positives
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 254/300
254254 /39/39
Algoritmos de búsqueda
De la programación dinámica a los métodosheurísticos
Busqueda basada en PD• Una forma razonable de buscar una secuencia en una base
de datos es realizando alineamientos locales de ésta contra
t d l d l b d d t
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 255/300
255255 /39/39
todas las de la base de datos• Algoritmo: Smith-Waterman – Encuentra una solución óptima
– Sólo impone una restricción: Puntuación > 0
– Proporciona la mejor sensibilidad
Inconvenientes de labúsqueda basada en SW• La busqueda basada en PD proporciona una gran
sensibilidad pero – Es poco específica Pocos falsos negativos: Fàcil perder las
“homologías remotas”
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 256/300
256256 /39/39
homologías remotas – Es necesariamente lenta.
• Alternativa: Métodos heurísticos – Aproximaciones a SW con restricciones que:
• Aumentan la especificidad (aunque baja la sensibilidad)
• Són mucho más rápidas
FASTA• Aproximación a S-W que utiliza dos heurísticas para ir más
rápido a costa de perder sensibilidad
Heurísticas : Restricciones al modelo evolutivo implicito en la
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 257/300
257257 /39/39
• Heurísticas : Restricciones al modelo evolutivo implicito en lacomparación de secuencias – Tamaño de palabra (Word size)
– Tamaño de ventana (Window size)
Tamaño de palabra en FASTA• La comparación entre secuencias no se realiza residuo a residuo sino
por grupos de residuos,
– 2 residuos en AA.
6 bases en DNA
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 258/300
258258 /39/39
– 6 bases en DNA.
• A mayor tamaño de palabra menor es la sensibilidad y mayor laespecificidad.
• El efecto de variar el tamaño de palabra se muestra en los dot-plots: Amayor tamaño menor numero de coincidencias.
Tamaño de palabra=1• Ruidoso
• Es dificillocalizatr las
zonas de
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 259/300
259259 /39/39
zonas desimilitud
Tamaño de palabra=2
• Se ven las
regiones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 260/300
260260 /39/39
regionescandidatas
• Aunque se pierdenalgunascoincidencias
Tamaño de palabra=3• Sin ruído pero
• Apenas sincoincidencias
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 261/300
261261 /39/39
BLAST
• Aproximación similar a la anterior basada en aparear fragmentos
cortos que irá extendiendo para buscar alineamientos locales
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 262/300
262262 /39/39
cortos que irá extendiendo para buscar alineamientos locales• Utiliza un modelo estadístico para encontrar los mejores
alineamientos entre la secuencia desconocida y la BD
• HSP: High-scoring Segment Pair
– La unidad fundamental de trabajo con BLAST
– Corresponde a una región de máxima similitud entre dossubsecuencias (palabras, W ) con una puntuación más grande o igual auna puntuación umbral, T
BLAST: Algoritmo
1. Compilar todas las palabras de medida n que den una puntuación
superior al umbral (HSP)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 263/300
263263 /39/39
superior al umbral (HSP)2. Comparar estas palabras con las de la BD para identificar las
identidades exactas (“hits”)
3. Extender las palabras que han superado el umbral, en las dosdirecciones mirando de mejorar la puntuación
– La extensión acabará si baja la puntuación por debajo de otro umbral,si llega a cero o si se acaba la secuencia
1. Listar los segmentos extendidos de puntuación más alta
Algoritmo de BLAST (1)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 264/300
264264 /39/39
Algoritmo de BLAST (2)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 265/300
265265 /39/39
Algoritmo de BLAST (3)
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 266/300
266266 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 267/300
267267 /39/39
5. Significación de los resultados
E-values, p-values y bit-scores• Dado que los programas de búsqueda heurística tan sólo
encuentran coincidencias aproximadas conviene poder cuantificar cuan aproximadas son
E t h di t di ti t t dí ti
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 268/300
268268 /39/39
• Esto se hace mediante distintos estadísticos – E-value
– P-value
– Bit-scores
E-values
• Dado un High Scoring Pair el E-value es el número esperado de
puntuaciones iguales o superiores a las del HSP dado
• Un E-value de 10 para una coincidencia significa, que, en una base de datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 269/300
269269 /39/39
Un E value de 10 para una coincidencia significa, que, en una base de datosdel mismo tamaño en la que se ha realizado la búsqueda, se podría esperar encontrar hasta 10 coincidencias con la misma puntuación o similar,simplemente por azar
• El E- value es la medida de corte más utilizada en las búsquedas en basesde datos. Sólo se informa de las coincidencias que superan un nivel mínimo
• El E-value oscila entre 0 y cualquier valor
P-values• Refleja la probabilidad de obtener por azar una puntuación superior o
igual a la observada
• Se relaciona con el E-value en que: P=1-e-E
• Un P-valor de 0 03 significa que hay una probabilidad (>=) 3% det t ió i l b d i l t
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 270/300
270270 /39/39
Un P valor de 0.03 significa que hay una probabilidad ( ) 3% deencontrar una puntuación superior a la observada simplemente por azar
• Si E<0,01 Los P-valores y los E-valores son similares
• Los p-valores oscilan entre 0 y 1
Bit scores• El valor de la puntuaciones obtenidas por un emparejamiento
carecen de sentido si no se tiene en cuenta el tamaño de labase de datos y el sistema de puntuación
L Bit li l t i
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 271/300
271271 /39/39
• Los Bit-scores normalizan las puntuaciones paraindependizarlas de ambos factores de forma que podamoscompararlas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 272/300
272272 /39/39
Score E-Value
< 0.05
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 273/300
273273 /39/39
< 1.00
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 274/300
274274 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 275/300
275275 /39/39
Bases de datos
Tipos de bases de datos• Primarias
– Principales depósitos de información. Datos de secuencia oestructura. Pueden contener datos adicionales.
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 276/300
276276 /39/39
• Derivadas – Preparadas a partir de primarias. Información adicional procesada
manual o automáticamente
Bases de datos biológicas
• Primarias
– Información suministrada por trabajo experimentalL i tit ió t i l i f ió ñ d d
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 277/300
277277 /39/39
– La institución receptora organiza la información per o no añade nada
• Ejemplo EMBL/GenBank
• Derivadas
– Anotadas a posteriori
• Los datos son revisados, corregidos y se añade información bibliográfica• Ejemplo SWISS-PROT
– Derivadas computacionalmente
• Ejemplo PFAM
– Combinaciones específicas
Molecular Database Collection 2006 update
Principales Tipos de Búsqueda• Acceso directo a la base de datos
– Normalmente se obtiene una información más elaborada
•Sistemas de búsqueda global – SRS, NCBI Entrez
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 278/300
278278 /39/39
q gSRS, NCBI Entrez – Automatizado, uniforme. Permite una visión global de la información (varias
BD simultáneamente)
• Acceso programático (bioXXX, servicios Web, taverna)
Bases de datos de secuencia
• Contienen todas las secuencias obtenidasexperimentalmente
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 279/300
279279 /39/39
Contienen todas las secuencias obtenidasexperimentalmente – DNA genómico
– cDNA, RNA
– EST
– Proyectos genoma (HTS) – Proteína
– ...
Origen de la información• Trabajo individual de investigación
– Produce información de gran calidad en cantidades muy limitadas
• Secuenciaciones masivas: EST HTS proyectos genoma
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 280/300
280280 /39/39
• Secuenciaciones masivas: EST, HTS, proyectos genoma. – Producen mucha información de una calidad inferior, en algunos
casos dudosa.
Principales repositorios• DNA/RNA
– (EMBL, Genbank, DDBJ), RefSeq
• Proteína
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 281/300
281281 /39/39
• Proteína – Uniprot (Swissprot/TrEMBL), PIR
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 282/300
282282 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 283/300
283283 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 284/300
284284 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 285/300
285285 /39/39
TEXT
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 286/300
286286 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 287/300
287287 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 288/300
288288 /39/39
Anotaciones
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 289/300
289289 /39/39
Traducción
http://www.expasy.org
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 290/300
290290 /39/39
Información cruzada
• La mayoría de archivos de bases de datos incluyenenlaces a otras bases de datos
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 291/300
291291 /39/39
– Secuencia DNA Secuencia proteína
– Secuencia Estructura 3D
– Secuencia Datos bibliográficos
– ....
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 292/300
292292 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 293/300
293293 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 294/300
294294 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 295/300
295295 /39/39
Busqueda integrada. SRS
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 296/300
296296 /39/39
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 297/300
297297 /39/39
Búsqueda integrada. Entrez
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 298/300
298298 /39/39http://www.ncbi.nlm.nih.gov/Database/datamodel/index.html
Uniprot ID PDB ID getHeadersfromPDBId PDBTextString
Acceso prog. Web Services
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 299/300
299299 /39/39
Output
ServiceInput/output
AAS: AminoAcidSeq
getAASfromUniprot getAASfromPDBId
getAASfromPDBText
getPDBFilefromPDBId
AAS PDBText
BLASTText
PMUTTextPHDText
StringtoAAS
runPSIBlastfromAAS
runPHDfromBlastText runPMUTHSfromBlastText
FSOLVText
runFSOLVfromPDBText
Notas de prudencia• Las bases de datos pueden contener errores
• Distintas versiones (“releases”) pueden contener diferencias
significativas
5/17/2018 Class 70 Sequence Alignment - slidepdf.com
http://slidepdf.com/reader/full/class-70-sequence-alignment 300/300
• Todos los grupos bioinformáticos publican bases de datos, no existecontrol
Recommended