Algorithms for Sequence Analysis

Suffix Tree / Array

Demo Text:

T := ACAGTCACAGTGTCACA$

`i`	`pos[i]`	`rank[i]`	`lcp[i]`	suffix
0	17	3	-1	`$`
1	16	10	0	`A$`
2	14	5	1	`ACA$`
3	0	13	3	`ACAGTCACAGTGTCACA$`
4	6	16	5	`ACAGTGTCACA$`
5	2	9	1	`AGTCACAGTGTCACA$`
6	8	4	3	`AGTGTCACA$`
7	15	11	0	`CA$`
8	13	6	2	`CACA$`
9	5	14	4	`CACAGTGTCACA$`
10	1	17	2	`CAGTCACAGTGTCACA$`
11	7	12	4	`CAGTGTCACA$`
12	11	15	0	`GTCACA$`
13	3	8	6	`GTCACAGTGTCACA$`
14	9	2	2	`GTGTCACA$`
15	12	7	0	`TCACA$`
16	4	1	5	`TCACAGTGTCACA$`
17	10	0	1	`TGTCACA$`
18	–	–	-1	–

Given a (lexicographical) order, a (w, k)-minimizer of a string is the smallest k-mer in a surrounding window of w consecutive k-mers.

Minimizers:

AAGAGCAGGAAT