Notations used in the paper
| Notation | Meaning | Example |
|---|---|---|
| Σ | the DNA alphabet: {A, C, G, T} | |
| S | a sequence using Σ | S = AGTTC |
| m | length of S | m = 5 for S = AGTTC |
| k-mer | a sequence of length k | ACG (for k = 3) |
| n | number of k-mers in S: m − k + 1 | n = 3 for S = AGTTC |
| S[i] | the ith character of S | S[1] = A for S = AGTTC |
| si | the k-mer starting at the ith position of S | s2 = GTT for S = AGTTC |
| ⊕ | the “exclusive or” (XOR) operation | 110 ⊕ 100 = 010 |
| ≫, ≪ | shift right and shift left operations | 100101 ≫ 2 = 001001 |
| and | bitwise “and” operation | 110 and 100 = 100 |
| rold(x) | d cyclic left rotations of x | rol2(100100) = 010010 |
| u · v | dot product of u and v | (1, 0, 1) · (1, 1, 0) = 1 + 0 + 0 = 1 |
| J( · , · ) | the Jaccard similarity: | X = {a, b, c}, Y = {c, d} |
| [n] | the integers between 0 and n − 1 | |
| h : U → [B] | a hash function from a universe U to the integers [B] | |
| domain of h | the set U | all 64-bit integers |
| codomain of h | the set [B] | all 4-bit integers |
| image of h | {h(x)|x ∈ U} | all odd 4-bit integers |
| π : U → [|U|] | a permutation: a bijective hash function | for 0 ≤ M < |U|, where |U| is a power of 2 |
| {hθ|θ ∈ Θ} | a family of hash functions with seeds chosen from Θ | |
| sim( · , · ) | a similarity measure associated with a metric space | s(X, Y) = J(X, Y) |
| spaced word | a subsequence extracted using a mask pattern | for mask 10011 and S = AGTTC, the extracted spaced word is ATC |