RapMap: Unreasonably Fast and Accurate Transcriptome Mapping

Introducing RapMap

I’ve recently been working with my student Avi Srivastava on a new project, RapMap.  RapMap is a tool for mapping (see below for the distinction between mapping and alignment) sequencing reads to a transcriptome.  It currently implements two related but distinct mapping strategies, which I refer to as pseudo-mapping (this is no different from pseudo-alignment, an idea developed by Bray et al. as described below, but I will use the name pseudo-mapping for consistency) and quasi-mapping.  A pre-print is forthcoming that will describe the tool, methods and results in further detail.  However, in this post, I want to describe the main ideas and motivation behind this project, and provide a few of the results that we found so astounding.

Alignment vs. Mapping

First, let me attempt to explain what RapMap is not.  This will require me to draw a distinction between alignment and mapping.  Read alignment produces a nucleotide-to-nucleotide correspondence between each query sequence it deems sufficiently similar to some subsequence(s) of the reference.  The result of computing such alignments is a collection of locations in the reference, as well as a specification (most commonly represented as a CIGAR string) of the correspondence between the query and the subsequence of the reference at this location that yields the smallest cost (or, equivalently, the highest score) under some specified model of sequence distance (or similarity).  Such alignments are the de facto currency of many higher-level genomic analyses.  It is important to note that the most common read aligners (Bowtie 2, BWA, STAR) are not exhaustive; that is, they do not guarantee that they will discover every subsequence of the reference that is within the specified distance of the query.  Though such exhaustive or fully-sensitive tools do exist, they tend to be substantially slower, and are used primarily for tasks in which finding every admissible alignment is essential.

In comparison to alignment, mapping is the determination of the set of locations in the reference that match the query sequence (i.e. the read) “sufficiently well”.  Here, I intentionally leave the term “sufficiently well” somewhat vague, as the problem is less well-studied than alignment and a reasonable determination of what constitutes “sufficiently well” is still a reasonable topic for discussion and debate.  The key difference between mapping and alignment, as described here (again, I note that these terms are often used interchangeably in the broader community), is that mapping need not, and typically does not, compute or report a nucleotide-to-nucleotide correspondence between the query and locations on the reference.  Avoiding this computation provides hope that reads can be mapped much faster than they can be aligned and, indeed, this seems to be the case.

RapMap is a read mapper.  Given a reference (in this case, a transcriptome) and set of sequencing reads, it computes the likely loci of origin of each sequenced read with respect to the reference.  The question, of course, is how to compute these locations rapidly and accurately.  RapMap implements two distinct but related approaches, both of which achieve these goals in spades.

What’s in RapMap?

The first algorithm provided by RapMap is an independent re-implementation of the method of pseudo-alignment (herein called pseudo-mapping) that was first introduced by Bray et al. in the pre-print for the RNA-seq quantification tool Kallisto.  Re-implementing a method is a fantastic way to understand how it works, and the initial motivation behind writing the first part of the RapMap coe was to really grok the innards of pseudo-mapping by implementing it.  A fringe benefit of this is to provide an implementation of this idea under a different license (currently RapMap is licensed under GPL)  than that adopted by Kallisto, whose license was the cause of some debate (a blog post by Lior Pachter, two by Titus Brown (1), (2), and two over at homolog.us (1), (2) ) a few weeks back.  While the details of our re-implementation differ in some places from the implementation provided in Kallisto, we neither expect nor observe that these differences have a substantial effect on the speed or quality of the pseudo-mapping process.  Thus, I refer the curious reader to the Kallisto pre-print (and the even-more-curious reader to the Kallisto and RapMap source code) for a more thorough description of pseudo-mapping.

The second algorithm provided by RapMap — quasi-mapping — is a novel one1, and thus the one upon which I wish to focus in this blog post.  It is inspired by some ideas from the venerable STAR aligner, and from understanding how to exploit the special structure of the transcriptome to allow fast mapping.  I will provide a high-level overview of how quasi-mapping works but, again, the forthcoming pre-print and the RapMap software itself will be the best place to understand the requisite details.

Quasi-mapping (from 30,000 feet)

The core data structures exploited by quasi-mapping are a generalized suffix array (SA) of the transcriptome, and a hash-table mapping fixed-depth suffixes (k-mers) from the reference to their suffix array intervals.  The hash table isn’t strictly necessary for the method to work — everything about the algorithm I describe below could be done with just the suffix array — but pairing the suffix array with a k-mer hash table to reduce the interval on which binary searches need to be performed can improve speed substantially.  The hash table provides an expected $O\left(1\right)$ lookup that allows one to retrieve, for any k-mer, k, the suffix array interval $\texttt{SAInt}\left(k\right) = \left[b, e\right)$ where it occurs, while the suffix array allows $O\left(m \log n\right)$ lookup for any substring of length m, where $n = \left|T\right|$ is the length of the concatenated text, T, on which the generalized suffix array is constructed. That is, for an arbitrary pattern p of length m, we can find $\texttt{SAInt}\left(p\right)$ in $O\left(m \log n\right)$ time. It’s worth noting that the suffix array search can be improved to $O\left(m + \log n\right)$ using an auxiliary data structure (the LCP array), and that the “simple accelerant” of the suffix array search (described in Gusfield’s classic text) allows one to achieve search speeds practically comparable without the need for the auxiliary LCP array.  Further, pairing the hash table with the suffix array ensures that any pattern of length m that begins with a k-mer in the hash can be found in $O\left(m \log\left(e-b\right)\right)$ time (which, due to the simple accelerant mostly becomes $O\left(m + \log\left(e-b\right)\right)$ in practice).  I also note here that a few more neat tricks (e.g. super-fast rank operations on a bit array, as provided by the method of Vigna) are necessary to yield a fast and practical index for quasi-mapping.

Given this index, the core algorithm behind quasi-mapping can be described based on two simple concepts; the maximum mappable prefix (MMP) and the next informative position (NIP).  I will describe these concepts, and then how they are used in the quasi-mapping algorithm.  A maximum mappable prefix, p, is a prefix of some suffix of a query that cannot be extended further without the size of $\texttt{SAInt}\left(p\right)$ going to 0.  In other words, it is the longest prefix of a given suffix of the query for which there is at least a single occurrence in the reference.  Given a query q, the the MMP of q, and its suffix array interval, can be found with two slightly modified suffix array searches.  That is, we can determine the maximum length prefix of q appearing in our reference, and the corresponding interval in the suffix array, almost as quickly as we can determine the suffix array interval for a pattern of a fixed and pre-specified size.

Consider a query q, with MMP of p, corresponding to a suffix array interval $\texttt{SAInt}\left(p\right) = \left[b, e\right)$.  By the definition of the MMP, we can not extend p any further without introducing a mismatch between the query and reference.  However, it is quite possible (and often turns out to be the case in practice) that $\texttt{T}\left[\texttt{SA}\left[b\right]\right]$ and $\texttt{T}\left[\texttt{SA}\left[e-1\right]\right]$ share some prefix of length $>\left|p\right|$ — that the bounds of the suffix array interval where we end up after searching for the MMP of q share a longer prefix than the query string which led us there.  In this case, we define the next informative position (NIP) on the query as $\texttt{NIP}\left(\texttt{start}\left(p\right)\right) = \texttt{start}\left(p\right) + \left|\texttt{LCP}\left(\texttt{T}\left[\texttt{SA}\left[b\right]\right],\texttt{T}\left[\texttt{SA}\left[e-1\right]\right]\right)\right|$, where $\texttt{start}\left(p\right)$ is the position on the query where the current maximum mappable prefix begins, and $\texttt{LCP}\left(\cdot,\cdot\right)$ denotes the longest common prefix function.  In words, the NIP at a position $i$ on the query is simply $i$ plus the length of the longest common extension of the suffix array boundaries for the maximum mappable prefix that begins at $i$.  Equipped with these definitions, we are now ready to discuss the quasi-mapping algorithm.

For the sake of simplicity, I will describe the situation in which all “hits” within a read (described below), occur in the forward direction with respect to the reference.  The technical details for handling reverse-complement  mappings are important, but rather trivial.  Consider mapping a read r against the reference using the index described above.  We begin at the left end of the read, looking, in turn, at each k-mer, until we find one that is present in the k-mer hash we’ve built.  Call this k-mer w, and imagine that it constitutes the first k bases of some suffix p of the read.  At this point, we find the corresponding suffix array interval $\texttt{SAInt}\left(w\right) = \left[b,e\right)$, and perform the requisite search in this interval to determine the maximum mappable prefix of p (the suffix of the read that starts with the k-mer, w, we have queried).  Since all suffixes in the suffix array that begin with some length $k' \ge k$ extension of w must reside in a (not necessarily proper) sub-interval of $\texttt{SAInt}\left(w\right)$, we can restrict the binary search to this interval, making it a $O\left(m \log\left(e-b\right)\right)$ operation rather than a $O\left(m \log n\right)$ one.  Let p’, some prefix of p, be the maximum mappable prefix we have determined, and let $\texttt{SAInt}\left(p'\right) = \left[b', e'\right)$.  Finally, we compute $x = \texttt{NIP}\left(\texttt{start}\left(p\right)\right)$.  Now, rather than move by a single nucleotide to the next k-mer to continue our search, we instead move to the position in the query that resides k-1 bases before $x$.  That is, the next k-mer we consider will be the rightmost k-mer that is not contained within the substring of the query that starts at $\texttt{start}\left(p\right)$ and ends at $\texttt{NIP}\left(\texttt{start}\left(p\right)\right)$.  As it turns out, the distance between $\texttt{start}\left(p\right)$ and $\texttt{NIP}\left(\texttt{start}\left(p\right)\right)$ is often quite large meaning that, on average, we have to perform this process very few times before we have “covered” the entire read.  Once this process is complete, we have a collection of suffix array intervals (these are the “hits” mentioned above) — one corresponding to each MMP we consider — which can then be easily processed to extract the transcripts and positions to which this read maps.  Specifically, to generate a set of mapping positions, we find the set of transcripts that appear in every hit, and find the positions on these transcripts that are (approximately) consistent with the distance between the corresponding MMPs in the query.

Modulo some optimizations and book-keeping details, that’s it.  The quasi-mapping procedure simply builds up, for each read, a collection of these “hits”, and then processes them to extract the mapping locations for each read.  Paired-end reads are mapped by filtering the mapping locations for each read to find consistent (concordant) mappings for the pair.  So that’s a high-level overview of the algorithm.  The tool itself, RapMap, is also dead-simple to use.  It exposes 4 commands $\texttt{pseudoindex}$, $\texttt{pseudomap}$, $\texttt{quasiindex}$ and $\texttt{quasimap}$ — you can guess what each does.  The standard process is to build the appropriate index on a target transcriptome using the corresponding “index” command.  Then, given a collection of sequencing reads, the “map” command can be used, along with the pre-computed index, to map reads fast . . . really, really, really, fast.  How fast?  Let me give you some numbers from preliminary testing.  First, on my iMac, it takes ~2 minutes (141s) to build the quasi-mapper index on the hg19 transcriptome.  The majority of the time spent indexing is, in fact, just spend in the suffix array construction algorithm (using the popular SAIS implementation of Yuta Mori).  While 2 minutes for index building on the human transcriptome probably isn’t something one should even bother optimizing, there are some interesting looking suffix array construction algorithms that are potentially faster.

Letting RapMap stretch its legs

Now, we consider mapping 25 million 76bp paired-end reads (generated with an empirical error distribution) from a synthetic dataset with a substantial amount of true multimapping (i.e. reads mapping to multiple, sequence-identical positions on the transcriptome) using an increasing number of threads.  The timings come out as follows (“no output” here refers to the fact that these runs check just the time required to do the mapping or alignment, not to dump their giant files to disk):

Time in secondsRapMapRapMap (just mapping)STAR Bowtie 2

MetricRapMapSTARBowtie2
Precision98.18%97.09%98.33%
Recall97.08%90.89%96.44%
F1 Score97.62%93.89%97.37%
FDR1.82%2.91%1.67%

So, we see that all of the aligners (or mapper in the case of RapMap) seem to do reasonably well, with qasi-mapping putting up some very nice numbers.  RapMap seems to report more mappings per read than STAR, but given its substantially higher recall, these extra mappings may be unavoidable if we’re also to recall the correct mapping.  Bowtie 2 has a very nice precision and recall as well, but generates a markedly larger average number of hits-per-read than either STAR or the quasi-mapper.  One potential explanation for this is that Bowtie2 is likely outputting some sub-optimal alignments as well.  Unlike Bowtie1, there is no way to return all mappings in the best stratum, which is, essentially, what we want.  So Bowtie 2 and RapMap seem, in some sense, comparably “accurate” here, but there is less ambiguity in the true positive alignment groups for RapMap (and it generates its result way, way, faster).

One final point is that all of the RapMap numbers given above are for the “quasi-mapping” algorithm, not the independent re-implementation of “pseudo-mapping”.  The pre-print will have some more inclusive (and comprehensive) performance numbers; the results are similar in many regards, and both clearly out-perform the more traditional approaches (again, remember the not-quite-apples-to-apples comparison of mapping vs. aligning), but there may be some reasons to grant slight preference to quasi-mapping2.

A bright future for “lightweight” mapping?

So, I hope you find quasi-alignment to be an interesting idea, and RapMap to be a useful tool.  An obvious question is “where might a tool like this be useful?”  Specifically, since we’re performing mapping and not alignment, we can’t really use this for things like e.g. variant detection (yet).  Well, one place is exactly where such methods (at least with respect to RNA-seq) first originated — speeding up transcript quantifiaction; Salmon introduced “lightweight-alignment” then Kallisto introduced “pseudo-alignment” (both are “mapping” in the terminology used above).  It’s a virtual certainty that “quasi-mapping” will make it into Salmon soon, and will provide a nice speed boost to the already “wicked fast” tool — it’s just a matter of settling on the RapMap API and doing the requisite testing.  However, such a tool brings along capabilities that extend beyond quantification, and we have a few places we’re interested in applying these concepts.  One immediately obvious application (to us, at least) is clustering, where one might very quickly find similar sequences by looking at shared multi-mapping reads.  We’ve also had the realization that if we can reduce every query to a very small number of potential loci of origin in the span of a few minutes, we might be able to turn these mappings into alignments without too much extra overhead (in some sense, the mapping acts like an incredibly efficient, albeit potentially lossy filter).  Since part of the quasi-mapping index is the un-molested reference (well, if you don’t consider concatenating things together separated by ‘\$’ as a form of textual molestation), actually throwing an efficient (e.g. banded, bit-vector) alignment algorithm at the mapping loci shouldn’t be too hard.  Further, it might be possible to speed even this step up.  Since the quasi-mapping procedure trivially gives us useful information about regions of the reference that exactly map, this means that alignment to different positions sharing identical sequence may also be able to share alignment computation.  We have quite a few other ideas as well, but I think I’ve gone on more than long enough for this post, so talking about those will have to wait for another day.

1. though the name was suggested in a tweet at some point around the “Biology of Genomes” meeting in early May, along with a somewhat humous plot.  I don’t remember the author of the tweet, but would like to credit the appropriate person with the name, so please let me know if you recall! edit: As pointed out by Valentine, it seems credit for this name goes to Stephen Turner, with the relevant tweet linked in the first comment below.

2. We generally find that pseudo-mapping is similar in terms of speed, and in terms of many of the metrics we consider above, but yields a somewhat higher “hits-per-read” statistic than quasi-mapping.  We also checked this against Kallisto directly to ensure that it wasn’t just a quirk of our implementation

This entry was posted in Computational Biology, Science. Bookmark the permalink.

4 Responses to RapMap: Unreasonably Fast and Accurate Transcriptome Mapping

1. Pretty sure this is the inspiration for the quasi-alignment name that you mention: https://twitter.com/genetics_blog/status/596062435582312448

• Rob says:

Indeed; Thanks, Valentine!

2. René Böttcher says:

Hi Rob,
I love the idea behind RapMap and look forward to your future developments! As a suggestion for the ‘conversion’ of mappings into alignments, we explored the idea of using ‘a priori knowledge’ for read alignment a few years ago with regard to targeted sequencing (specifically the HaloPlex technology).
Feel free to have a look: http://www.ncbi.nlm.nih.gov/pubmed/22581774.
Best,
René

• Rob says:

Hi René,

Thanks for the kind words! Also, thanks for pointing us at this reference. We’re currently looking into this restricted alignment problem, and the initial results seem to be very promising indeed. There are, of course, a few standard techniques to improve alignment speed given certain restrictions (e.g. reported exact matches must participate in the optimal alignment), but it turns out there are a few other special conditions that allow for further acceleration in our particular context. We’ll be sure to check out your paper and see if any of the ideas you propose there can be applied in this context (I’d venture to guess they probably can!).

Thanks,
Rob