Eric Coissac
6acafa7f2c
Introduces a comprehensive documentation set covering theoretical foundations, CLI usage, installation, and system architecture. Adds MkDocs configuration and Makefile targets to generate, serve with live reload, and clean the documentation site. Includes citation styles and bibliography files for academic references.
29 lines
1.4 KiB
Markdown
29 lines
1.4 KiB
Markdown
# DNA encoding
|
||
|
||
## 2-bit nucleotide encoding
|
||
|
||
Every nucleotide is encoded on 2 bits, most-significant-bit first within each word:
|
||
|
||
| Base | Encoding |
|
||
|------|----------|
|
||
| A | `00` |
|
||
| C | `01` |
|
||
| G | `10` |
|
||
| T | `11` |
|
||
|
||
The Watson-Crick complement of a base is its bitwise NOT on 2 bits: $\text{complement}(base) = \lnot base \mathbin{\&} \texttt{0b11}$.
|
||
|
||
## Kmer encoding
|
||
|
||
A kmer of length $k$ ($k \le 31$) fits in a single 64-bit word. The first nucleotide occupies the two most significant bits, each following nucleotide occupies the next two bits, and unused low-order bits are zero. Extracting nucleotide i (0-indexed from the 5′ end) is a shift-and-mask operation.
|
||
|
||
Reverse complement is computed by bit manipulation directly on the packed word, without any lookup table: complement every base, reverse the byte order, then reverse the order of 2-bit groups within each byte in two more passes, and finally realign the result to the most-significant bits.
|
||
|
||
## Canonical form
|
||
|
||
The canonical form of a kmer is the lexicographic minimum of the kmer and its reverse complement:
|
||
|
||
$$\text{canonical}(kmer) = \min\big(kmer,\ \text{revcomp}(kmer)\big)$$
|
||
|
||
Using the canonical form halves the kmer space and makes counting strand-independent: a kmer and its reverse complement are always treated as the same entity, regardless of which DNA strand was sequenced.
|