Download - Métodos Heurísticos
![Page 1: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/1.jpg)
Métodos Métodos HeurísticosHeurísticos
Ventajas: Más rápido
Desventajas: Sub-óptimo
![Page 2: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/2.jpg)
Las más conocidasLas más conocidas
FAST: Lipman, Pearson (1985)
BLAST (Basic Local Alignment Search Tool):
Altschul et al. (1990)
![Page 3: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/3.jpg)
FASTFAST
• FASTP (proteínas)
• FASTN (ADN)
• FASTA (proteínas y ADN)
• TFASTA (una proteína contra una base de datos de ADN)
• LFASTA (devuelve más de un alineamiento local)
![Page 4: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/4.jpg)
Algoritmo FASTPAlgoritmo FASTP
• Secuencias s y t
• |s| = m, |t| = n
• ktup (1 ó 2 para proteínas)
• Tabla de búsqueda (lookup table, ej: hash)
• Vector indexado por offsets e inicializado en 0.
![Page 5: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/5.jpg)
EjemploEjemplo (pág. 87)
s = HARFYAAQIVL
t = VDMAAQIA
1 2 3 4 5 6 7 8 9 10 11
H A R F Y A A Q I V Ls =
1 2 3 4 5 6 7 8
V D M A A Q I At =
![Page 6: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/6.jpg)
1 2 3 4 5 6 7 8 9 10 11
H A R F Y A A Q I V Ls =
A 2,6,7
F 4
H 1
I 9
L 11
Q 8
R 3
V 10
Y 5
otras-
Tabla de búsqueda
A
F
H
I
L
Q
R
V
Y
otras
![Page 7: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/7.jpg)
Vector de Offsets
1 2 3 4 5 6 7 8 9 10 11
H A R F Y A A Q I V Ls =
1 2 3 4 5 6 7 8
V D M A A Q I At =
A 2,6,7
F 4
H 1
I 9
L 11
Q 8
R 3
V 10
Y 5
otras -
1 2 3 4 5 6 7 8
V D M A A Q I At =
| | | | | | | |+9
-2+2+3
-3+1+2
+2
+2
-6-2-1
offsets
![Page 8: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/8.jpg)
1 2 3 4 5 6 7 8
V D M A A Q I At =
| | | | | | | |+9
-2+2+3
-3+1+2
+2
+2
-6-2-1
-7 -6 -5 -4 -3 -2 -1 0 +1 +2 +3 +4 +5 +6 +7 +8 +9+10
1 1 2 1 1 4 1 1
offsets
Vector de offsets:
-7 -6 -5 -4 -3 -2 -1 0 +1 +2 +3 +4 +5 +6 +7 +8 +9+10
![Page 9: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/9.jpg)
ScoringScoring
• Se unen aquellas k-tuplas que están en la misma diagonal no muy lejos entre sí formando regiones.
• Se le da un puntaje a cada región dependiendo de los match y mismatch de cada uno.
• Las 5 mejores regiones se les da un nuevo puntaje utilizando una matriz de sustitución.
![Page 10: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/10.jpg)
Matrices de SustituciónMatrices de Sustitución
Ejemplos:
• PAM (Point Accepted Mutation) – PAM1, PAM 250
•BLOSUM (BLOcks SUbstitution Matrix) – BLOSUM62
• La elección puede influir fuertemente en el resultado del análisis.
• Representan una teoría particular de evolución.
![Page 11: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/11.jpg)
BLOSUM62BLOSUM62 A R N D C Q E G H I L K M F P S T W Y V B Z X *
A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0 -2 -1 0 -4
R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3 -1 0 -1 -4
N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3 3 0 -1 -4
D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3 4 1 -1 -4
C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 -4
Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1 0 -3 -1 0 -1 -2 -1 -2 0 3 -1 -4
E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2 1 4 -1 -4
G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3 -1 -2 -1 -4
H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3 0 0 -1 -4
I -1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3 1 0 -3 -2 -1 -3 -1 3 -3 -3 -1 -4
L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2 2 0 -3 -2 -1 -2 -1 1 -4 -3 -1 -4
K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2 0 1 -1 -4
M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 0 -2 -1 -1 -1 -1 1 -3 -1 -1 -4
F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 -4 -2 -2 1 3 -1 -3 -3 -1 -4
...
![Page 12: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/12.jpg)
• El mejor de estos puntajes es utilizado como el score inicial (initial score).
• Para las secuencias con los mejores puntajes, se calcula un score optimizado generando una alineamiento exacto usando programación dinámica restringido a una franja alrededor del alineamiento inicial.
• ktup alto favorece la selectividad, ktup bajo incrementa sensibilidad.
Continuado...Continuado...
![Page 13: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/13.jpg)
Salida (output)Salida (output)fasta -E 2.0 -f -16 -g -4 -s dna.mat -O clase.txt VipRo.txt m15pla~1.seq 6
VipRo.txt, 160 aa vs m15pla~1.seq library
532 residues in 1 sequences results sorted and z-values calculated from opt score 1 scores better than 1 saved, ktup: 6, variable pamfact dna.mat matrix, gap penalties: -16,-4 joining threshold: 47, optimization threshold: 32, width: 16 scan time: 0:00:00The best scores are: initn init1 opt m15pla~1 159 159 194
>> m15pla~1 (532 nt)initn: 159 init1: 159 opt: 194 59.048% identity in 105 nt overlap
![Page 14: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/14.jpg)
30 40 50 60 70 80VipRo. GAGAGCTGGCTAACTTAATTAATGTATGTGTATATCCTGATAAA---TGAATGCATTCT- :::..: : .::: :: : ::: : AATATNNCTGGGNAAAANGGGAGGGAATTTTG 10 20 30 90 100 110 120 130 140VipRo. TTATGATACTTTCTACCGTATGAATCTTTTGGGAAGAACGCGACTTTGTAGGGGCGGGAG X::::..: :.: .::.: ::: :: :: :::.: :: : :: :.:: :::::::::X TTATGNNAATNTTNACNGGATGGATTTTCGGGGNAAAAAGAGAATNTGAAGGGGCGGGAA 40 50 60 70 80 90
150 160VipRo. CCGATAGAGGCCAGA :....: :::.. :: CNNNNAAAGGNNGGAGAAAATTTAAAGNTAAGTTTTCAATNCCATTNACCNTTTTGGTTN 100 110 120 130 140 150
Library scan: 0:00:00 total CPU time: 0:00:00
![Page 15: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/15.jpg)
BLASTBLAST
• BLASTP
• BLASTN
• BLASTX (ADN contra una base de datos de proteínas)
• TBLASTN (proteína contra una base de datos de ADN)
• TBLASTX
![Page 16: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/16.jpg)
Algoritmo BLASTAlgoritmo BLAST
• Secuencias s y t
• |s| = m, |t| = n
• word: default ADN =11, default proteínas = 3
![Page 17: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/17.jpg)
Paso 1 - IndexaciónPaso 1 - Indexación
• Se generan un índice a cada word de la secuencia s y de todas las secuencias t de la base de datos:
s = TCATATCACGGCCC... Con w = 11
words:TCATATCACGG
CATATCACGGC
ATATCACGGCC
...
![Page 18: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/18.jpg)
Paso 2 – Búsqueda InicialPaso 2 – Búsqueda Inicial• Cada word de la secuencia s es comparada con el índice de la base de datos y se le da un score.
• ADN: match = +1, mismatch = -3
Proteínas: Se utiliza una matriz de sustitución
• Se descartan aquellas words con puntaje menor a un umbral T (ADN = 0, proteínas = 11)
• Los resultantes se los llama HSPs (High-scoring Segment Pair).
![Page 19: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/19.jpg)
s = TCAGATCACGG...
t = TGTCAGCTAACGGCC...
word s: TCAGATCACGG
word t: TGTCAGCTAAC
GTCAGCTAACG
TCAGCTAACGG
...
Alineamientos:
TCAGATCACGG
| | |
TGTCAGCTAAC
TCAGATCACGG
| |
GTCAGCTAACG
TCAGATCACGG
|||| | ||||
TCAGCTAACGG
Score: -21
Score: 3
Score: -25
HSP
![Page 20: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/20.jpg)
Paso 3 – ExtensiónPaso 3 – Extensión
• Se extienden los HSP en ambas direcciones...
• ...hasta que el score llega a un umbral.
![Page 21: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/21.jpg)
s = TCAGATCACGG...
t = TGTCAGCTAACGGCC...
Alineamientos:
Original:
TCAGATCACGG
|||| | ||||
TCAGCTAACGG
Extensión:
TCAGATCACGG
|||| | ||||
TCAGCTAACGG
Extensión:
TCAGATCACGGC
|||| | |||||
TCAGCTAACGGC
Extensión:
TCAGATCACGGCC
|||| | ||||||
TCAGCTAACGGCC
Extensión:
TCAGATCACGGCCCAACGGACCTGAGG
|||| | |||||| ||
TCAGCTAACGGCCGTTACGATGCTAAA
Score: 3Score: 4Score: 5Score: -29
![Page 22: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/22.jpg)
Paso 4 – Inserción de gapsPaso 4 – Inserción de gaps
• Los gaps son agregados para conectar HSPs.
• Un gap será agregado si el costo de unir dos HSPs es positivo.
![Page 23: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/23.jpg)
Expect (E)Expect (E)
• E = la frecuencia esperada de un score en la base de datos.
• Un match solo será mostrado si su E es menor que un umbral.
![Page 24: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/24.jpg)
Salida (output)Salida (output)
BLASTN 2.0.11 [Jan-20-2000]
Reference:Altschul, Stephen F., Thomas L. Madden, Alejandro A. Schäffer, Jinghui Zhang, Zheng Zhang, Webb Miller, and David J. Lipman (1997), "Gapped BLAST and PSI-BLAST: a new generation of protein database searchprograms", Nucleic Acids Res. 25:3389-3402.
Query= (160 letters)
Database: tcruzi 206 sequences; 160,103 total letters
![Page 25: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/25.jpg)
Distribution of 41 Blast Hits on the Query Sequence
![Page 26: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/26.jpg)
Score E
Sequences producing significant alignments: (bits) Value
SIRE 317 5e-89
VIPPAPER 287 5e-80
VIP5P 287 5e-80
...SIRE Length = 435 Score = 317 bits (160), Expect = 5e-89 Identities = 160/160 (100%) Strand = Plus / Plus
Query: 1 ttaggagcttgtgaaaagaatgatcgtgggagagctggctaacttaattaatgtatgtgt 60 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct: 1 ttaggagcttgtgaaaagaatgatcgtgggagagctggctaacttaattaatgtatgtgt 60...
![Page 27: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/27.jpg)
Mejora a BLASTMejora a BLAST
• En lugar de extender (paso 3) todos los HSPs solamente se extienden aquellos que estén en la misma diagonal y a distancia A.
![Page 28: Métodos Heurísticos](https://reader034.vdocumento.com/reader034/viewer/2022051316/568144bd550346895db1853c/html5/thumbnails/28.jpg)
PSI-BLASTPSI-BLAST
PSI-BLAST: Position Specific Iterated-BLAST
1. BLAST.
2. Aquellos hits por arriba de un cierto umbral son utilizados para construir un alineamiento múltiple.
3. Se arma una matriz de sustitución específica para cada posición con el alineamiento múltiple.
4. BLAST con esta nueva matriz.
5. Se agregan los nuevos hits y se repite el proceso.