1.1: BLAST (AKA so you have a sequence)

Step 1: Break the query sequence up into "words"

The first step in the BLAST algorithm is to break the sequence you are interested in (aka the "query" sequence) up into "words" (aka sequences of consecutive letters of a particular size). For example, AQTYRCATW is a word of length 9. The words of length 6 in this word are AQTYRC, QTYRCA, TYRCAT, and YRCATW.

Words are often also called "k-mers", where k is the length of the word. Why do we do this? Well, try this next exercise:

It is much easier to search through ~1000 things than it is ~a million!

Step 2: Store the word data for sequences in your database

We now have a set of words from the query sequence. We also have these words for all the sequences in our database. These words can be stored in a table like this (with the example of 4-letter words):

The entries in this table (indiated by #1, #2, etc) are the actual locations in the database where the word occurs, and the columns are each possible location in the database. Thus, when you acquire a new sequence, you can break it up into words and add a new column to this table. The words in the first column are called "seeds", because we will use them to start "growing" potential sequence matches.

Step 3: Use seeds to find and extend matches

We can match the words from our sequence (aka seeds) to existing words in the database. Better matches are going to be more similar around these seed matches. Let's take an example sequence TGCATCAA. All 4-letter words from this sequence are: TGCA, GCAT, CATC, ATCA, and TCAA. Each of these words can be used as a seed. For example, the word "GCAT" could be found at the locations #091001, #098199, and #032465. I wrote these locations in this weird way because they represent pointers, which are directions to physical locations in the memory of a computer (which is actually how these things are stored). Anyways, we can go to each of these locations and see how the rest of the sequence matches up. Let's say that we have the following sequences at these locations (with the seed word bolded):

• #091001: GGCATCCC
• #098199: AAAAAAAGCATAAAAAAA
• #032465: TGCATCAA

Note that in general the sequences are going to be much longer than this. For each hit, the basic idea is to start at the seed and then start comparing letters next to the seed. You could go in one direction only, or in both directions. Let's try the first hit, go in both directions, and compute the score at each extension (using the above example where a match is +5 and a mismatch is -4):

• Query: TGCATCAA

• GGCATCCC: 20
• GGCATCCC: 16 (mismatch)
• GGCATCCC: 21 (match)
• GGCATCCC: 17 (mismatch)
• GGCATCCC: 13 (mismatch)

Notice that continuing to extend the search does not necessarily make the match better. This is because BLAST is a local matching algorithm (that's what the L stands for); it wants to find regions of sequences that match and doesn't care if the whole sequence matches or not. This locality is usefyl when trying to find sequences that may have been diverging for a long period of time but are still similar in some places.

The MSP for this match is the highest score you get, which is 21.

Try the other two potential matches as an exercise:

Flavors of BLAST

There are a few different versions of BLAST that are all useful for slightly different things. Regular old BLAST (also called BLASTn) uses nucleotide sequences as queries and targets, and you want to use it if you have a DNA or RNA sequence and want to find the best match to another DNA or RNA sequence. To do the analogous thing with proteisn (aka take an amino acid sequence and find the best match amino acid sequence), you use BLASTp. One benefit of BLASTp is you can find proteins that are similar in amino acid structure but could be relatively different in nucleotide sequence.

If you have a nucleotide sequence and don't know the reading frame, you can use BLASTx, which takes your nucelotide sequence, translates it using all 6 reading frames, and then tries to find a best match protein sequence+reading frame. The reverse of BLASTx is called tBLASTn (takes the database nucleotide sequence and translate it to try to match your protein sequence). Finally, if we really have no idea what is going on, tBLASTx translates on both ends (from your nucleotide sequence to potential protein sequences, and from database nucleotide sequences to potential protein sequences).

The table below summarizes these versions (adapted from here). "Comparison" means what sequences are being compared to compute MSP scores by matching.