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

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:

1. 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?
• According to BI SE this falls into the category ".... However, if your motivation is “I would like others to explain ______ to me”, then you are probably OK." From bioinformatics.stackexchange.com/help/dont-ask Which is why I was hoping to find some help here. Jan 23, 2022 at 13:24
• Thanks for the clarification. It's fine to ask these types of specific questions, but context helps a lot in providing useful answers. You've mentioned "a beginner with biology background and very little idea about algorithms", which is inconsistent with the level of algorithmic detail you've provided. That's why I asked for clarification.
– gringer
Jan 24, 2022 at 4:45
• @gringer Thanks, I see (-: trust me, algorithms are still a big challenge and mystery to me. Jan 24, 2022 at 10:00

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.