3 - FASTA, BLAST, sequence similarity statistics and homology detection

Question 1

How are FASTA and BLAST different from NW and SW methods?

Answer 1

NW and SW are good for doing pairwise alignments between two sequences of interest.

But it’s way too slow to compare millions of pairwise alignments.

FASTA and BLAST are heuristic methods that can do this, though they are not guaranteed to find the globally optimal alignments (definition of heurisitic)

Though, both FASTA and BLAST are loosely based on the Smith-Waterman algoritithm

Question 2

What is the nr database?

Answer 2

Non-redundant database (non-currated / largest)

Question 3

Give the steps of the FASTA algorithm

Answer 3

1. Makes words of length ktup
2. For each database sequence entry, search for identities of words
3. Rescan top 10 regions with BLOSUM or PAM
4. Trim ends to include only residues contributing to the highest score. Attempt to join together compatible ungapped alignments with gap penalty (initn score).
5. If score is > threshold, perform SW alignment to get optimized score
6. Normalize optimum scores for sequence length (need to correct for longer sequences having increased opt scores). You get a Z score
7. Evaluate statistical significance using the extreme value distribution (E score)

Question 4

List five types of BLAST

Answer 4

• BLASTN
• BLASTP
• BLASTX (nucleotides - AA, tries the 6 different reading frames)
• TBLASTN (protein query against nucleotides translated into protein, for identifying transcripts)
• TBLASTX (Cross species gene prediction at the genome or transcript level, searching for genes missed by traditional methods or not yet in protein database.

Question 5

What does E mean in BLAST/FASTA?

Answer 5

THe expected number of scores equal or greater in identity to the alignment you’ve found.

Question 6

Give the steps of BLAST

Answer 6

1. Seeding
   - FInding matches of ungapped strings
   - Breaking sequences into triplet words
   - Find subs of each word that have similarity scores values >= T (threshold)
   - Stores the set of similar words
   - Searches database sequence for matching words
2. Extension
   - Tries to extend forward and backwards word matches to make longer matches using BLOSUM62 (or another matrix)
   - Alignment is trimmed back to max score
3. Evaluation
   - Is score >S (another threshold), then this High-scoring segment pair (HSP) is saved
   - Attempt to combine consistent HSPs and calculate probability (P(N)) for consistent matches
   - Reports significant HSPs
   - Calculates significance (E-values) for HSPs using Karlin-Altschul statistics (extreme value distribution etc.)

Question 7

How do you tell if an alignment is significant?

Answer 7

Searching a database

• Use the distribution of similarity scores amongst non-hit alignments
• Theory for distribution of ungapped alignment score (Karlin and Altschul statistics)

Single pairwise alignments
- Monte-carlo test to calculate p-value for the real S

Question 8

What is the extreme value distribution?

Answer 8

• Allows calculation of probability of a normalize similarity score for ungapped alignments
• Gives a P-value and E-value (expect value) for a given database

The extreme value distribution is obtained by choosing the largest values from N independent and identically distributed samples from a population.

Question 9

In FASTA and SW, what type of score distributions to you get in the output?

Answer 9

• Expected (E-value)

- Observed (p-value)

Question 10

give the formula for an expect value (E)

Answer 10

E = kmne^-λs

k: constant
m: query sequence length
n: database sequence length
λ: scaling constant
s: SCORE