Matching

Question 1

Why are sequences matched?

Answer 1

Protein sequences are similar between related species

Can transfer knowledge about known sequences to new sequences

Question 2

Alignment

Answer 2

First task after sequencing

Finds best match at DNA and protein level

Question 3

Difference between protein and DNA mutations

Answer 3

Selective pressure affects DNA and proteins differently
Protein mutations - Can lead to in viable offspring - Highly conserved for protein sequences
DNA mutations - Can have more mutations with no changes in function - Less conserved than proteins

Question 4

Conserved Sequences

Answer 4

Conserved:Does not change between different generations, species or even kingdoms
More important sequences are generally more conserved

Question 5

Universally Conserved Sequences

Answer 5

Found in all living things
Proteins for transcription and translation

Conserved from the last “universal common ancestor” of all life

Question 6

Degeneracy in genetic code

Answer 6

Can change whilst still coding for the same amino acid

Question 7

Use of conservation in sequence similarity

Answer 7

More similar amino acids are more likely to be substituted

Used to work out how similar two sequences are

Question 8

Histones

Answer 8

Highly conserved

Involved in DNA replication

Question 9

BLOSOM 50

Answer 9

Block Substitution Matrix
Using known alignments, calculate likelihood that one amino acid is substituted with another

Generated by eliminating sequences with higher than a given similarity
Find frequency of each amino acid combination
Create ratio of occurrences of each of the pairs
Calculate log-odds of each pair - 2 * log of observed\expected (How likely is a match just random chance?)

Each entry in the matrix corresponds to the probability of one amino acid mutating into another

Question 10

Gaps in Sequence Matching

Answer 10

Often good matches are found with insertions/deletions from a string
Linear Model - Poor - Small gaps just as likely as large gaps

Instead use edit distance/levenshtein distance
Local Matching/Global Matching

Question 11

Dynamic programming for inexact string matches

Answer 11

Not possible to exhaustively try all solutions
Build set of optimal partial solutions

Not dynamic or programming

Question 12

Complexity of Dynamic Programming Approach

Answer 12

Need to compute cost at each point in the forward algorithm so O(n^2)
Only one calculation needed at each column in the backward algorithm so O(n)

Brute force method would require O(2^n)

Question 13

Needleman Wunsch

Answer 13

Global alignment
Minimum edit distance between two strings
Assumes linear gap cost for insertions/deletions
Cost of substitutions taken from BLOSOM-50 matrix
Matrix with score for best alignment

Question 14

NW Complexity

Answer 14

Time = Theta(MN) - Not too bad
Space = Theta(MN) - DNA has sequences which are millions of bases long so will become an issue

Question 15

Hirschberg Algorithm

Answer 15

Recursively splits up the matching
Linear in space
Still quadratic in time - Still almost doubles the amount of time needed

Question 16

Differences between global and local matching

Answer 16

Global - Aligning all of the sequences with each other - NW

Local - Only finding the best matching sub sequences - Some sections are accidentally copied - SW

Question 17

Smith-Waterman

Answer 17

Also dynamic programming approach
Adds option of ignoring a match (cost 0) to NW
Optimal for local matching but slow on long strings

Question 18

SW repeated and overlapping matches

Answer 18

SW finds the single best match
SW can also be adapted to deal with this
Unsymmetric as looking for repeats of one section within another.

Question 19

Gaps in local matching

Answer 19

Insertion - Adding another subsequence from elsewhere
Deletion - Jumping bases or treating an exon as an intron

Both of these are rare events but lead to large gaps - Having a linear gap cost is unrealistic

Question 20

Gap cost function evaluated over all previous possible gap sizes

Answer 20

Time Complexity = O(n^3)

Question 21

Affine Gap Cost Function

Answer 21

y(g) = -d - (g-1) e
d = 12 e = 3 gives a good model
Punishes all gaps but larger gaps are punished slightly more
Can be O(n^2)
Requires 3 matrices

Question 22

Affine gap cost function - Finite State Automata

Answer 22

Each state represents a matrix

Possible for an approximation of the affine gap cost with a two state model

Question 23

Inexact matching in practice - Proteins

Answer 23

O(mn) possible - hundreds of amino acids long
Over 200 million sequenced
Difficult to compare sequence with each o ne

Question 24

Inexact matching in practice - DNA

Answer 24

100000 bases long
O(mn) impossible
Need to do approximate matching

Question 25

FASTA

Answer 25

FAST ALL (DNA and Protein alphabets) Not optimal - Use of heuristics so still good Find series of short non-overlapping subsequences known as words Match against database of candidate sequences to find regions with same offset Smith-Waterman against regions found BLAST mostly used now but FASTA file format still used

Question 26

BLAST

Answer 26

Basic Local Alignment Search Tool Not optimal - uses heuristics so still good Removes low complexity/repeated regions K-letter exact matches? Only evaluate most significant matches Find gaps by combining high scoring matches Finishing off with Smith Waterman Need to know how significant matches are

Question 27

Significance Scoring

Answer 27

BLOSOM50 uses log odds ratio For local matching need probability of a match given sequences a and b. Can use bayes rule here EVDs

Question 28

Extreme Value Distributions

Answer 28

How likely it is that a particular score was random rather than due to a match More accurate with longer strings Characterised as a Gumbel distribution