<p>You can take a look at slide 40 of the <a href="https://rob-p.github.io/CMSC423_F21/static_files/presentations/CMSC423_F21_5.pdf" rel="nofollow noreferrer">lectures slides</a> I use when I teach suffix arrays (reproduced here)
<a href="https://i.sstatic.net/aNdIr.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aNdIr.png" alt="pre-indexing of the suffix array" /></a></p>
<p>An L-mer <em>is</em> 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 <strong>all suffixes that begin with this length 14 prefix</strong>.  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 <span class="math-container">$268435456 = 4^{14}$</span>.  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.</p>
<p>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.</p>

CC BY-SA 4.0
2022-01-23T19:06:31.390Z
2022-01-23T19:06:31.390Z
nomad
<p>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 &quot;its enough to know that it works&quot;. 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.</p>
<p>I am trying to understand the section <em>Pre-indexing of suffix arrays</em> from <a href="https://oup.silverchair-cdn.com/oup/backfile/Content_public/Journal/bioinformatics/29/1/10.1093_bioinformatics_bts635/2/bts635_Supplementary_Data.zip?Expires=1645401704&amp;Signature=jkgvDWNJutWbvNaZ9RiZbgkSBswvI19rq-8NkA35l-ruzy5w0W4RBIRvhtpncSGvAd1iiCi3PHZCeDmq1Jgr1N79wDz%7E2bnb8KSoQcSh%7EObsOwCI-G7bWuZiQRh3T1jbjOL-1VW9irjTnVO4icYY%7EgGvASDXRxVvxTsOl1m3%7EdQrGjcvUU4QXFQG8opHedFwmY0NaC9e%7E8WfqrdGLLFPXbMbZarL396dLCIVgk7DhgaeIUktXIPxXqyEeJ6fRH4FCnUl63uuAU45GJnE8aObOGwXKM5IDVlEz9AcSiB-QuHQN76LghnZNc6iDQZVCmBAZTLnvH0D0huPHuHUvGaEMg__&amp;Key-Pair-Id=APKAIE5G5CRDK6RD3PGA" rel="nofollow noreferrer">supplementary materials</a> of the <em>Dobin et al.</em> <a href="https://academic.oup.com/bioinformatics/article/29/1/15/272537" rel="nofollow noreferrer">STAR RNA seq-aligner Publication</a>.</p>
<blockquote>
<p>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 <span class="math-container">$L-mers$</span> in the SA, <span class="math-container">$L&lt;=L_{max}$</span>, 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.</p>
</blockquote>
<p>The authors also state:</p>
<blockquote>
<p>Suffix Array (SA) of the whole genome is utilized to find the Maximum Mappable Prefixes (MMP).</p>
</blockquote>
<ol>
<li>I am confused by the use of the term <span class="math-container">$L-mer$</span>. When googleing I only keep finding <span class="math-container">$k-mers$</span> in combination with suffix arrays. I did however find <a href="https://github.com/mariusmni/radixSA64" rel="nofollow noreferrer">this GitHub page</a> mentioning <span class="math-container">$L-mers$</span> in the following way:</li>
</ol>
<blockquote>
<p>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).</p>
</blockquote>
<p>→ Can I assume that <span class="math-container">$L-mer$</span> was used instead of <span class="math-container">$k-mer$</span> to stress the lexicographical ordering? But as far as I understood <em>all</em> suffix arrays contain the suffixes' index based on its lexicographic ordering as illustrated by <a href="https://en.wikipedia.org/wiki/Suffix_array#Correspondence_to_suffix_trees" rel="nofollow noreferrer">wikipedia's page on suffix arrays</a>:</p>
<p><img src="https://i.sstatic.net/sDHuo.png" alt="enter image description here" /></p>
<ol start="2">
<li>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?</li>
</ol>

CC BY-SA 4.0
2022-01-23T13:24:32.850Z
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 https://bioinformatics.stackexchange.com/help/dont-ask 
Which is why I was hoping to find some help here.
ilam engl
CC BY-SA 4.0
2022-01-24T04:45:12.227Z
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
CC BY-SA 4.0
2022-01-24T10:00:59.603Z
@gringer Thanks, I see (-:  trust me, algorithms are still a big challenge and mystery to me.
ilam engl
<algorithms><star><indexing>
How should I imagine the pre-indexing of suffix arrays in the STAR RNA Seq-aligner?
# How should I imagine the pre-indexing of suffix arrays in the STAR RNA Seq-aligner?

(Asked by: username_0 on 2022-01-23)

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](https://oup.silverchair-cdn.com/oup/backfile/Content_public/Journal/bioinformatics/29/1/10.1093_bioinformatics_bts635/2/bts635_Supplementary_Data.zip?Expires=1645401704&Signature=jkgvDWNJutWbvNaZ9RiZbgkSBswvI19rq-8NkA35l-ruzy5w0W4RBIRvhtpncSGvAd1iiCi3PHZCeDmq1Jgr1N79wDz%7E2bnb8KSoQcSh%7EObsOwCI-G7bWuZiQRh3T1jbjOL-1VW9irjTnVO4icYY%7EgGvASDXRxVvxTsOl1m3%7EdQrGjcvUU4QXFQG8opHedFwmY0NaC9e%7E8WfqrdGLLFPXbMbZarL396dLCIVgk7DhgaeIUktXIPxXqyEeJ6fRH4FCnUl63uuAU45GJnE8aObOGwXKM5IDVlEz9AcSiB-QuHQN76LghnZNc6iDQZVCmBAZTLnvH0D0huPHuHUvGaEMg__&Key-Pair-Id=APKAIE5G5CRDK6RD3PGA) of the *Dobin et al.* [STAR RNA seq-aligner Publication](https://academic.oup.com/bioinformatics/article/29/1/15/272537).

> 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](https://github.com/mariusmni/radixSA64) 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](https://en.wikipedia.org/wiki/Suffix_array#Correspondence_to_suffix_trees):

![enter image description here](https://i.sstatic.net/sDHuo.png)

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?

**Tags:** algorithms, star, indexing
> **Comments:**
> **username_0**: 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 https://bioinformatics.stackexchange.com/help/dont-ask  Which is why I was hoping to find some help here.  
> **username_1**: 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.  
> **username_0**: @gringer Thanks, I see (-:  trust me, algorithms are still a big challenge and mystery to me.  

---

## 1 answers

### Answer by username_2 on 2022-01-23. Score: 2 | Accepted answer

You can take a look at slide 40 of the [lectures slides](https://rob-p.github.io/CMSC423_F21/static_files/presentations/CMSC423_F21_5.pdf) I use when I teach suffix arrays (reproduced here)
[![pre-indexing of the suffix array](https://i.sstatic.net/aNdIr.png)](https://i.sstatic.net/aNdIr.png)

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.


---

