How should I imagine the pre-indexing of suffix arrays in the STAR RNA Seq-aligner?

Question

I'm using STAR for an internship (fusion-genes in ALL cancer) and I'd like to understand what exactly it is doing. The people at the internship don't know either how it works, given their biology backgrounds. They told me "its enough to know that it works". That was not an satisfactory answer for me which is why I am fighting my way trough the suplementary materials trying to wrap my head around the algo. My background is bio as well but I've spent reading a book about algos and algos in BI this year.

I am trying to understand the section Pre-indexing of suffix arrays from supplementary materials of the Dobin et al. STAR RNA seq-aligner Publication.

While suffix array search is theoretically fast owing to its binary nature, in practice it may suffer from non-locality resulting in persistent cache misses which deteriorate the performance. To alleviate this problem we developed a pre-indexing strategy. After the SA is generated, we find the locations of all possible $L-mers$ in the SA, $L<=L_{max}$, where L_{max} is user defined and is typically 12-15. Since the nucleotide alphabet contains only four letters, there are NL=22L different L-mers for which the SA locations have to be stored.

The authors also state:

Suffix Array (SA) of the whole genome is utilized to find the Maximum Mappable Prefixes (MMP).

1. I am confused by the use of the term $L-mer$. When googleing I only keep finding $k-mers$ in combination with suffix arrays. I did however find this GitHub page mentioning $L-mers$ in the following way:

This program computes either the suffix array or the L-mer array of a string. The suffix array gives the lexicographical order of all the suffixes of a string. The L-mer array gives the lexicographical order of all the L-mers in the string (sorts the suffixes with respect to only the first L characters).

→ Can I assume that $L-mer$ was used instead of $k-mer$ to stress the lexicographical ordering? But as far as I understood all suffix arrays contain the suffixes' index based on its lexicographic ordering as illustrated by wikipedia's page on suffix arrays:

2. Do I have to imagine the entire genome being a single string that is converted into one single suffix array? Could you provide sources fit for a beginner with biology background and very little idea about algorithms?

Answer 1

You can take a look at slide 40 of the lectures slides I use when I teach suffix arrays (reproduced here)

An L-mer is a K-mer — STAR builds an explicit lookup table from all length 14 (by default) strings that maps the length 14 string to interval of the suffix array that contains all suffixes that begin with this length 14 prefix. This means that, to find a MMP, instead of having to do a binary search on the entire suffix array, you only have to do a binary search on the sub-interval that begins with the length 14 prefix that your query string starts with. If all substrings suffixes began with length 14 prefixes with equal frequency, then this would reduce the size of the interval you have to look at by a factor of $268435456 = 4^{14}$. Of course, in biological sequence, all prefixes are not equally likely, so the speedup is more variable in practice. Nonetheless, it makes lookup in the suffix array much, much faster.

Of course, in addition to the core algorithm, STAR contains many heuristics not all of which are likely described in the paper (especially since the tool has been and continues to be under active development and improvement since the paper's publication). Nonetheless, this is the idea behind the suffix array pre-indexing. Since STAR still has the whole suffix array, if there is no length 14 exact prefix match, it is still possible to find a smaller match using a more standard binary search in the suffix array. However, I do not know (and am not sure where it is documented) exactly when/if STAR will fall back to a more naive binary search if a prefix L-mer is not found. If you are truly curious about this, I'd recommend asking Alex Dobin (the STAR author and maintainer) over on the STAR GitHub repository. He is generally very responsive to user queries there.