Rosalind — Bioinformatics Stronghold — Strings

KMP — Speeding Up Motif Finding

The failure array records, for each prefix, the longest proper prefix that is also a suffix — so a mismatch can resume without re-reading the text. That is what makes matching linear rather than quadratic, and it is the same insight the trie and suffix-array problems generalise.

TRIE — Introduction to Pattern Matching

solved Problem statement

Patterns sharing a prefix share a path, so the text is scanned once regardless of how many patterns are sought. That is the property that makes trie matching worth building, and BA9A and BA9B use it directly.

LING — Linguistic Complexity of a Genome

solved Problem statement

The fraction of substrings that actually occur out of all that could. Repetitive sequence scores low because it reuses the same substrings — which is exactly what makes repeats hard to assemble through, as GREP demonstrates.

LREP — Finding the Longest Multiple Repeat

solved Problem statement

Rosalind supplies the suffix tree as an edge list, so nothing has to build one — the work is counting leaves below each node, which is how often the path to it occurs.

MREP — Identifying Maximal Repeats

solved Problem statement

Read off the LCP array: a value of at least 20 is a candidate repeat, kept when its occurrences do not all share the character before them.

SUFF — Encoding Suffix Trees

solved Problem statement

Built from the suffix array and LCP array rather than by collapsing a trie. Both give the same tree; a trie of all suffixes has O(n^2) nodes first, whereas the arrays are linear — which is why aligners store the arrays and never materialise the tree.