Bioinformatics

Scoring Matrices

David Gilbert
Bioinformatics Research Centre
[Link]
Department of Computing Science, University of Glasgow
 Scoring Matrices
• Learning Objectives
– To explain the requirement for a scoring system reflecting
possible biological relationships
– To describe the development of PAM scoring matrices
– To describe the development of BLOSUM scoring
matrices

(c) David Gilbert 2008 Scoring matrices 2

 Scoring Matrices
• Database search to identify homologous sequences based on
similarity scores

• Ignore position of symbols when scoring

• Similarity scores are additive over positions on each sequence

to enable DP

• Scores for each possible pairing, e.g. proteins composed of 20

amino acids, 20 x 20 scoring matrix

(c) David Gilbert 2008 Scoring matrices 3

 Scoring Matrices
• Scoring matrix should reflect
– Degree of biological relationship between the amino-acids
or nucleotides
– The probability that two AA’s occur in homologous
positions in sequences that share a common ancestor
• Or that one sequence is the ancestor of the other

• Scoring schemes based on physico-chemical

properties also proposed

(c) David Gilbert 2008 Scoring matrices 4

 Scoring Matrices
• Use of Identity
– Unequal AA’s score zero, equal AA’s score 1. Overall score can then
be normalised by length of sequences to provide percentage identity

• Use of Genetic Code

– How many mutations required in NA’s to transform one AA to
another
• Phe (Codes UUU & UUC) to Asn (AAU, AAC)

• Use of AA Classification
– Similarity based on properties such as charge, acidic/basic,
hydrophobicity, etc

(c) David Gilbert 2008 Scoring matrices 5

 Scoring Matrices
• Scoring matrices should be developed from
experimental data
– Reflecting the kind of relationships occurring in nature

• Point Accepted Mutation (PAM) matrices

– Dayhoff (1978)
– Estimated substitution probabilities
– Using known mutational (substitution) histories

(c) David Gilbert 2008 Scoring matrices 6

 Scoring Matrices
• Dayhoff employed 71 groups of near homologous sequences
(>85% identity)
• For each group a phylogenetic tree constructed
• Mutations accepted by species are estimated
– New AA must have similar functional characteristics to one replaced
– Requires strong physico-chemical similarity
– Dependent on how critical position of AA is to protein
• Employs time intervals based on number of mutations per
residue

(c) David Gilbert 2008 Scoring matrices 7

 Scoring Matrices
Overall Dayhoff Procedure:-
• Divide set of sequences into groups of similar sequences –
multiple alignment for each group
• Construct phylogenetic tree for each group
• Define evolutionary model to explain evolution
• Construct substitution matrices
– The substitution matrix for an evolutionary time interval t gives for each
pair of AA (a, b) an estimate for the probability of a to mutate to b in a
time interval t.

(c) David Gilbert 2008 Scoring matrices 8

 Scoring Matrices
• Evolutionary Model
– Assumptions : The probability of a mutation in one position of a sequence is
only dependent on which AA is in the position
– Independent of position and neighbour AA’s
– Independent of previous mutations in the position

• No need to consider position of AA’s in sequence

• Biological clock – rate of mutations constant over time

– Time of evolution measured by number of mutations observed in given number
of AA’s. 1-PAM = one accepted mutation per 100 residues

(c) David Gilbert 2008 Scoring matrices 9

 Scoring Matrices
• Calculating Substitution Matrix – count number of
accepted mutations

ACGH DKGH DDIL CKIL

C-K D-A D-K C-A A C D G H I K L

D-A A 1 2
C 1 1
AKGH AKIL D 2 1
G-I
G 1
H-L H 1
I 1
K 1 1
L 1

(c) David Gilbert 2008 Scoring matrices 10

 Scoring Matrices
• Once all accepted mutations identified calculate
– The number of a to b or b to a mutations from table – denoted as fab
– The total number of mutations in which a takes part – denoted as fa = Σb≠a fab
– The total number of mutations f =Σa fa (each mutation counted twice)

• Calculate relative occurrence of AA’s

– pa where Σa pa = 1

(c) David Gilbert 2008 Scoring matrices 11

 Scoring Matrices
• Calculate the relative mutability for each AA
– Measure of probability that a will mutate in the evolutionary time being
considered
• Mutability depends on fa
– As fa increases so should mutability ma ; AA occurring in many mutations
indicates high mutability
– As pa increases mutability should decrease ; many occurrences of AA indicate
many mutations due to frequent occurrence of AA
• Mutability can be defined as ma = K fa / pa where K is a constant

(c) David Gilbert 2008 Scoring matrices 12

 Scoring Matrices
• Probability that an arbitrary mutation contains a
– 2fa / f
• Probability that an arbitrary mutation is from a
– fa / f
• For 100 AA’s there are 100pa occurrences of a
• Probability to select a 1/ 100pa
• Probability of any of a to mutate
– ma = (1/ 100pa ) x (fa / f)
• Probability that a mutates in 1 PAM time unit defined by ma

(c) David Gilbert 2008 Scoring matrices 13

 Scoring Matrices
• Probability that a mutates to b given that a mutates is fab / fa
• Probability that a mutates to b in time t = 1 PAM
– Mab = mafab / fa when a ≠ b
X=0
C 12
S 0 2
T -2 1 3
P -3 1 0 6 Log-odds PAM 250 matrix
A -2 1 1 1 2
G -3 1 0 -1 1 5
N -4 1 0 -1 0 0 2
D -5 0 0 -1 0 1 2 4
E -5 0 0 -1 0 0 1 3 4
Q -5 -1 -1 0 0 -1 1 2 2 4
H -3 -1 -1 0 -1 -2 2 1 1 3 6
R -4 0 -1 0 -2 -3 0 -1 -1 1 2 6
K -5 0 0 -1 -1 -2 1 0 0 1 0 3 5
M -5 -2 -1 -2 -1 -3 -2 -3 -2 -1 -2 0 0 6
I -2 -1 0 -2 -1 -3 -2 -2 -2 -2 -2 -2 -2 2 5
L -6 -3 -2 -3 -2 -4 -3 -4 -3 -2 -2 -3 -3 4 2 6
V -2 -1 0 -1 0 -1 -2 -2 -2 -2 -2 -2 -2 2 4 2 4
F -4 -3 -3 -5 -4 -5 -4 -6 -5 -5 -2 -4 -5 0 1 2 -1 9
W 0 -3 -3 -5 -3 -5 -2 -4 -4 -4 0 -4 -4 -2 -1 -1 -2 7 10
Y -8 -2 -5 -6 -6 -7 -4 -7 -7 -5 -3 2 -3 -4 -5 -2 -6 0 0 17
C S T P A G N D E Q H R K M I L V F W Y

(c) David Gilbert 2008 Scoring matrices 14

 Dayhoff mutation matrix (1978) - summary
• Point Accepted Mutation (PAM)
• Dayhof matrices derived from sequences 85% identical
• Evolutionary distance of 1 PAM = probability of 1 point mutation per 100 residues
• Likelihood (odds) ratio for residues a and b :
Probability a-b is a mutation / probability a-b is chance
• PAM matrices contain log-odds figures
val > 0 : likely mutation
val = 0 : random mutation
vak < 0 : unlikely mutation
• 250 PAM : similarity scores equivalent to 20% identity
• low PAM - good for finding short, strong local similarities
high PAM = long weak similarities

(c) David Gilbert 2008 Scoring matrices 15

 Scoring Matrices
• What about longer evolutionary times ?
• Consider two mutation periods 2-PAM
– a is mutated to b in first period and unchanged in second
• Probability is Mab Mbb
– a is unchanged in first period but mutated to b in the second
• Probability is Maa Mab
– a is mutated to c in the first which is mutated to b in the second
• Probability is Mac Mcb
• Final probability for a to be replaced with b
– M2ab = Mab Mbb + Maa Mab + Σ c≠a,b Mac Mcb = Σ c Mac Mcb

(c) David Gilbert 2008 Scoring matrices 16

 Scoring Matrices
• Simple definition of matrix multiplication
– M2ab = Σ c Mac Mcb
– M3ab = Σ c M2ac Mcb etc

• Typically M40 M120 M160 M250 are used in scoring

• Low values find short local alignments, High values find longer and weaker
alignments

• Two AA’s can be opposite in alignment not as a results of homology but by pure
chance

• Need to use odds-ratio Oab = Mab / Pb (Use of Log)

– Oab > 1 : b replaces a more often in bologically related sequences than in random
sequences where b occurs with probability Pb
– Oab < 1 : b replaces a less often in bologically related sequences than in random
sequences where b occurs with probability Pb
(c) David Gilbert 2008 Scoring matrices 17
 BLOSUM Scoring Matrices
• PAM matrices derived from sequences with at least 85%
identity
• Alignments usually performed on sequences with less
similarity
• Henikoff & Henikoff (1992) develop scoring system based on
more diverse sequences
• BLOSUM – BLOcks SUbstitution Matrix
• Blocks defined as ungapped regions of aligned AA’s from
related proteins
• Employed > 2000 blocks to derive scoring matrix

(c) David Gilbert 2008 Scoring matrices 18

 BLOSUM Scoring Matrices
• Statistics of occurrence of AA pairs obtained

• As with PAM frequency of co-occurrence of AA pairs

and individual AA’s employed to derive Odds ratio

• BLOSUM matrices for different evolutionary

distances
– Unlike PAM cannot derive direct from original matrix
– Scoring Matrices derived from Blocks with differing levels
of identity

(c) David Gilbert 2008 Scoring matrices 19

 BLOSUM Scoring Matrices
• Overall procedure to develop a BLOSUM X matrix
– Collect a set of multiple alignments
– Find the Blocks (no gaps)
– Group segments of Blocks with X% identity
– Count the occurrence of all pairs of AA’s
– Employ these counts to obtain odds ratio (log)

• Most common BLOSUM matrices are 45, 62 & 80

(c) David Gilbert 2008 Scoring matrices 20

 Scoring Matrices
• Differences between PAM & BLOSUM
– PAM based on predictions of mutations when proteins diverge
from common ancestor – explicit evolutionary model
– BLOSUM based on common regions (BLOCKS) in protein
families
• BLOSUM better designed to find conserved domains
• BLOSUM - Much larger data set used than for the PAM matrix
• BLOSUM matrices with small percentage correspond to PAM
with large evolutionary distances
– BLOSUM64 is roughly equivalent to PAM 120

(c) David Gilbert 2008 Scoring matrices 21