View
221
Download
0
Category
Preview:
Citation preview
Alineamientos de secuencias
¿Para qué hace falta la compoaración de secuencias?
Bases biológicas:
• Muchos genes y proteínas son miembros de familias que tienen funciones biológicas similares o un origen filogenético común.
Se usa para:
• Identificar relacciones evolutivas.• Identificar patrones conservados.• en caso de secuencias con funciones desconocidas:
encontrar dominios similares en otras proteinas implica una función similar.
Claves:• 1- que tipo de alineamiento hay que considerar• 2- que sistema de puntuacion “scoring” hay que
usar para clasificar los alineamientos• 3- que algoritmos hay que usar para encontrar la
solución óptima (o buena)• 4- métodos estadisiticos necesarios para
evaluar la significacion del score de los alineamientos
Alineamiento de secuencias
Tipos de comparación de secuencias
• Pairwise Alignments
• Alineamientos múltiples
• Búsquedas en bases de datos
• Principios de la comparación por pares de secuencias
• alineamientos globales / locales • sistemas de puntuación “scoring” • penalizaciones por GAP
• Métodos de pairwise sequence alignment • Basados en deslizamiento de ventanas “window-based” • programación dinámica
Pairwise Sequence Alignment
• Alineamientos globales
• Alineamientos locales
Pairwise Sequence Alignment
(Needleman & Wunsch) crea alineamientos en toda la
longitud de la secuencia.
Alineamiento Global
Para secuencias que estan muy relaccionadas
Dos secuencias con varias regiones de similaridad
1 AGGATTGGAATGCTCAGAAGCAGCTAAAGCGTGTATGCAGGATTGGAATTAAAGAGGAGGTAGACCG.... 67
1 AGGATTGGAATGCTAGGCTTGATTGCCTACCTGTAGCCACATCAGAAGCACTAAAGCGTCAGCGAGACCG 70
|||||||||||||| | | | |||| || | | | ||
Con un alineamiento local solo se obtendrá una similaridad muybaja: fragmento azul
Alineamiento Global
Alineamiento Local
14 TCAGAAGCAGCTAAAGCGT 32 ||||||||| |||||||||42 TCAGAAGCA.CTAAAGCGT 59
1 AGGATTGGAATGCT 14 |||||||||||||| 1 AGGATTGGAATGCT 14
39 AGGATTGGAAT 49 ||||||||||| 1 AGGATTGGAAT 11
62 AGACCG 67 ||||||66 AGACCG 71
Alineamiento local encuentra la region que tiene la mejor similaridadlocal.
Pairwise Sequence Alignmentalfa globina humana
beta-globina
leghemoglobina
Glutonina S-tranferasanematodos
Parámetros a tener en cuenta en el alineamiento de secuencias
Sistemas de puntuación:
• A cada par de símbolos se le asigna un valor numerico
basado en una tabla de comparación de síbolos.
Penalizaciones por Gap:
• apertura: Costo de introducir un gap• Extensión: Costo de extender el gap
actaccagttcatttgatacttctcaaa
taccattaccgtgttaactgaaaggacttaaagact
Sequencia 1
Sequencia 2
A G C T
A 1 0 0 0
G 0 1 0 0
C 0 0 1 0
T 0 0 0 1
Match: 1Mismatch: 0Score = 5
Sistemas de puntuación de secuencias de nucleótidos
Valores negativos que penalizen los mismatches:
A T C G
A 5 -4 -4 -4
T -4 5 -4 -4
C -4 -4 5 -4
G -4 -4 -4 5
Matches: 5Mismatches: 19
Score: 5 x 5 + 19 * (-4) = - 51
actaccagttcatttgatacttctcaaa
taccattaccgtgttaactgaaaggacttaaagact
Sequencia 1
Sequencia 2
Sistemas de puntuación de secuencias de nucleótidos
PTHPLASKTQILPEDLASEDLTI
PTHPLAGERAIGLARLAEEDFGM
Sequencia 1
Sequencia 2
Scoringmatrix
T:G = -2 T:T = 5Score = 48
C S T P A G N D . .
C 9
S -1 4
T -1 1 5
P -3 -1 -1 7
A 0 1 0 -1 4
G -3 0 -2 -2 0 6
N -3 1 0 -2 -2 0 5
D -3 0 -1 -1 -2 -1 1 6
.
.
C S T P A G N D . .
C 9
S -1 4
T -1 1 5
P -3 -1 -1 7
A 0 1 0 -1 4
G -3 0 -2 -2 0 6
N -3 1 0 -2 -2 0 5
D -3 0 -1 -1 -2 -1 1 6
.
.
Sistemas de puntuación de secuencias de proteínas
210 valores
• Amino acidos tienen diferentes propiedades bioquímicas y físicasque pueden influenciar su capacidad de ser reemplazados en la evolución
CP
GGAVI
L
MF
Y
W HK
RE Q
DN
S
T
CSH
S+S
positive
chargedpolar
aliphatic
aromatic
small
tiny
hydrophobic
Protein Scoring Systems
• Las matrices reflejan
• Probabilidades de substituciones mutuas
• Probabilidad de ocurrencia de un aminoacido
• Matrices mas usadas:
• PAM
• BLOSUM
Protein Scoring Systems
PAM (Percent Accepted Mutations) matrices
• Derived from global alignments of protein families .
• Family members share at least 85% identity (Dayhoff et al.,
1978).
• Construction of phylogenetic tree and ancestral sequences of each protein family
• Computation of number of replacements for each pair of amino acids
• The numbers of replacements were used to compute a so-called PAM-1 matrix.
• PAM 1 significa: 1% de mutaciones aceptadas, es decir se utilizaría esta matriz cuando uno esperara un 1 % de substituciones. PAM matrices para distancias evolucionarias mas grandes se pueden extrapolar a partir de esta matriz.
• PAM250 = 250 mutaciones por cada 100 residuos.
• A mayor número mayor distancia evolutiva.
PAM (Percent Accepted Mutations) matrices
PAM250 es muy común. a esta distancia evolutiva, 48% de los triptófanos, 41% de las cisteinas y 20% de las histidinas permanecen inalteradas pero solo 7% de las serinas
A R N D C Q E G H I L K M F P S T W Y V B Z
A 2 -2 0 0 -2 0 0 1 -1 -1 -2 -1 -1 -3 1 1 1 -6 -3 0 2 1 R -2 6 0 -1 -4 1 -1 -3 2 -2 -3 3 0 -4 0 0 -1 2 -4 -2 1 2 N 0 0 2 2 -4 1 1 0 2 -2 -3 1 -2 -3 0 1 0 -4 -2 -2 4 3 D 0 -1 2 4 -5 2 3 1 1 -2 -4 0 -3 -6 -1 0 0 -7 -4 -2 5 4 C -2 -4 -4 -5 12 -5 -5 -3 -3 -2 -6 -5 -5 -4 -3 0 -2 -8 0 -2 -3 -4 Q 0 1 1 2 -5 4 2 -1 3 -2 -2 1 -1 -5 0 -1 -1 -5 -4 -2 3 5 E 0 -1 1 3 -5 2 4 0 1 -2 -3 0 -2 -5 -1 0 0 -7 -4 -2 4 5 G 1 -3 0 1 -3 -1 0 5 -2 -3 -4 -2 -3 -5 0 1 0 -7 -5 -1 2 1 H -1 2 2 1 -3 3 1 -2 6 -2 -2 0 -2 -2 0 -1 -1 -3 0 -2 3 3 I -1 -2 -2 -2 -2 -2 -2 -3 -2 5 2 -2 2 1 -2 -1 0 -5 -1 4 -1 -1 L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6 -3 4 2 -3 -3 -2 -2 -1 2 -2 -1 K -1 3 1 0 -5 1 0 -2 0 -2 -3 5 0 -5 -1 0 0 -3 -4 -2 2 2 M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6 0 -2 -2 -1 -4 -2 2 -1 0 F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9 -5 -3 -3 0 7 -1 -3 -4 P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6 1 0 -6 -5 -1 1 1 S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2 1 -2 -3 -1 2 1 T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3 -5 -3 0 2 1 W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17 0 -6 -4 -4 Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10 -2 -2 -3 V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4 0 0 B 2 1 4 5 -3 3 4 2 3 -1 -2 2 -1 -3 1 2 2 -4 -2 0 6 5 Z 1 2 3 4 -4 5 5 1 3 -1 -1 2 0 -4 1 1 1 -4 -3 0 5 6
PAM 250
C
-8 17
W
W
El valor de un par de aa idénticos representa la probabilidad de que esteaa permanezca inalterado (e.g. triptófano)
• Derivada de alineamientos de dominios pertenecientes aproteinas alejadas en la evolucion (Henikoff & Henikoff,1992).
• Contaron la presencia de cada par de aa en cada columna de cada bloque de alineamientos.
• Los números obtenidos delanálisis de todos los bloques se usaronpara calcular las matricesde tipo BLOSUM.
A
A
C
E
C
A - C = 4A - E = 2C - E = 2A - A = 1C - C = 1
BLOSUM (Blocks Substitution Matrix)
AACEC
BLOSUM (Blocks Substitution Matrix)
• Las secuencias se clusterizan dentro de un bloque de acuerdo a su grado de identidad. Clusters are counted as a single sequence. • Las matrices BLOSUM difieren en el porcentaje de identidad de secuencias usado para hacer el clustering
• El número de la matriz (e.g. 62 en BLOSUM62) se refiere al porcentaje máximo de identidad entre las secuencias utilizado para crear la matriz
•Mayores número significan distancias evolutivas menores.
Matrices de substitución: Log-odds Ratio
P(x,y|R) =qx qyi iii
Dado un par de secuencias alineadas queremos asignar una score que mida el grado de posibilidad „likelihood“, de que las secuencias estan relaccionadas
Random model (unrelated) :
Match model (related) : P(x,y|M) =px yii i
Odds ratio :related
unrelatedP(x,y|
M)P(x,y|
R)
= =px yii i
qx qyi iii
px yi i
qx qyi i
i
Log-odds ratio : S = s(xi,yi)i
where : s(a,b) = logpab
qa qb
s(a,b) is the log likelyhood ratio of the residue pair (a,b) occurring as an aligned pair, as opposed to an unaligned pair.
x,y = amino acids (A,C......Y) P = likelyhoodi = 1....n (longitud de la secuencia n) q = probabilidad
Como escoger la matriz adecuada
• Generally, BLOSUM matrices perform better than PAM matrices for local similarity searches (Henikoff &
Henikoff, 1993).
• When comparing closely related proteins one should use lower PAM or higher BLOSUM matrices, for distantly related proteins higher PAM or lower BLOSUM matrices.
• For database searching the commonly used matrix is BLOSUM62.
T A T G T G G A A T G A
Como puntuar inserciones y delecciones
A T G T - - A A T G C A
A T G T A A T G C A
T A T G T G G A A T G A
La creación de un gap se penaliza con un score negativo.
insertion / deletion
• Un alineamiento optimo
• maximiza el numero de matches • minimiza el número de gaps
• Permitir la inserción arbitraria de muchos gaps puede dar lugar a scores altos entre secuencias no homologas.
• La penalización de los gaps fuerza a los alineamientos a alcanzar los criterios optimos
Gap Penalties
Gap Penalties
Linear gap penalty score:
(g) = - gd
Affine gap penalty score:
(g) = -d - (g -1)e
(g) = gap penalty score of a gap of lenght g
d = gap opening penalty
e = gap extension penalty
g = gap lenght
Scoring Insertions and Deletions
A T G T T A T A C
T A T G T G C G T A T A
Total Score: 4
Gap parameters:
d = 3 (gap opening)
e = 0.1 (gap extension)
g = 3 (gap lenght)(g) = -d - (g -1)e
(g) = -3 - (3 -1) 0.1 = -3.2
T A T G T G C G T A T A
A T G T - - - T A T A C
insertion / deletion
match = 1mismatch = 0
Total Score: 8 - 3.2 = 4.8
• Principios de la comparación por pares de secuencias
• alineamientos globales / locales • sistemas de puntuación “scoring” • penalizaciones por GAP
• Métodos de pairwise sequence alignment • Basados en deslizamiento de ventanas “window-based” • programación dinámica
Pairwise Sequence Alignment
A TTCACATA
T A C A T T A C G T A C
Sequence 1
Sequence 2
Pairwise Sequence Alignment
Dotplot:
A T T C
A C
A T A
T A C A T T A C G T A CSequence 1
Sequence 2
A dotplot da una visión general del alineamiento
Dotplot:
A T T C
A C
A T A
T A C A T T A C G T A C
T A C A T T A C G T A C
A T A C A C T T A
Sequence 1
Sequence 2
One possible alignment:
Cada diagonal en elgráfico corresponde a un posible alineamiento sin gap entre las dos secuencias
• Principios de la comparación por pares de secuencias
• alineamientos globales / locales • sistemas de puntuación “scoring” • penalizaciones por GAP
• Métodos de pairwise sequence alignment • Basados en deslizamiento de ventanas “window-based” • programación dinámica
Pairwise Sequence Alignment
Window-based Approaches
• Word Size
• Window / Stringency
Word Size Algorithm
T A C G G T A T G
A C A G T A T C
T A C G G T A T G
A C A G T A T C
T A C G G T A T G
A C A G T A T C
T A C G G T A T G
A C A G T A T C
C T A T G A C A
T A C G G T A T G
Word Size = 3
Window / Stringency
T A C G G T A T G
T C A G T A T C
T A C G G T A T G
T C A G T A T C
T A C G G T A T G
T C A G T A T C
T A C G G T A T G
T C A G T A T C
C T A T G A CA
T A C G G T A T G
Window = 5 / Stringency = 4
Considerations
• The window/stringency method is more sensitive than the wordsize method (ambiguities are permitted).
• The smaller the window, the larger the weight of statistical (unspecific) matches.
• With large windows the sensitivity for short sequences is reduced.
• Insertions/deletions are not treated explicitly.
Insertions / Deletions in a Dotplot
T
A
C
T
G
T
C
A
T
T A C T G T T C A TSequence 1
Sequence 2
T A C T G - T C A T| | | | | | | | |T A C T G T T C A T
Hemoglobin -chain
Hemoglobin
-chain
Dotplot (Window = 130 / Stringency = 9)
Dotplot (Window = 18 / Stringency = 10)
Hemoglobin
-chain
Hemoglobin -chain
• Principles of pairwise sequence comparison• global / local alignments• scoring systems• gap penalties
• Methods of pairwise sequence alignment • window-based approaches• dynamic programming approaches
• Needleman and Wunsch• Smith and Waterman
Pairwise Sequence Alignment
Procedimiento automático que encuentra el mejor
alineamiento con un score óptimo dependiendo de los
parámetros elegidos.
Dynamic Programming
Soluciones recursivas. Los problemas pequeños
se solucionan primero y las soluciones se usan
para resolver problemas mayores despues. Las
soluciones intermedias se almacenan en matrices
tabulares.
Principios básicos de la programación dinámica
-Initialization of alignment matrix: the scoring model
- Stepwise calculation of score values
(creation of an alignment path matrix)
- Backtracking (evaluation of the optimal path)
Initialization of Matrix (BLOSUM 50)
H E A G A W G H E E
P -2 -1 -1 -2 -1 -4 -2 -2 -1 -1
A -2 -1 5 0 5 -3 0 -2 -1 -1
W -3 -3 -3 -3 -3 15 -3 -3 -3 -3
H 10 0 -2 -2 -2 -3 -2 10 0 0
E 0 6 -1 -3 -1 -3 -3 0 6 6
A -2 -1 5 0 5 -3 0 -2 -1 -1
E 0 6 -1 -3 -1 -3 -3 0 6 6
Needleman and Wunsch (global alignment)
Sequence 1: H E A G A W G H E ESequence 2: P A W H E A E
Scoring parameters: BLOSUM50 matrix
Gap penalty: Linear gap penalty of 8
Creation of an alignment path matrix
Idea:Crear un alineamiento global optimo usando soluciones precias para alineamientos optimos de subsecuencias más pequeñas.
• Construct matrix F indexed by i and j (one index for each sequence)
• F(i,j) es el score para el mejor alineamiento entre el segmento inicial x1...i de x hasta xi y el segmento inicial y1...j de y hasta yj
• construir F(i,j) de forma recursiva empezando con F(0,0) = 0
-A
EEHH
G-WWAA
G-AP
E-
H-
Optimal global alignment:
F(i, j) = F(i-1, j-1) + s(xi ,yj)
F(i, j) = max F(i, j) = F(i-1, j) - d
F(i, j) = F(i, j-1) - d
F(i-1, j-1) F(i, j-1)
F(i-1,j) F(i, j)
-d
-d
s(xi ,yj)
Creation of an alignment path matrix
HEAGAWGHE-E--P-AW-HEAE
• If F(i-1,j-1), F(i-1,j) and F(i,j-1) are known we can calculate F(i,j)
• Three possibilities:
• xi and yj are aligned, F(i,j) = F(i-1,j-1) + s(xi ,yj)
• xi is aligned to a gap, F(i,j) = F(i-1,j) - d
• yj is aligned to a gap, F(i,j) = F(i,j-1) - d
• The best score up to (i,j) will be the largest of the three options
Creation of an alignment path matrix
H E A G A W G H E E 0
P
A
W
H
E
A
E
-8 -16 -24 -32 -40 -48 -56 -64 -72 -80
-8
-16
-24
-32
-40
-48
-56
F(j, 0) = -j d
Boundary conditions
F(i, 0) = -i d
Creation of an alignment path matrix
H E A G A W G H E E 0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
P -8
A -16
W -24
H -32
E -40
A -48
E -56
Stepwise calculation of score values
-2
-10
-9
-3
F(i, j) = F(i-1, j-1) + s(xi ,yj)
F(i, j) = max F(i, j) = F(i-1, j) - d
F(i, j) = F(i, j-1) - d
F(0,0) + s(xi ,yj) = 0 -2 = -2
F(1,1) = max F(0,1) - d = -8 -8= -16 = -2
F(1,0) - d = -8 -8= -16
F(1,0) + s(xi ,yj) = -8 -1 = -9
F(2,1) = max F(1,1) - d = -2 -8 = -10 = -9
F(2,0) - d = -16 -8= -24
-8 -2 = -10
F(1,2) = max -16 -8 = -24 = -10
-2 -8 = -10
-2 -1 = -3
F(2,2) = max -10 -8 = -18 = -3
-9 -8 = -17
P-H=-2
E-P=-1
H-A=-2
E-A=-1
H E A G A W G H E E 0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
P -8 -2 -9 -17 -25 -33 -42 -49 -57 -65 -73
A -16 -10 -3 -4 -12 -20 -28 -36 -44 -52 -60
W -24 -18 -11 -6 -7 -15 -5 -13 -21 -29 -37
H -32 -14 -18 -13 -8 -9 -13 -7 -3 -11 -19
E -40 -22 -8 -16 -16 -9 -12 -15 -7 3 -5
A -48 -30 -16 -3 -11 -11 -12 -12 -15 -5 2
E -56 -38 -24 -11 -6 -12 -14 -15 -12 -9 1
Backtracking
-5
1
-A
EE
HHG-WWAA
G-AP
E-H-
0
-25
-5
-20
-13
-3
3
-8 -16
-17
Optimal global alignment: EE
Two differences:
1.
2. An alignment can now end anywhere in the matrix
Smith and Waterman(local alignment)
Example:Sequence 1 H E A G A W G H E ESequence 2 P A W H E A E
Scoring parameters: Log-odds ratiosGap penalty: Linear gap penalty of 8
0
F(i, j) = F(i-1, j-1) + s(xi ,yj)
F(i, j) = F(i-1, j) - d
F(i, j) = F(i, j-1) - d
F(i, j) = max
H E A G A W G H E E 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 5 0 0 0 0 0
W 0 0 0 0 2 0 20 12 4 0 0
H 0 10 2 0 0 0 12 18 22 14 6
E 0 2 16 8 0 0 4 10 18 28 20
A 0 0 8 21 13 5 0 4 10 20 27
E 0 0 6 13 18 12 4 0 4 16 26
Smith Waterman alignment
Optimal local alignment: AA
G-
EE
HH
WW
28
0
5
20 12
22
Extended Smith & Waterman
To get multiple local alignments:• delete regions around best path
• repeat backtracking
H E A G A W G H E E 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 0 0 0 0 0
W 0 0 0 0 2 0 0 0
H 0 10 2 0 0 0
E 0 2 16 8 0 0
A 0 0 8 21 13 5 0
E 0 0 6 13 18 12 4 0
0
5
20 12 4
12 18 22 14 6
4 10 18 28 20
4 10 20 27
4 16 26
Extended Smith & Waterman
H E A G A W G H E E 0 0 0 0 0 0 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0
A 0 0 0 5 0 0 0 0 0 0
W 0 0 0 0 2 0 0 0
H 0 10 2 0 0 0
E 0 2 16 8 0 0
A 0 0 8 21 13 5 0
E 0 0 6 13 18 12 4 0
Second best local alignment:
0
21
10
16
HHEEAA
Extended Smith & Waterman
Further Extensions of Dynamic Programming
• Overlap matches
• Alignment with affine gap scores
• Pairwise sequence comparison• global / local alignments• parameters• scoring systems• insertions / deletions
• Methods of pairwise sequence alignment • dotplot• windows-based methods• dynamic programming• algorithm complexity
Pairwise Sequence Alignment
End.of.pa.irwise..sequence | | | | | align.ment.cours.e
Methods of Pairwise Comparison
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step
Programs perform global alignments:
• Needleman & Wunsch: (Pileup, Tree, Clustal)
• Word Size Method: (Clustal)
• X. Huang (MAlign) (modified N-W)
1.
Construction of a Guide Tree
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step
1 2 3 4 5
1
2
3
4
5
Sequence
Similarity Matrix:
displays scores ofall sequence pairs.
The similarity matrix is transformed into a distance matrix . . . . .
2.
Construction of a Guide Tree
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step
DistanceMatrix
1
23
4
5
Guide Tree
Neighbour-Joining Method or
UPGMA (unweighted pair group method of arithmetic averages)
2.
Multiple Alignment
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step
1
23
4
5
Guide Tree
2
3.
1
T T A C T T C C A G G
Columns - once aligned - are never changed
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step
T T A C T T C C A G G
3.
G T C C G - - C A G G
T T - C G C - C - G G
G T C C G - C A G G
T T - C G C C - G G
T T A C T T C C A G G
Columns - once aligned - are never changed
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step
T T A C T T C C A G G
3.
G T C C G - - C A G G
T T - C G C - C - G G
G T C C G - C A G G
T T - C G C C - G G
. . . . and new gaps are inserted.
T T A C T T C C A G G
Columns - once aligned - are never changed
Multiple AlignmentProgressive Alignment:
step
Progressive Alignment:
step3.
G T C C G - - C A G G
T T - C G C - C - G G
A T C - T - - C A A T
C T G - T C C C T A G
A T C T - - C A A T
C T G T C C C T A G
T T A C T T C C A G G
G T C C G - - C A G G
T T - C G C - C - G G
Sub-sequence alignments
A K-means like clustering problem
Clustering resulting model
Clustering predictions
Assignments
•Describe a pairwise alignment with a different gap penalization.
•Provide an example and perform a multiple global alignment. Describe the recipe.
•Provide an example and perform a multiple alignment of subsequences. Describe the recipe.
•Algorithms Order (polynomial, exponential, NP)
Algorithmic Complexity
How does an algorithm‘s performance in CPU time and required memory storage scale with the size of the problem?
Needleman & Wunsch
• Storing (n+1)x(m+1) numbers
• Each number costs a constant number of calculations to compute (three sums and a max)
• Algorithm takes O(nm) memory and O(nm) time
• Since n and m are usually comparable: O(n2)
Gracias porsu atención…
http://www.m4m.es
Recommended