Transcript Analysis of Sequences IV

Mark Gerstein, Yale University
GersteinLab.org/courses/452
(last edit in fall '05)
1 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
BIOINFORMATICS
Sequences #2
• Basic Alignment via Dynamic
Programming
• Suboptimal Alignment
• Gap Penalties
• Similarity (PAM) Matrices
• Multiple Alignment
• Profiles, Motifs, HMMs
• Local Alignment
• Probabilistic Scoring
Schemes
• Rapid Similarity Search:
Fasta
• Rapid Similarity Search: Blast
• Practical Suggestions on
Sequence Searching
• Transmembrane helix
predictions
• Secondary Structure
Prediction: Basic GOR
• Secondary Structure
Prediction: Other Methods
• Assessing Secondary
Structure Prediction
2 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Sequence Topics (Contents)
3 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Computational Complexity
Computational Complexity
• Basic NW Algorithm is
O(n2) (in speed)
• O(n2) in memory too!
• Improvements can
(effectively) reduce
sequence comparison to
O(n) in both
N
A
A
B
C
N
R
Q
C
L
C
R
P
M
1
Y
1
C
1
1
Y
1
1
N
M
Y
1
R
5
4
3
3
2
2
0
0
C
3
3
4
3
3
3
3
4
3
3
1
0
0
K
3
3
3
3
3
3
3
3
3
2
1
0
0
C
2
2
3
2
2
2
2
3
2
3
1
0
0
R
2
1
1
1
1
2
1
1
1
1
2
0
0
B
1
2
1
1
1
1
1
1
1
1
1
0
0
P
0
0
0
0
0
0
0
0
0
0
0
1
0
N’
4 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
 M x N squares to fill
 At each square need to
look back (M’+N’) “black”
squares to find max in block
 M x N x (M’+N’) -> O(n3)
 However, max values in
block can be cached, so
algorithm is really only
O(n2)
Cor
e
M’
5 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
How normal dynamic programming
without caching has O(N3) complexity
6 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Rapid Similarity Search:
FASTA and BLAST
Cor
e
Hash table of short words in the query sequence
Go through DB and look for matches in the query
hash (linear in size of DB)
perl: $where{“ACT”} = 1,45,67,23....
K-tuple determines word size (k-tup 1 is single aa)
by Bill Pearson & D Lipman
VLICT =
•
•
•
•
•
_
VLICTAVLMVLICTAAAVLICTMSDFFD
7 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
FASTA
(adapted from R Altman)
8 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
A More Interesting Dot Matrix
(Adapted from D Brutlag)
9 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Join together query
lookups into
diagonals and then
a full alignment
(m-7)
10 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
End of class 2005,11.07
Basic
Blast
Cor
e
11 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
• Altschul, S., Gish, W., Miller, W., Myers, E. W.
& Lipman, D. J. (1990). Basic local alignment
search tool. J. Mol. Biol. 215, 403-410
• Indexes query (also tried indexing DB [blat])
• Starts with all overlapping words from query
• Calculates “neighborhood” of each word
using PAM matrix and probability threshold
matrix and probability threshold
• Looks up all words and neighbors from query
in database index
• Extends High Scoring Pairs (HSPs) left and
right to maximal length [Pure hashing type of
approach]
• Finds Maximal Segment Pairs (MSPs)
between query and database
• Blast 1 does not permit gaps in alignments
Cor
e
• Extend hash hits into
High Scoring Segment
Pairs (HSPs)
• Stop extension when
total score doesn’t
increase
• Extension is O(N). This
takes most of the time
in Blast
12 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Blast: Extension
of Hash Hits
Blasting
against
the DB
Number of
hash hits is
proportional
to O(N*M*D),
where N is
the query
size, M is the
average DB
seq. size, and
D is the size
of the DB
13 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
• In simplest Blast algorithm, find best scoring segment in each
DB sequence
• Statistics of these scores determine significance
Analytic Score Formalism for Blast
Extra
14 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Karlin-Altschul statistics for occurrence of highscoring segments (HSPs) in random sequences
Cor
e
15 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Blast2:
Gapped
Blast
• Gapped Extension on
Diagonals with two Hash
Hits
• Statistics of Gapped
Alignments follows EVD
empirically
Cor
e
16 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Blast2:
Gapped Blast
Automatically builds
profile and then
searches with this
Also PHI-blast
17 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Y-Blast
Parameters: overall •
threshold, inclusion
threshold, interations
•
Speed
Iteration
Scheme
Sensitivity
Cor
e
Blast
FASTA
SmithWaterman
PSI-Blast
Profiles
HMMs
18 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
PSI-Blast
19 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Sequence Searching Issues
(graphic and some text adapted from D
Brutlag)
• Search both strands
• Protein search is more sensitive
than nuc. acid, Translate ORFs
(codons & subst. matrices)
• BLAST for infinite gap penalty
• Smith-Waterman for
cDNA/genome comparisons
• cDNA =>Zero gap-Transition
matrices Consider transition
matrices
• Ensure that expected value of
score is negative
20 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Practical
Issues on
DNA
Searching
• Examine results with exp. between 0.05
and 10
• Reevaluate results of borderline
significance using limited query
• Beware of hits on long sequences
• Limit query length to 1,000 bases
• Segment query if more than 1,000 bases
• Choose between local or
global search algorithms
• Use most sensitive search
algorithm available
• Original BLAST for no gaps
• Smith-Waterman for most
sensitivity
• FASTA with k-tuple 1 is a
good compromise
• Gapped BLAST for well
delimited regions
• PSI-BLAST for families
• Initially BLOSUM62 and
default gap penalties
(some text adapted from D Brutlag)
21 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
General Protein
Search Principles
• If no significant results, use
BLOSUM30 and lower gap
penalties
• FASTA e-value cutoff of .01
• Blast p-value cutoff of .0001
• Examine results between exp.
0.05 and 10 for biological
significance
• Ensure expected score is
negative
• Beware of hits on long
sequences or hits with unusual
aa composition
• Reevaluate results of borderline
significance using limited query
region
• Segment long queries 300
amino acids
• Segment around known motifs
• The Significance of Similarity Scores Decreases with
Database Growth




The score between any pair of sequence pair is constant
The number of database entries grows exponentially
The number of nonhomologous entries >> homologous entries
Greater sensitivity is required to detect homologies
Greater s
• Score of 100 might rank as best in database of 1000
but only in top-100 of database of 1000000
DB-3
QUERY
DB-1
DB-2
22 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Significance Depends
on Database Size
• Low Complexity Regions
 Different Statistics for matching
AAATTTAAATTTAAATTTAAATTTAAATTT
than
ACSQRPLRVSHRSENCVASNKPQLVKLMTHVKDFCV
 Automatic Programs Screen These Out (SEG)
Cor
e
 Identify through computation of sequence entropy in a window of a
given size
H =  f(a) log2 f(a)
• Also, Compositional Bias
 Matching A-rich query to A-rich DB vs. A-poor DB
LLLLLLLLLLLLL
23 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Low-Complexity Regions
Extra
(threading)
HMMs
24 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Sequence Searching History
• Why interesting?
 Not tremendous success, but many methods brought to bear.
 What does difficulty tell about protein structure?
• Start with TM Prediction (Simpler)
• Basic GOR Sec. Struc. Prediction
• Better GOR
 GOR III, IV, semi-parametric improvements, DSC
• Other Methods
 NN, nearest nbr.
25 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Secondary Structure Prediction Overview
Credits: Rost et al. 1993;
Fasman & Gilbert, 1990
• Not Same as Tertiary
Structure Prediction -- no
coordinates
• Need torsion angles of
terms + slight diff. in
torsions of sec. str.
Sequence
Structure
RPDFCLEPPYTGPCKARIIRYFYNAKAGLVQTFVYGGCRAKRNNFKSAEDAMRTCGGA
CCGGGGCCCCCCCCCCCEEEEEEETTTTEEEEEEECCCCCTTTTBTTHHHHHHHHHCC
26 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
What secondary
structure
prediction tries
to accomplish?
27 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
TM Helix Identification: the Problem
• Transmembrane segments can be identified by using
the GES hydrophobicity scale (Engelman et al., 1986).
The values from the scale for amino acids in a window
of size 20 (the typical size of a transmembrane helix)
were averaged and then compared against a cutoff of
-1 kcal/mole. A value under this cutoff was taken to
indicate the existence of a transmembrane helix.
• H-19(i) = [ H(i-9)+H(i-8)+...+H(i) + H(i+1) + H(i+2) + . .
. + H(i+9) ] / 19
Cor
e
28 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
How to use GES to predict proteins
-3.7
-3.4
-3.1
-2.8
-2.6
-2.0
-1.9
-1.6
-1.2
-1.0
-0.6
+0.2
+0.7
+3.0
+4.1
+4.8
+8.2
+8.8
+9.2
+12.3
Goldman, Engleman, Steitz
KD – Kyte Dolittle
For instance, DG from
transfer of a Phe
amino acid from water
to hexane
I
V
L
F
C
M
A
G
T
W
S
Y
P
H
E
Q
D
N
K
R
4.5
4.2
3.8
2.8
2.5
1.9
1.8
-0.4
-0.7
-0.9
-0.8
-1.3
-1.6
-3.2
-3.5
-3.5
-3.5
-3.5
-3.9
-4.5
29 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
F
M
I
L
V
C
W
A
T
G
S
P
Y
H
Q
N
E
K
D
R
Some TM scales:
GES
KD
Cor
e
30 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Graph showing
Peaks in scales
Illustrations Adapted From: von
Heijne, 1992; Smith notes, 1997
31 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Basic Ideas
• f(aa x,obs [in TM
helix]) / f(aa x, exp
[from DB])
• Substitution
matrices
• Pseudo E = Log
obs/exp
• Window averaging
with log obs/exp
instead of dG
(GES)
• Refinements:
F(x, obs in TM
helix at the n-term
position)
(m-8)
32 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
End of class 2005,11.09
• Propensity P(A) for amino
acid A to be in the middle
of a TM helix or near the
edge of a TM helix
Cor
e
n( A, TM )
n( A, TM )

A
P ( A) 
n( A, everywhere )
 A n( A, everywhere )
Illustration Credits: Persson & Argos, 1994
P(A) = fTM(A)/fSwissProt(A)
33 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Statistics Based Methods:
Persson & Argos
Extra
34 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Scale Detail
Extra
• How to train to find right
threshold? Not that many TM
helices
• Marginal TM helices are not that
hydrophobic but 1/3 of TM's are
very hydrophobic, so focus on
these.
•Sosui, Klein &
Delisi, Boyd
•Discriminant
Soluble
analysis: set
threshold to be best
partition of dataset
TM
Solb
Marginal
TM
2.5%
2.0%
1.5%
1.0%
Thresholds
0.5%
2500
0.50
0.25
0.00
-0.25
-0.50
-0.75
-1.00
-1.25
-1.50
-1.75
-2.00
-2.25
-2.50
-2.75
0.0%
Number of Worm ORFs
2000
-3.00
Freq. in worm genome
3.0%
marginal
sure
1500
1000
500
Min H value
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Number of TM helices per ORF
35 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Refinements:
MaxH
36 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Secondary Struc. Prediction: GOR
Cor
e
• For independent events just add up the information
• I(Sj ; R1, R2, R3,...Rlast) = Information that first through
last residue of protein has on the conformation of
residue j (Sj)
 Could get this just from sequence sim. or if same struc. in DB
(homology best way to predict sec. struc.!)
• Simplify using a 17 residue window:
I(Sj=H ; R[j-8], R[j-7], ...., R[j], .... R[j+8])
• Difference of information for residue to be in helix
relative to not: I(dSj;y) = I(Sj=H;y)-I(Sj=~H;y)
 odds ratio: I(dSj;y)= ln P(Sj;y)/P(~Sj;y)
 I determined by observing counts in the DB, essentially a lod value
37 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
GOR: Simplifications
 I(Sj,R[j+m]) = information that residue at position m in
window has about conformation of protein at position j
 1020 bins=17*20*3
• In Words
 Secondary structure prediction can be done using the
GOR program (Garnier et al., 1996; Garnier et al., 1978;
Gibrat et al., 1987). This is a well-established and
commonly used method. It is statistically based so that the
-8
0 3
+8
prediction for a particular residue (say Ala) to be in a given
state (i.e. helix) is directly based on the frequency that this
residue (and taking into account neighbors at +/- 1, +/- 2,
and so forth) occurs in this state in a database of solved
structures. Specifically, for version II of the GOR program
f(H,+3)/f(~H,+3) (Garnier et al., 1978), the prediction for residue i is based
on a window from i-8 to i+8 around i, and within this
window, the 17 individual residue frequencies (singlets).
38 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Basic
GOR
• Pain & Robson, 1971;
Garnier, Osguthorpe, Robson, 1978
• I ~ sum of I(Sj,R[j+m]) over 17 residue window
centered on j and indexed by m
39 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Overview of variables in simple GOR
OBS
LOD= ln ------EXP
helix
strand
coil
Credits: King & Sternberg, 1996
Cor
40 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Directional
Information
Credits: King &
Sternberg, 1996
•
•
•
•
Group I favorable residues and Group II unfavorable one:
A, E, L -> H; V, I, Y, W, C -> E; G, N, D, S -> C
Cor
P complex; largest effect on proceeding residue
e
Some residues favorable at only one terminus (K)
41 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Types of
Residues
• I(Sj; R[j+m], R[j+n]) = the frequencies of all 136
(=16*17/2) possible di-residue pairs (doublets) in the
window.
 20*20*3*16*17/2=163200 pairs
• Parameter Explosion Problem: 1000 dom. struc. * 100
res./dom. = 100k counts, over how many bins
• Dummy counts for low values (Bayes)
Cor
e
All Singletons in 17
residue window
All Pairs
42 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
GOR IV
Cor
e
43 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
How to calculate an entry in the GOR I
tables and a comparison to GOR IV
Simple - 20 values at position i
Gor I - ~1000 values within 17 res window at i
Gor IV ~ 160K, all pairs within the window
(bin = how many times do I have a helix at i with A at
position m=5 and V at position n=-4)
GOR-2010 -- bigger window, triplets!!
GOR-5000 -- all 15mer words, 20^15!!
44 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Spectrum of calculations
Also, why
secondary
structure
prediction is so
hard
Cor
e
45 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
An
example
of miniGOR
• AASDTLVVIPWERE
• HHHHHEEEECCCHH
• Hhhheeeeeeeech
Input Seq
Pred.
Gold Std.
46 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
How to set up assessment
PPV = number get right / number things you predict
Roc curve = number right / number of known positives
• Q3 + other assess, 3x3
• Q3 = total number of
residues predicted correctly
over total number of
residues (PPV)
• GOR gets 65%
 sum of diagonal over total number
of residue -- (14K+5K+21K)/ 64K
• Under predict strands & to a
lesser degree, helices: 5.9 v
4.1, 10.9 v 10.6
Credits: Garnier et al., 1996
47 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Assessment
• Cross Validation:
Leave one out,
seven-fold
4-fold
Credits: Munson,
1995;
Garnier et al., 1996
48 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Training and
Testing Set
• Parametric Statistical
 struc. = explicit numerical func. of the data (GOR)
• Non-parametric
 struc. = NON- explicit numerical func. of the data
 generalize Neural Net, seq patterns, nearest nbr, &c.
• Semi-parametric: combine both
• single sequence
• multi sequence
 with or without multiple-alignment
Cor
e
49 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Types of Secondary Structure
Prediction Methods
• Filtering
GOR to
regularize
Cor
e
Illustration Credits: King & Sternberg, 1996
50 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
GOR Semiparametric
Improvements
• Average GOR
over multiple seq.
Alignment
• The GOR method only uses
single sequence information
and because of this achieves
lower accuracy (65 versus >71
%) than the current "state-ofthe-art" methods that
incorporate multiple sequence
information (e.g. King &
Sternberg, 1996; Rost, 1996;
Rost & Sander, 1993).
Illustration Credits: Livingston &
Barton, 1996
51 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Multiple
Sequence
Methods
 dist from C-term, Nterm
 insertions/deletes
 overall composition
 hydrophobic
moments
 autocorrelate: helices
 conservation moment
Illustration Credits: King & Sternberg, 1996
52 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
DSC -- an
improvement on
GOR
• GOR parms
• + simple linear
discriminant
analysis on:
Conservation, k-nn
Extra
Patterns of
Conservation
Inside (conserved)
k-nearest
neighbors
53 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
outside
• Neural networks
• struc class predict
 Vect dist. between composition vectors
•
•
•
•
threading via pair pot
Distant seq comparison
ab initio from md
ab initio from pair pot.
Extra
54 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Yet more methods….
55 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Threading
Query sequence
Library of known folds
Best-fit fold
56 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Fold recognition
• Structure prediction made easier by sampling
1,000~10,000 folds, rather than >4100 possible
conformations
• Practical importance: fold assignment in genomes
• Fold recognition can be done using sequence-based
(BLAST, HMM, profile alignment) or structure-based
methods (threading)
57 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Why fold recognition?
• Input: A query sequence, a fold library
• For each fold template in the library:
 Generate alignments between the query sequence and the fold
template
 Evaluate alignments; choose the best one
• Do this for all folds, choose the best fold
58 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Fold recognition by threading
• Query sequence:
• Thread the sequence onto
the fold template
• Use structural properties to
evaluate the fit
 Environment
 Pairwise interactions
59 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
What is threading
(m-9)
[lectures continue
in structures sections]
60 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
End of class 2005,11.14
● Align:
to:
RVLGFIPTWFALSKY
Many possible alignments:
V
R
L
S
R
L
G
A
K
V
I
F
F
Y
P
T
W
2
1
12
13
3
4
11
14
6
5
10
15
7
8
9
16
A
L
A
L
V
R
F
S
L
F
S
L
G
W
K
F
G
W
K
F
T
Y
I
P
T
Y
I
P
1234567890123456
1234567890123456
123456789012--3456
RVLGFIPTWFALSKY-
-RVLGFIPTWFALSKY
RVLGF--IPTWFALSKY-
Deletion
Insertion
61 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Align sequence to fold: an example
Evaluate alignments using threading
energy function
• Eenv: Total environment energies. Measures compatibility of
a residue and its corresponding 3D environment (secondary
structure, solvent accessibility)
• Epair: Total pairwise energies. Measures interaction
between spatially close residues
• Egap: Gap opening and extension penalities
• Etot represents how compatible a sequence in a given
alignment is to structural model represented in terms of
environments and pairpot.
62 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
• Etotal = Eenv + Epair + Egap
• Optimum E tot is arrived through a sort of dyn.
programming against the model…
63 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Pairwise and Environment Energies
Generalized Substitution matrix
M(env=buried,aa=Met)=+2 (complementary)
64 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Generalized Substitution Matrices
i
• PAM(A,V) = 0.5
1
 Applies at every position
1
• S(aa @ i, aa @ J)
2
 Specific Matrix for each pair of
residues
i in protein 1 and
J in protein 2
 Example is Y near N-term.
matches any C-term. residue (Y
at J=2)
3
4
5
6
7
8
9
• S(i,J)
 Doesn’t need to depend on a.a.
identities at all!
 Just need to make up a score
for matching residue i in protein
1 with residue J in protein 2
10
11
12
J
2
A B
A 1
Y
C
Y
N
R
C
K
C
R
B
1
P
3
4
5
6
7
8
9 10 11 12 13
C N Y R Q C L C R P M
1
5 5 5 5 5 5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
65 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Structural Alignment (1b)
Make a Similarity Matrix
(Generalized Similarity Matrix)
66 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Using Dynamic Programming in
Threading
• NP-hard problem; needs approximation
• Dynamic programming and the
“frozen approximation”
 Approximately calculate amino acid preferences for each residue position by
fixing the interaction partners at that position
 Find best alignment using dynamic programming
 Update interaction partners for each position; repeat till convergence
• Other optimization techniques
 Simulated annealing
 Branch-and-bound, etc.
67 (c) Mark Gerstein, 2005, Yale, bioinfo.mbb.yale.edu
Find the best alignment