As we already know, traditional methods of alignment involve mapping sequencing reads to a reference genome (or transcriptome), but this requires a high degree of sequence similarity between the reads and the reference sequence, which can be difficult to achieve for non-model organisms. However in 2014, Nicolas Bray, a prominent young scientist, developed a new algorithm that does not require a fully assembled reference sequence. He named it pseudoalignment.
What, How and Why
Pseudoalignment is a method of aligning sequencing reads that does not require the fully assembled reference sequence. This approach has become popular in recent years as it is well-suited for analyzing data from non-model organisms, for which reference genomes/transcriptomes may not be available. Pseudoalignment works by first mapping reads to a database of known short sequences, and then using these mapped positions to infer the position of each read on the target genome/transcriptome.
Pseudoalignment is not about comparing or aligning nucleotides against each other; it is about splitting the reference sequence to the small unique pieces with a sliding window, called k-mers, indexing them, and then building a sort of pathway, to which we can map the reads of our target sequence and find the "location" of the read.
Pseudoaligning has several advantages over traditional alignment methods:
- Pseudoalignment is much faster than traditional alignment methods, making it well-suited for large data sets — RNA-seq of 30 million reads can be done under 3 minutes on a laptop;
- Pseudoalignment does not require a complete genome assembly, it can be used with data from unfinished or low-quality assemblies;
- In RNA-Seq analysis, only 30% of reads align uniquely to single transcript. Pseudoalignment (and Expectation-Maximization algorithm) can help to reduce this transcript ambiguity.
After Nicolas Bray published his work, another scientist, Lior Patcher, created a tool based on pseudoalignment algorithm for faster RNA-seq analysis. This tool called Kallisto was released in 2015.
Kallisto
Kallisto is a program for RNA-Seq analysis; it compares raw sequence reads to transcripts without aligning the reads to the genome. This way, it can rapidly quantify transcript abundance (in other words, expression).
What's the mechanism?
Imagine we have 3 transcripts: A, B, and C. These transcripts are used to create a transcriptome de Bruijn graph (T-DBG) (circles represent k-mers):
As we can see, each k-mer is associated with at least one transcript. This association is called k-compatibility class; if a k-mer can be found in 3 transcripts at the same time, its k-compatibility class equals 3.
After Kallisto has built T-DBG, it will then create a hash table to store the location of each k-mer — in other words, Kallisto does indexing.
Now, let's try to take a read of the following structure:
This read, but in k-mers, will appear on the graph as follows:
Let's find a k-compatibility class of the whole read to find what transcript the read is compatible with; for that, we need to find an intersection of all k-mer k-compatibility classes:
And here comes the last important take home message: Kallisto can find and skip redundant information. Here, the 3 left k-mers have the same location and the same k-compatibility class — they form an equivalence class. When this happens, Kallisto counts k-mers as one and then proceeds to the next k-mer:
This brings us to the result of the intersection: the read is part of the transcripts A and B, but not C.
The advantage of Kallisto over other methods of quantifying transcript abundances is that it is much faster, since it does not actually align the reads. This makes Kallisto particularly well suited for RNA-Seq data sets, which are often extremely large.
Conclusion
Pseudoalignment is a k-mer based algorithm that can help to identify potential matches for a query sequence without aligning the query to reference sequences. This makes it much faster than traditional alignment methods and also means that it can be used with data where the fully assembled reference sequence is unavailable. For performing pseudoalignment, Kallisto is a very popular program that is used for RNA-seq analysis.