Métodos Métodos HeurísticosHeurísticos

Ventajas: Más rápido

Desventajas: Sub-óptimo

Las más conocidasLas más conocidas

FAST: Lipman, Pearson (1985)

BLAST (Basic Local Alignment Search Tool):

Altschul et al. (1990)

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)

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.

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 =

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

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

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

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.

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.

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

...

• 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...

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

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

BLASTBLAST

• BLASTP

• BLASTN

• BLASTX (ADN contra una base de datos de proteínas)

• TBLASTN (proteína contra una base de datos de ADN)

• TBLASTX

Algoritmo BLASTAlgoritmo BLAST

• Secuencias s y t

• |s| = m, |t| = n

• word: default ADN =11, default proteínas = 3

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

...

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).

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

Paso 3 – ExtensiónPaso 3 – Extensión

• Se extienden los HSP en ambas direcciones...

• ...hasta que el score llega a un umbral.

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

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.

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.

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

Distribution of 41 Blast Hits on the Query Sequence

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...

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.

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.