IAE Academy

FOR CORE AND IT JOBS · CHAPTER 3 OF 7

Searching databases with BLAST

This chapter explains why exact alignment cannot scan a whole database, how BLAST finds seeds and extends them, what the five BLAST programs compare, and how to read score, bit score, E-value and percent identity. You need it to judge whether a database hit means anything.

Updated 30 Oct 2026

What you will be able to do

You will be able to explain why a database search cannot fill a full alignment table for every sequence. You will describe how BLAST uses short seeds, hits and extension instead. You will pick the right BLAST program for a query. You will turn a bit score into an E-value, read percent identity and choose a cut-off with care.

Before you start

  1. Chapter 2, Pairwise sequence alignment (substitution matrices, gap scores, local alignment by dynamic programming)

  2. DNA's two strands, their 5' to 3' direction, and codons of three bases

  3. Powers of 2 and of e; logarithms to base e and base 2, with log₂ x = ln x ÷ ln 2

  4. The rule that probabilities of independent events multiply

  5. Expected count = number of tries × probability of success on each try

Why exact search is too slow

Chapter 2 gave you an exact method. Local alignment fills a table with one cell for every pair of positions. That is fine for two sequences. A large database holds millions of sequences, so the same table must be filled against every one of them. BLAST gives up the guarantee of finding the single best alignment in return for finishing in seconds.

COST OF EXACT SEARCH

Holds when one full table is filled per database sequence with no shortcut. m is the query length in residues. N is the total length of all database sequences in residues. Each cell costs a small fixed amount of work.

WORKED EXAMPLE

A protein query has 300 residues. The database holds 10^9 residues in total. A computer fills 10^8 table cells per second. How long does one exact search take?

Solution
  1. Every query position meets every database position once, so cells = 300 × 10^9 = 3 × 10^11.

  2. Time is cells divided by rate: 3 × 10^11 ÷ 10^8 = 3000 s.

  3. 3000 s ÷ 60 = 50 minutes for one query.

  4. Time grows in step with N: twice the database, twice the time. A shared server cannot answer many users this way.

Answer: 3000 s, about 50 minutes per query.

Seeds, hits and extension

Most of a database is unrelated to your query, and BLAST skips it quickly. It cuts the query into short words, called seeds, and stores them in a lookup table. It then reads through the database once. A database word found in the table is a hit. Only around hits does BLAST do alignment work: one hit starts it for DNA, two nearby hits for proteins. It extends left and right, and stops when the score falls too far below its best so far.

NUMBER OF SEED WORDS

Holds when words slide along the query one position at a time. m is the query length in residues. w is the word length, commonly 3 for proteins and 11 for DNA.

RANDOM SEED HITS FOR DNA

Holds for exact word matches on one strand, bases equally likely and independent, N much longer than w. Tries: each of the m − w + 1 query words against each of about N database positions, so (m − w + 1)N tries. Each matches with probability . N is the database length in bases. H is the expected number of chance hits; both strands double it.

PROTEIN SEED RULE

Used for proteins, where similar residues replace each other, so exact matching is too strict. and are the residues at position i of a query word and another word of length w. s is the substitution matrix score from Chapter 2. T is a threshold score the program sets. Words that pass are the query word's neighbouring words.

  1. Seed: cut the query into words of length w. For proteins, the lookup table holds every neighbouring word of each query word.

  2. Hit: read through the database once, looking up each database word in the table. A lookup is far cheaper than a table fill. A hit's diagonal is its database position minus its query position, the same diagonal as in the Chapter 2 table. Hits on one diagonal can lie in one gap-free alignment. For DNA one hit starts an extension; for proteins, two hits on the same diagonal a short distance apart.

  3. Ungapped extension: from the hit, extend both ways adding match and mismatch scores. Stop when the running score falls a set amount below its best so far, and keep the best stretch.

  4. Filter: pass on only ungapped extensions whose score reaches a trigger score the program sets.

  5. Gapped extension: for these, run local dynamic programming as in Chapter 2 outward from the hit, stopping where scores fall too low, so usually only a small part of the table is filled.

  6. Report each local alignment whose E-value is within the cut-off, with its scores.

The five programs differ in which side, if any, is translated to protein before the search. Translation uses the 6 reading frames of DNA: 3 on each strand.

Program

Query

Database

What is compared

blastn

DNA

DNA

Nucleotides directly

blastp

Protein

Protein

Amino acids directly

blastx

DNA, translated in 6 frames

Protein

Translated query against proteins

tblastn

Protein

DNA, translated in 6 frames

Query against translated database

tblastx

DNA, translated in 6 frames

DNA, translated in 6 frames

Both translated: 36 frame pairs

WATCH OUT FOR

A shorter word finds more weak relatives, but random hits rise fast and each costs an extension. Test: w = 11 gives per try and w = 10 gives about , four times more.

Reading a BLAST result

Each reported alignment carries several numbers. The raw score S adds match, mismatch and gap scores, so it depends on the matrix used. The bit score rescales S so scores from different scoring systems can be compared. The E-value is the number of hits at least this good you would expect by chance in a search of this size.

BIT SCORE

Holds for local alignment scores under one fixed matrix and gap penalty. S is the raw score. converts raw score into natural-log units; K is a scale factor for the search space; the program fits both to the scoring system. Dividing by ln 2 turns natural-log units into bits. is in bits.

E-VALUE

Holds for local alignments between unrelated sequences of typical composition, with and K fitted as above. m and N are the query and database lengths in residues, as in the cost formula; the program uses slightly shorter effective lengths, because an alignment cannot start near a sequence's end. Doubling N doubles E. Each extra bit halves E.

CHANCE OF AT LEAST ONE RANDOM HIT

Holds when chance hits arrive independently at an average rate E per search. For E below 0.01, .

PERCENT IDENTITY

The alignment length counts every column, including gaps. It does not say how unlikely the match is, so it cannot replace the E-value.

Read percent identity off the alignment rows. Both rows are written 5' to 3', as all sequences here are, and a dash is a gap.

query  ACGTTGCA-T
hit    ACGATGCAGT

There are 10 columns. Eight hold the same base in both rows; column 4 is a mismatch and column 9 a gap. Identity = 100 × 8 ÷ 10 = 80%. Yet so few columns give a small raw score, so a small bit score, and stays large.

WORKED EXAMPLE

A blastp search of a 300-residue query against a database of 10^9 residues returns two alignments, with bit scores 40 and 50. Find the E-value of each. Which do you keep at a cut-off of 0.001?

Solution
  1. The search space is m × N = 300 × 10^9 = 3 × 10^11, because E counts every query and database position pair. Take the effective lengths as the given lengths, since none are stated.

  2. For 40 bits, work through , so . Since and , . So E = 3 × 10^11 ÷ 1.10 × 10^12 ≈ 0.273, about 0.27.

  3. For 50 bits, , so E ≈ 2.7 × 10^-4. Check: 10 more bits divide E by 1024, and 0.273 ÷ 1024 ≈ 2.7 × 10^-4.

  4. Compare with 0.001. For E = 0.27, , so a hit this good turns up by chance in about a quarter of searches: drop it. An E of 2.7 × 10^-4 is below the cut-off, so keep it.

Answer: E ≈ 0.27 (drop) and E ≈ 2.7 × 10^-4 (keep).

E is counted per search. A cut-off of 0.001 lets through, on average, 0.001 chance hits per search: about one in a thousand searches. Loosen it to 10 to see weak relatives, and expect about 10 chance hits per search among them. Tighten it to to keep only very strong matches, and miss weaker true relatives. The right value depends on whether a missed relative or a false lead costs you more.

WATCH OUT FOR

A low E-value shows the similarity is unlikely to be chance, not that function is shared: the hit may share one domain only, or be a relative whose function changed. Test: does the alignment cover most of the query, and was the hit's function shown by experiment?

Check yourself

CHECK YOURSELF 1

Why is a BLAST search much faster than filling a local alignment table against every database sequence?

  1. (A)

    It aligns only the first word of the query

  2. (B)

    It extends only from short seed hits instead of filling a full table everywhere

  3. (C)

    It uses a smaller substitution matrix

  4. (D)

    It guarantees the best alignment without any table

Answer and solution

Answer: (B)

  1. Exact search fills m × N cells.

  2. BLAST looks up each database word in a table of the query's words and does alignment work only around the hits.

  3. It does not guarantee the best alignment, so D is wrong. Only B states the real saving.

CHECK YOURSELF 2

A blastp search has a 200-residue query and a database of 5 × 10^8 residues; take these as the effective lengths. An alignment has a bit score of 45. Take . Find the E-value, to four decimal places.

Answer and solution

Answer: (accepted range )

  1. .

  2. m N = 200 × 5 × 10^8 = 10^11.

  3. E = 10^11 ÷ 3.518 × 10^13 ≈ 0.00284, which is 0.0028 to four decimal places.

CHECK YOURSELF 3One or more options are correct

Which statements are correct for a BLAST E-value?

  1. (A)

    For the same bit score, doubling the database size doubles E

  2. (B)

    One extra bit of score halves E

  3. (C)

    An E-value of 0.001 proves the hit has the same function as the query

  4. (D)

    It is the number of hits with at least this score expected by chance in a search of this size

Answer and solution

Answer: (A), (B), (D)

  1. , so E is proportional to N (A true).

  2. Raising by 1 multiplies E by 1/2 (B true).

  3. A low E-value shows the match is unlikely to be chance, not that function is shared (C false).

  4. D is the definition of the E-value.

CHECK YOURSELF 4

You hold a protein sequence and want to find regions that may encode related proteins in a DNA database that has not been annotated. Which program do you use?

  1. (A)

    blastn

  2. (B)

    blastp

  3. (C)

    blastx

  4. (D)

    tblastn

Answer and solution

Answer: (D)

  1. The query is protein and the database is DNA.

  2. tblastn translates the database in 6 frames and compares the protein against it.

  3. blastx does the reverse: a translated DNA query against proteins.

Used in these GATE topics