LSMA

LONDON SCHOOL OF MULTIOMICS & AI

Free course

Free course

0 of 73 lessons

Lesson 5 of 9

Module 4 · Comparing sequences

Searching databases fast

Searching databases fast

Searching databases fast

BLAST finds relatives of a sequence among hundreds of millions in seconds. Learn how its word seeds work, what an E-value means, and how to read a results page.

⏱ 17 min readModule 4 · Comparing sequencesFree
Lesson at a glance6 steps · about 17 min
  1. Why searching needs a shortcut
  2. How BLAST works: seeds, extension, score
  3. E-values: how surprised should you be?
  4. The seed idea in Python
  5. Reading a web BLAST results page
  6. Choosing blastn, blastp or blastx

Why searching needs a shortcut

In Global and local alignment, without heavy maths you aligned two sequences with PairwiseAligner. It tries every way of lining them up and is guaranteed to find the best-scoring alignment. That is fine for two proteins. A public database, though, holds hundreds of millions of sequences, and comparing your query with every one of them in full would take far too long for a search you want back in seconds.

The answer is a heuristic: a method that takes sensible shortcuts and finds the right answer nearly every time, without the guarantee. The best-known heuristic search tool is BLAST, the Basic Local Alignment Search Tool. It finds local alignments (Global and local alignment, without heavy maths): the best-matching stretches, rather than the two sequences end to end. That suits searching, because a query often shares only one domain or one region with a database entry.

BLAST answers a similarity question: which entries look like my query, and how unlikely is that resemblance by chance? From strong, unlikely similarity you can infer homology, shared ancestry, as Why compare sequences: homology, similarity and identity explained. The search itself never proves ancestry; it gives you the evidence.

How BLAST works: seeds, extension, score

The idea rests on one observation. Two truly related sequences almost always share at least one short stretch that matches well. So instead of aligning everything, BLAST first looks for those short stretches and spends its effort only where it finds them.

  • Words. The query is cut into short overlapping pieces called words, or k-mers, where k is the word length. For proteins the usual length is 3 letters. For DNA it is longer, 11 letters in standard blastn and 28 in megablast, because DNA has only four letters and short DNA words match by chance far too often.
  • Neighbourhood words. For proteins, BLAST does not only look for exact copies of each word. Using a scoring matrix such as BLOSUM62 (Scoring matrices: PAM and BLOSUM), it also lists similar words whose score passes a threshold, so that VHL can also find IHL. This makes the search more sensitive to distant relatives.
  • The word-length trade-off. Shorter words and lower neighbourhood thresholds give more seeds, so fewer real relatives are missed, but the search slows down because there are more seeds to extend. Longer words are faster and miss more. Megablast's long words are why it is the quick choice for finding near-identical DNA, and why it is a poor choice for distant relatives.
  • Seeds. The database has been indexed ahead of time, so BLAST can look up at once where each word occurs. Each place where a query word lands on a database sequence is a seed, or hit.
  • Extension. From each seed, BLAST grows the match outwards in both directions, adding the score of each new pair of letters. It stops when the running score has fallen too far below the best score seen so far. This cut-off is called the X-drop. Promising matches are then extended again with gaps allowed, using the same kind of alignment you met in Global and local alignment, without heavy maths, but only in that small region.
  • Score. The final alignment has a raw score, the sum from the scoring matrix and gap penalties. BLAST converts it to a bit score, which is adjusted for the scoring system so that scores from different searches can be compared, and then to an E-value.
Searching databases fast: similarity search and E-values · LSMA free course Four cards from left to right. One: the query MVHLTPEEK is cut into overlapping three-letter words such as MVH, VHL and HLT. Two: each word is looked up in an index of the database, and the places it lands are seeds. Three: each seed is extended in both directions until the score drops too far, then refined with gaps. Four: the final score becomes a bit score and an E-value, and only hits with a small E-value are reported. A bar underneath shows the work shrinking from the whole database to a few hits. 1 · WORDS 2 · SEEDS 3 · EXTEND 4 · SCORE MVHLTPEEK MVH VHL HLT LTP … overlapping 3-letter words word lookups in an index grow both ways stop when score drops raw score bit score E-value report small E only HOW MUCH IS LOOKED AT whole database a few hits, each fully scored
The four steps of a BLAST search. Most of the database is never aligned at all; only regions with a seed are extended. Schematic, not to scale.

How to read the figure

Read the cards from left to right. Card 1 shows the start of a protein query cut into three-letter words, each starting one letter after the last. In card 2, each grey bar is a database sequence, and the vermilion blocks are places where a query word was found: the seeds. Card 3 zooms in on one seed and shows it growing in both directions. The tapering bar at the bottom is the point of the whole design: the expensive alignment step is spent on a tiny share of the database.

BLAST was published by Altschul, Gish, Miller, Myers and Lipman (1990), 'Basic local alignment search tool', Journal of Molecular Biology 215:403–410. The gapped extension used today came in Altschul et al. (1997), 'Gapped BLAST and PSI-BLAST: a new generation of protein database search programs', Nucleic Acids Research 25:3389–3402. The statistics behind E-values rest on Karlin and Altschul (1990), PNAS 87:2264–2268. The command-line version is BLAST+ (Camacho et al., 2009, BMC Bioinformatics 10:421). Databases grow all the time, so the same search can give different E-values next year. Report the program and its version, the database, the date you searched and any settings you changed.

E-values: how surprised should you be?

A score on its own is hard to judge. Is 50 good? It depends on how long the query is and how big the database is, because a bigger search gives chance more opportunities. The E-value (expect value) takes care of that. It is the number of alignments with at least this score that you would expect to find by chance alone, in a search of this size with unrelated sequences.

  • An E-value of 10 means ten such matches would turn up by chance: the hit tells you nothing.
  • An E-value of 0.01 means a chance match this good would turn up about once in a hundred searches.
  • An E-value such as 1e-50 (written 1e-50, meaning 1 × 10−50) is far beyond chance. BLAST prints 0.0 for values too small to show.

The calculation is simple once you have a bit score, S′. Each extra bit halves the chance of a random match, so E = m × n × 2−S′, where m is the length of the query and n the total length of the database, both in letters. Two consequences follow. The same alignment gets a larger, worse E-value in a larger database. And a short query can never reach a very small E-value, because it cannot build up a high score.

A practical consequence: the bit score belongs to the alignment, while the E-value belongs to the alignment and the search together. Search the same query against swissprot and against the much larger nr, and the same alignment keeps its bit score but gets a larger E-value in nr. When you compare hits from two searches, compare bit scores; when you judge whether a single hit could be chance, use its E-value.

E-values also assume that the sequences look like ordinary proteins or DNA. The low-complexity regions met in Why compare sequences: homology, similarity and identity, stretches built from only a few kinds of letter, break that assumption and can give impressive-looking E-values between unrelated sequences. BLAST therefore offers a filter, under the algorithm parameters, that masks such regions before the search: the masked letters are not used for seeds and may appear in lower case, or as X or N, in the results. For DNA searches the filter is switched on by default. For protein searches BLAST by default adjusts the scores for unusual amino acid composition instead, and the filter can be switched on if needed.

Worked example · from bit score to E-value

query length m = 150 · database length n = 100,000,000,000 (example values)
search space m × n = 1.5 × 1013
bit score 30 → E = 1.5 × 1013 ÷ 230 ≈ 14,000
bit score 50 → E = 1.5 × 1013 ÷ 250 ≈ 0.013
bit score 100 → E = 1.5 × 1013 ÷ 2100 ≈ 1.2 × 10−17

The numbers are round example values, chosen to show the arithmetic. Real BLAST makes small corrections to the lengths, but the pattern is the same.

Step by step. Multiply the query length by the database length: 150 × 100 billion = 1.5 × 1013. This is the search space, every place a match could start. Then divide by 2 raised to the bit score. 230 is about 1.07 billion, and 1.5 × 1013 ÷ 1.07 × 109 is about 14,000. 250 is about 1.13 × 1015, giving 0.013. 2100 is about 1.27 × 1030, giving 1.2 × 10−17.

What the answer means. A bit score of 30 is noise: you would expect thousands of matches that good by chance. A bit score of 50 is borderline, likely real but worth checking. A bit score of 100 is overwhelming evidence of a real relationship. Adding 20 bits divided E by about a million, which is why E-values fall so steeply as alignments get longer.

Go deeper: an E-value is not a p-value

An E-value is the expected number of chance hits; a p-value is the probability of at least one. The statistics behind BLAST link them with a simple rule: p = 1 − e to the power −E, where e is the number 2.718…. For small E-values the two are almost the same: E = 0.01 gives p ≈ 0.00995.

For larger values they part company. E = 1 gives p ≈ 0.63, E = 3 gives p ≈ 0.95, and E = 10 gives p ≈ 0.99995. A p-value can never pass 1, while an E-value can take any size, which makes E-values easier to read across the wide range BLAST reports. The E-value already allows for the size of the database, so you do not need to correct it again for the number of entries searched; that is its purpose.

The seed idea in Python

This lesson needs no extra packages: the code is plain Python. It uses three short DNA sequences made up for teaching, so you can see every seed. The first block finds seeds: words of length 5 that occur in both the query and a database sequence.

Python
# Made-up DNA sequences, for teaching only
query = "GATTACAGCCTAGGCATCG"
database = {
    "seq_A": "TTTTGATTACAGCATAGGCATCGTTTT",
    "seq_B": "CCCCCCGGGGGGAAAAAATTTTTT",
    "seq_C": "AGCCTAGGTTTTTTTTTTTTTTTT",
}
k = 5                                   # word length

def words(seq, k):
    """Every word of length k, with its start position."""
    return [(seq[i:i+k], i) for i in range(len(seq) - k + 1)]

query_words = {}
for w, i in words(query, k):
    query_words.setdefault(w, []).append(i)

for name, seq in database.items():
    seeds = [(qi, si, w) for w, si in words(seq, k)
             for qi in query_words.get(w, [])]
    print(name, len(seeds), "seeds", seeds[:3])

What this does

  • query and database hold the made-up sequences. A dictionary, written with curly brackets, links each name to its sequence.
  • words(seq, k) slides along a sequence and returns every word of length k with its start position. Python counts positions from 0, so the first letter is position 0.
  • The first loop builds query_words, an index from each query word to where it occurs.
  • For each database sequence, the next line keeps every pair of positions where the same word occurs in both. Each one is a seed, stored as (query position, database position, word). The code prints how many seeds there are and the first three.
seq_A 10 seeds [(0, 4, 'GATTA'), (1, 5, 'ATTAC'), (2, 6, 'TTACA')] seq_B 0 seeds [] seq_C 4 seeds [(6, 0, 'AGCCT'), (7, 1, 'GCCTA'), (8, 2, 'CCTAG')]

Reading the output

seq_A has 10 seeds, starting with GATTA at query position 0 and database position 4: the two sequences share a long stretch. seq_B has none, so a search would skip it without aligning anything. seq_C has 4 seeds, all in one short run starting with AGCCT. Seeds tell you where to look, not yet how good the match is. The query has 15 words; seq_A differs from it at one letter, which breaks the 5 words that cover that letter, leaving 10.

The second block extends a seed. It walks to the right, adding +1 for a match and −2 for a mismatch, and stops when the running score falls more than 3 below the best so far. Real BLAST extends in both directions; one direction keeps the code short.

Python
def extend(q, s, qi, si, k, match=1, mismatch=-2, xdrop=3):
    best = score = k * match            # the seed itself
    best_end = 0
    step = 1                            # walk right from the seed
    while qi + k - 1 + step < len(q) and si + k - 1 + step < len(s):
        score += match if q[qi+k-1+step] == s[si+k-1+step] else mismatch
        if score > best:
            best, best_end = score, step
        if best - score > xdrop:        # fell too far below the best: stop
            break
        step += 1
    return best, q[qi:qi+k+best_end], s[si:si+k+best_end]

print(extend(query, database["seq_A"], 0, 4, k))
print(extend(query, database["seq_C"], 6, 0, k))

What this does

  • extend starts with the score of the seed itself, 5 matches × 1 = 5, and remembers it as the best.
  • Each pass of the while loop looks at the next pair of letters to the right of the seed, adds the match or mismatch score, and records a new best score and where it ended.
  • if best - score > xdrop: break is the X-drop rule: once the score has dropped more than 3 below the best, the match is judged to be over.
  • The function returns the best score and the two matching stretches. The two calls use seeds from block 1: query position 0 against seq_A position 4, and query position 6 against seq_C position 0.
(16, 'GATTACAGCCTAGGCATCG', 'GATTACAGCATAGGCATCG') (8, 'AGCCTAGG', 'AGCCTAGG')

Reading the output

For seq_A, the match runs the full 19 letters of the query with one mismatch (C against A at the tenth letter): 18 matches × 1 − 2 = 16. For seq_C, the match stops after 8 letters with a score of 8: after that, the letters disagree and the score falls away. Of the two, seq_A is clearly the better hit.

Reading a web BLAST results page

Real searches run on the BLAST web pages at NCBI (blast.ncbi.nlm.nih.gov). Choose the program, paste your sequence in FASTA format, choose a database, and press BLAST. For proteins, swissprot (reviewed UniProt entries) gives a short, well-annotated list; nr (non-redundant) is far larger. The results page opens on a Descriptions table, one row per database sequence. Below is the kind of table you get for the human haemoglobin beta protein (147 residues) searched with blastp.

DescriptionScientific nameMax scoreQuery coverE valuePer. ident
Hemoglobin subunit betaHomo sapiens305100%4e-82100.00%
Hemoglobin subunit betaGorilla gorilla gorilla304100%1e-8199.32%
Hemoglobin subunit betaEquus caballus25399%2e-6683.56%
Hemoglobin subunit betaBos taurus25298%3e-6684.72%
Hemoglobin subunit beta-1Mus musculus250100%1e-6580.27%
Hemoglobin subunit betaGallus gallus218100%7e-5669.39%
Hemoglobin subunit alphaHomo sapiens11497%1e-2442.07%
MyoglobinHomo sapiens4797%2e-0425.52%

Example output, shortened. A real search lists many more globins, and the exact scores and E-values depend on the database version. The identities and coverages here come from real alignments of these UniProt sequences; the E-values were worked out as in the worked example above.

How to read this table

  • Max score is the bit score of the best local alignment with that sequence. Higher is better.
  • Query cover is the share of your query that lies inside the alignment. 97% means nearly all of it; 30% would mean only one region matched.
  • E value is as explained above. Rows are sorted by it, smallest first.
  • Per. ident (percent identity) is the share of aligned positions with the same letter, counted over the aligned stretch only, not over the whole query.

Read the rows from the top. The human protein matches itself. The other species' beta chains follow. Their order does not simply follow the family tree of the animals: mice are more closely related to humans than horses or cows are, yet mouse beta globin has changed more. Trees from sequences comes back to this. Next comes human alpha globin, a different gene that shares an ancestor with beta globin long ago, at 42% identity. Myoglobin, a more distant relative, still scrapes in at E = 2e-04 with 26% identity. Hits with larger E-values are cut off by the Expect threshold, a setting you can change under the algorithm parameters before you run the search.

Always read identity and cover together. A hit with 100% identity over 10% cover may be one short shared motif, not the same protein.

Treat the Description column with care. It is copied from the database entry, and in a large database such as nr many entries were named by a computer from their own best match, so a wrong name can spread from record to record. Words such as "hypothetical", "predicted" or "uncharacterized" are a warning that nobody has studied that protein directly. Each row links to its record, which you can read as in Reading a gene record and a protein record; checking the review status there is a quick way to tell a curated name from an inherited one.

Choosing blastn, blastp or blastx

The BLAST page offers several programs. They differ in what the query is and what the database holds. "Translated" means BLAST converts DNA into protein, in all six reading frames (three on each strand), before comparing.

ProgramQueryDatabaseUse it when
blastnDNADNAYou want the same or a very similar DNA sequence: checking a PCR product, finding a gene in a genome, identifying a species from a barcode sequence.
blastpProteinProteinYou have a protein and want its relatives, including distant ones.
blastxDNA, translatedProteinYou have a DNA sequence, such as a new transcript, and want to know what protein it might encode.
tblastnProteinDNA, translatedYou want to find genes for a known protein in DNA that has not been annotated yet.

How to read this table

Read across each row: the program, what you paste in, what it is compared with, and when to choose it. The deciding rule is that protein comparisons find more distant relatives than DNA comparisons. The genetic code has redundancy, so DNA changes faster than the protein it encodes, and twenty amino acids carry more information per letter than four bases. Two genes that have drifted to near-random DNA similarity can still have clearly related proteins. So if your DNA codes for protein and you want relatives beyond close species, use blastx rather than blastn.

Two cautions. First, check which variant of blastn the page is set to: the web page often starts on megablast, which is fast for close matches and can return nothing for a gene from a distant species that a more sensitive setting would find. Second, blastx and tblastn search all six reading frames, so a hit can come from a frame you did not expect. The alignment view shows which frame matched, and a hit on the opposite strand simply means your sequence was written in the reverse direction to the gene.

Key point

BLAST is fast because it only aligns where short words match. Judge each hit by its E-value, then read query cover and percent identity together: a small E-value over most of the query is strong evidence of homology.

The reverse does not hold. A large E-value does not prove two sequences are unrelated. Very distant relatives can fall below what any similarity search detects, which is why comparing 3D structures sometimes reveals relationships that BLAST misses.

Further reading · Module 4BLAST help: the official guide to programs, databases and results. · BLAST FAQ: short answers on scores and E-values. · All reading for this course

Check your understanding

1. A blastp hit shows 100% identity, but over only 12% of your query, with an E-value of 3. What should you conclude?

2. The same alignment, with the same bit score, is found in a database ten times larger. What happens to its E-value?

3. You have a new transcript from an insect with no close relatives sequenced, and want to know what protein it may encode. Which program fits best?

Up next

Lesson 6

Multiple alignment and conserved regions

Ask BioTutor

Create a free website with Framer, the website builder loved by startups, designers and agencies.