MCB 182 MDT 2

Database: DNA

Query: DNA

Example: Align mRNA to genome

Program: BLASTN

Database: AA (amino acids)

Query: AA

Example: Search for proteins related to your favorite protein

Program: BLASTP

Database: AA

Query: DNA

Example: Find protein-coding exons in a BAC

Program: BLASTX

Database: DNA

Query: AA

Example: Search for transcripts related to your favorite protein

Program: TBLASTN

Database: DNA

Query: DNA

Example: Find orthologous protein-coding exons

Program: TBLASTX

Karlin-Altschul Equation

E=kMNe^-λS

The number of alignments expected by chance (E) is directly…

proportional to the size of the search space (M*N)

The number of alignments expected by chance (E) is inversely….

proportional to the score of the alignment (e^-S)

The closer the E-value is to 1.0…

the worse the alignment (good chance it was produced randomly)

Karlin-Altschul Assumptions

1) A positive score must be possible

2) expected score must be negative

3) sequences are infinitely long

4) Letters are independent and identically distributed

5) Alignments do not contain gaps

You will get more reward (bits)…

the more the scoring system penalizes mismatches relative to matches

Gaps make…

alignments easier. λ should go down.

Why is BLAST more widely used than SW?

• Much faster

• reports all significant alignments rather than one best alignment

• assesses the statistical significance of all alignments

1st Stage of BLAST

• Seeding

  • algorithm finds matching words between 2 sequences

  • Each location in the search space containing a word match is an alignment___

  • most interesting areas of the search space have __ close in proximity

2nd stage of BLAST

• Extension

  • alignments are extended on either side of each seed

  • stops when the quality degrades

  • once score has dropped more than X from previous min., the extension is terminated, and end of alignment end is set to max score

3rd Stage of BLAST

• Evaluation

  • Evaluate the statistical significance of each alignment→ use KA equation to do this

What does a higher value of T indicate?

• T= neighborhood word threshold

• lower T= larger neighborhood, more search space to explore

If X is small in BLAST…

• alignments will terminate quickly

• not necessarily an issue for highly conserved sequences, but for poorly conserved sequences, they can terminate too early.

True positive (TP)

the test says you have COVID & you do

True Negative (TF)

the test says you don't have COVID and you don't

False Positive (FP)

the test says you have COVID & you don't

False Negative (FN)

the test says you don’t have COVID but you do

Sensitivity (true positive rate); want to MAXIMIZE the TP.

TPR= TP/TP+FN

Specificity (true negative rate); focuses on the negatives of the threshold

TNR= TN/TN+FP

Precision (positive predictive value): focuses on the positives of the threshold

PPV= TP/TP+FP

False discovery rate; a low FDR is ideal in a test

FDR= FP/FP+TP

Accuracy (ACC); aggregate of all the terms

ACC= TP+TN/TP+TN+FP+FN

Prosite Patterns

• describes a functional site in a protein using certain rules

• form of regular expression→ may be invented because a certain sequence has a specific function

• no partial matching

• sensitivity and specificity can be thought of as how often it occurs at random

Position Weight Matrices (PWM)

• always ungapped multiple alignments

  • lowercase letters indicate where authors didn’t observe recognizable patterns

• To construct one,

  • choose a length (ex. 6 capital letters)

  • count up letters in each column

• Some can be represented as raw counts or into probabilities→ but often displayed as sequence logs, has to do with information theory (absolute height of each column= 2-H)

PWM Matches

• can match potentially everywhere but to varying degrees→ have to decide what threshold constitutes a match & what values are not worth considering

• Threshold can be given as a probability OR a score

• Lower threshold= increased sensitivity at the cost of specificity and precision

K-Mers

• sequence of letters of size k where k is some integer.

  • Ex. sequence= ACTGGATAC, k=3

  • k-mer 1= ACT

  • k-mer 2= GGA

  • k-mer 3= TAC

• Changing to larger sizes of k= genomes are increasingly different from each other

K-Mer Scoring

S= score

L= length of sequence

k=k-mer size

Obs(i)= probability of observed k-mer at position i

Exp(i)= probability of expected k-mer at position i

• ex. obs of G= 0.3

  • exp. of G= 0.3

  • k-mer= G, score= log2(0.3/0.3)= 0

  • add up all k-mer scores for the sequence to get sum. If sum= positive number, sequence= more likely to be generated from observed model than expected

Intron-Mediated Enhancement (IME)

• phenomenon where introns provide a general increase in expression

• 2 diff. kinds of introns, those near the promoter (proximal) and far away from promoter (distal)

• IMEter= determines if a sequence looks more like a proximal intron (positive score) or distal intron (negative score)

• S= IMEter score

• L=length of intron

• K= k-mer size

• A= length acceptor site

• D= length of donor site

• P= k-mer frequencies in proximal introns

• Q= k-mer frequencies in distal introns

• Pwi= probability of word w at position i in proximal introns

• IMEter score= accurate predictor of how much an intron will improve expression

Markov Models; What is the name of the algorithm that finds the best state path given some observations?

Viterbi Algorithim

What is the name of the database containing multiple alignments and HMMs?

Pfam

In a Profile HMM, what is the probability of emitting a W from an I state?

• typically equal to the background frequency of W in sequence data

In a Profile HMM, what is the probability of emitting a G from a D state?

• 0

• Happens because delete states emit a gap symbol with a probability of 1, and any real sequence probability= 0

In a Profile HMM, what is the probability of emitting a Q from an M state?

• depends on position-specific emission probability distribution from the original multiple sequence alignment

What is different from GHMMs & HMMs?

• In GHMMS, each state emits a sequence of symbols whose length is defined explicitly

• In traditional HMMs, each state emits one symbol