Is the algorithm of the STAR RNA Seq-Aligner similar to the Knuth-Morris-Pratt string matching algorithm?

Question

I don't know if I'm in the right SE, if not let me know and I'll delete it.

I am reading the original publication of the STAR RNA-Sequence aligner.

Given the quoted text below I wonder if the algorithm for the seed search is actually an implementation of th Knut-Morris-Pratt algorithm?

The central idea of the STAR seed finding phase is the sequential search for a Maximal Mappable Prefix (MMP). MMP is similar to the Maximal Exact (Unique) Match concept used by the large-scale genome alignment tools Mummer (Delcher et al., 1999, 2002; Kurtz et al.) and MAUVE (Darling et al., 2004, 2010). Given a read sequence R, read location i and a reference genome sequence G, the MMP(R,i,G) is defined as the longest substring (Ri, Ri+1, … , Ri+MML−1) that matches exactly one or more substrings of G, where MML is the maximum mappable length. We will explain this concept using a simple example of a read that contains a single splice junction and no mismatches (Fig. 1a). In the first step, the algorithm finds the MMP starting from the first base of the read. Because the read in this example comprises a splice junction, it cannot be mapped contiguously to the genome, and thus the first seed will be mapped to a donor splice site. Next, the MMP search is repeated for the unmapped portion of the read, which, in this case, will be mapped to an acceptor splice site. Note that this sequential application of MMP search only to the unmapped portions of the read makes the STAR algorithm extremely fast and distinguishes it from Mummer and MAUVE, which find all possible Maximal Exact Matches.

It is not cited in the references but it might be considered 'common knowledge' by now which is why the citation is omitted...

Answer 1

No, STAR isn't using the KMP algorithm or a modification of it. The KMP algorithm is an online exact pattern matching algorithm. It does (linear time) pre-processing on the query and then finds all exact occurrences of the query in the string (as you may be alluding, you can also modify KMP to report maximal exactly matching prefixes of the query). This process takes time of order N+M where N is the length of the reference and M the length of the query.

On the other hand, STAR pre-computes a suffix array on the reference, and then uses this to answer exact prefix match queries across many different queries. This is a very different approach. Building the suffix array takes time linear in the reference, and storing the suffix array requires space linear in the reference (though the constant factor is pretty big). However, it allows enumerating all occurrences of a query Q in the reference R in time $O(k + lg(\left|R\right|)+ \left|Q\right|)$ where $k$ is the number of occurences of Q in R. This holds not just for the whole pattern, but for any maximal prefix as well. Also, in practice, STAR does this much faster by building a lookup table that maps small prefixes (say, all length 12 prefixes) to the contiguous suffix array interval where they occur. In practice, this gives very fast lookup of queries. Again, a key difference between this kind of approach and KMP is that the suffix array pre-processes the reference and therefore builds an index that works for many different queries (the sequencing reads), while KMP pre-processes the query to find all of its occurrences on the reference. Another key difference is that, while the KMP algorithm is always linear in the length of the reference to return all matches in the worst case, the suffix array can be considerably faster.

In the original STAR publication, this is mentioned in the supplementary material in section 1.2 "Pre-indexing of suffix arrays". This idea (along with others) is also covered in quite some depth in this paper. Basically, the look up table has been a folk technique for a long time, but it's not clear there is an "original" source for it.