doc/theory/encoding/index.html


<!doctype html>
<html lang="en" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      
      
        <link rel="prev" href="../kmers_and_superkmers/">
      
      
        <link rel="next" href="../entropy_filter/">
      
      
      <link rel="icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.7.6">
    
    
        <title>DNA encoding - obikmer — User Guide</title>
      
    
      <link rel="stylesheet" href="../../assets/stylesheets/main.484c7ddc.min.css">
      
      
        <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,300i,400,400i,700,700i%7CRoboto+Mono:400,400i,700,700i&display=fallback">
        <style>:root{--md-text-font:"Roboto";--md-code-font:"Roboto Mono"}</style>
      
    
    <script>__md_scope=new URL("../..",location),__md_hash=e=>[...e].reduce(((e,_)=>(e<<5)-e+_.charCodeAt(0)),0),__md_get=(e,_=localStorage,t=__md_scope)=>JSON.parse(_.getItem(t.pathname+"."+e)),__md_set=(e,_,t=localStorage,a=__md_scope)=>{try{t.setItem(a.pathname+"."+e,JSON.stringify(_))}catch(e){}}</script>
    
      
  </head>
  
  
    <body dir="ltr">
  
    
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" for="__drawer"></label>
    <div data-md-component="skip">
      
        
        <a href="#dna-encoding" class="md-skip">
          Skip to content
        </a>
      
    </div>
    <div data-md-component="announce">
      
    </div>
    
    
<header class="md-header md-header--shadow" data-md-component="header">
  <nav class="md-header__inner md-grid" aria-label="Header">
    <a href="../.." title="obikmer — User Guide" class="md-header__button md-logo" aria-label="obikmer — User Guide" data-md-component="logo">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 0 0 3-3 3 3 0 0 0-3-3 3 3 0 0 0-3 3 3 3 0 0 0 3 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54"/></svg>

    </a>
    <label class="md-header__button md-icon" for="__drawer">
      
      <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 6h18v2H3zm0 5h18v2H3zm0 5h18v2H3z"/></svg>
    </label>
    <div class="md-header__title" data-md-component="header-title">
      <div class="md-header__ellipsis">
        <div class="md-header__topic">
          <span class="md-ellipsis">
            obikmer — User Guide
          </span>
        </div>
        <div class="md-header__topic" data-md-component="header-topic">
          <span class="md-ellipsis">
            
              DNA encoding
            
          </span>
        </div>
      </div>
    </div>
    
    
      <script>var palette=__md_get("__palette");if(palette&&palette.color){if("(prefers-color-scheme)"===palette.color.media){var media=matchMedia("(prefers-color-scheme: light)"),input=document.querySelector(media.matches?"[data-md-color-media='(prefers-color-scheme: light)']":"[data-md-color-media='(prefers-color-scheme: dark)']");palette.color.media=input.getAttribute("data-md-color-media"),palette.color.scheme=input.getAttribute("data-md-color-scheme"),palette.color.primary=input.getAttribute("data-md-color-primary"),palette.color.accent=input.getAttribute("data-md-color-accent")}for(var[key,value]of Object.entries(palette.color))document.body.setAttribute("data-md-color-"+key,value)}</script>
    
    
  </nav>
  
</header>
    
    <div class="md-container" data-md-component="container">
      
      
      <main class="md-main" data-md-component="main">
        <div class="md-main__inner md-grid">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="sidebar" data-md-type="navigation" >
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    

<nav class="md-nav md-nav--primary" aria-label="Navigation" data-md-level="0">
  <label class="md-nav__title" for="__drawer">
    <a href="../.." title="obikmer — User Guide" class="md-nav__button md-logo" aria-label="obikmer — User Guide" data-md-component="logo">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 0 0 3-3 3 3 0 0 0-3-3 3 3 0 0 0-3 3 3 3 0 0 0 3 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54"/></svg>

    </a>
    obikmer — User Guide
  </label>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
    <li class="md-nav__item">
      <a href="../.." class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Home
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../installation/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Installation
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item md-nav__item--active md-nav__item--nested">
      
        
        <input class="md-nav__toggle md-toggle " type="checkbox" id="__nav_3" checked>
        
          
          <label class="md-nav__link" for="__nav_3" id="__nav_3_label" tabindex="0">
            
  
  <span class="md-ellipsis">
    
  
    Theory
  

  </span>
  
  
            <span class="md-nav__icon md-icon"></span>
          </label>
        
        <nav class="md-nav" data-md-level="1" aria-labelledby="__nav_3_label" aria-expanded="true">
          <label class="md-nav__title" for="__nav_3">
            <span class="md-nav__icon md-icon"></span>
            
  
    Theory
  

          </label>
          <ul class="md-nav__list" data-md-scrollfix>
            
              
    <li class="md-nav__item">
      <a href="../kmers_and_superkmers/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Kmers and super-kmers
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item md-nav__item--active">
      
      <input class="md-nav__toggle md-toggle" type="checkbox" id="__toc">
      
      
        <label class="md-nav__link md-nav__link--active" for="__toc">
          
  
  <span class="md-ellipsis">
    
  
    DNA encoding
  

  </span>
  
  
          <span class="md-nav__icon md-icon"></span>
        </label>
      
      <a href="./" class="md-nav__link md-nav__link--active">
        
  
  <span class="md-ellipsis">
    
  
    DNA encoding
  

  </span>
  
  
      </a>
      
        
<nav class="md-nav md-nav--secondary" aria-label="Table of contents">
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon"></span>
      Table of contents
    </label>
    <ul class="md-nav__list" data-md-component="toc" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#2-bit-nucleotide-encoding" class="md-nav__link">
    <span class="md-ellipsis">
      
        2-bit nucleotide encoding
      
    </span>
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#kmer-encoding" class="md-nav__link">
    <span class="md-ellipsis">
      
        Kmer encoding
      
    </span>
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#canonical-form" class="md-nav__link">
    <span class="md-ellipsis">
      
        Canonical form
      
    </span>
  </a>
  
</li>
      
    </ul>
  
</nav>
      
    </li>
  

    <li class="md-nav__item">
      <a href="../entropy_filter/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Low-complexity kmer filter
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../minimizer_selection/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Minimizer selection
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../indexing_architecture/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Partitioning and indexing architecture
  

  </span>
  
  
      </a>
    </li>
  

          </ul>
        </nav>
      
    </li>
  

    <li class="md-nav__item md-nav__item--nested">
      
        
        <input class="md-nav__toggle md-toggle " type="checkbox" id="__nav_4" >
        
          
          <label class="md-nav__link" for="__nav_4" id="__nav_4_label" tabindex="0">
            
  
  <span class="md-ellipsis">
    
  
    Usage
  

  </span>
  
  
            <span class="md-nav__icon md-icon"></span>
          </label>
        
        <nav class="md-nav" data-md-level="1" aria-labelledby="__nav_4_label" aria-expanded="false">
          <label class="md-nav__title" for="__nav_4">
            <span class="md-nav__icon md-icon"></span>
            
  
    Usage
  

          </label>
          <ul class="md-nav__list" data-md-scrollfix>
            
              
    <li class="md-nav__item">
      <a href="../../usage/superkmer/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    superkmer
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/index_command/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    index
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/merge/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    merge
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/filter/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    filter
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/select/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    select
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/query/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    query
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/dump/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    dump
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/annotate/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    annotate
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/phylo/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    phylo
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/name-tree/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    name-tree
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/unitig/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    unitig
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/estimate/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    estimate
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/reindex/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    reindex
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/utils/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    utils
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/pack/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    pack
  

  </span>
  
  
      </a>
    </li>
  

    <li class="md-nav__item">
      <a href="../../usage/predicates/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Predicates and taxonomy paths
  

  </span>
  
  
      </a>
    </li>
  

          </ul>
        </nav>
      
    </li>
  

    <li class="md-nav__item md-nav__item--nested">
      
        
        <input class="md-nav__toggle md-toggle " type="checkbox" id="__nav_5" >
        
          
          <label class="md-nav__link" for="__nav_5" id="__nav_5_label" tabindex="0">
            
  
  <span class="md-ellipsis">
    
  
    Formats
  

  </span>
  
  
            <span class="md-nav__icon md-icon"></span>
          </label>
        
        <nav class="md-nav" data-md-level="1" aria-labelledby="__nav_5_label" aria-expanded="false">
          <label class="md-nav__title" for="__nav_5">
            <span class="md-nav__icon md-icon"></span>
            
  
    Formats
  

          </label>
          <ul class="md-nav__list" data-md-scrollfix>
            
              
    <li class="md-nav__item">
      <a href="../../formats/index_layout/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Index construction and on-disk layout
  

  </span>
  
  
      </a>
    </li>
  

          </ul>
        </nav>
      
    </li>
  

    <li class="md-nav__item">
      <a href="../../architecture/" class="md-nav__link">
        
  
  <span class="md-ellipsis">
    
  
    Architecture notes
  

  </span>
  
  
      </a>
    </li>
  

  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
              <div class="md-sidebar md-sidebar--secondary" data-md-component="sidebar" data-md-type="toc" >
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    

<nav class="md-nav md-nav--secondary" aria-label="Table of contents">
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon"></span>
      Table of contents
    </label>
    <ul class="md-nav__list" data-md-component="toc" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#2-bit-nucleotide-encoding" class="md-nav__link">
    <span class="md-ellipsis">
      
        2-bit nucleotide encoding
      
    </span>
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#kmer-encoding" class="md-nav__link">
    <span class="md-ellipsis">
      
        Kmer encoding
      
    </span>
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#canonical-form" class="md-nav__link">
    <span class="md-ellipsis">
      
        Canonical form
      
    </span>
  </a>
  
</li>
      
    </ul>
  
</nav>
                  </div>
                </div>
              </div>
            
          
            <div class="md-content" data-md-component="content">
              
              <article class="md-content__inner md-typeset">
                
                  
<h1 id="dna-encoding">DNA encoding</h1>
<h2 id="2-bit-nucleotide-encoding">2-bit nucleotide encoding</h2>
<p>Every nucleotide is encoded on 2 bits, most-significant-bit first within each word:</p>
<table>
<thead>
<tr>
<th>Base</th>
<th>Encoding</th>
</tr>
</thead>
<tbody>
<tr>
<td>A</td>
<td><code>00</code></td>
</tr>
<tr>
<td>C</td>
<td><code>01</code></td>
</tr>
<tr>
<td>G</td>
<td><code>10</code></td>
</tr>
<tr>
<td>T</td>
<td><code>11</code></td>
</tr>
</tbody>
</table>
<p>The Watson-Crick complement of a base is its bitwise NOT on 2 bits: <span class="arithmatex">\(\text{complement}(base) = \lnot base \mathbin{\&amp;} \texttt{0b11}\)</span>.</p>
<h2 id="kmer-encoding">Kmer encoding</h2>
<p>A kmer of length <span class="arithmatex">\(k\)</span> (<span class="arithmatex">\(k \le 31\)</span>) 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.</p>
<p>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.</p>
<h2 id="canonical-form">Canonical form</h2>
<p>The canonical form of a kmer is the lexicographic minimum of the kmer and its reverse complement:</p>
<div class="arithmatex">\[\text{canonical}(kmer) = \min\big(kmer,\ \text{revcomp}(kmer)\big)\]</div>
<p>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.</p>


              </article>
            </div>
          
          
<script>var target=document.getElementById(location.hash.slice(1));target&&target.name&&(target.checked=target.name.startsWith("__tabbed_"))</script>
        </div>
        
      </main>
      
        <footer class="md-footer">
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-copyright">
  
  
    Made with
    <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
      Material for MkDocs
    </a>
  
</div>
      
    </div>
  </div>
</footer>
      
    </div>
    <div class="md-dialog" data-md-component="dialog">
      <div class="md-dialog__inner md-typeset"></div>
    </div>
    
    
      <script id="__config" type="application/json">{"annotate": null, "base": "../..", "features": [], "search": "../../assets/javascripts/workers/search.2c215733.min.js", "tags": null, "translations": {"clipboard.copied": "Copied to clipboard", "clipboard.copy": "Copy to clipboard", "search.result.more.one": "1 more on this page", "search.result.more.other": "# more on this page", "search.result.none": "No matching documents", "search.result.one": "1 matching document", "search.result.other": "# matching documents", "search.result.placeholder": "Type to start searching", "search.result.term.missing": "Missing", "select.version": "Select version"}, "version": null}</script>
    
    
      <script src="../../assets/javascripts/bundle.79ae519e.min.js"></script>
      
        <script src="https://unpkg.com/mathjax@3/es5/tex-mml-chtml.js"></script>
      
    
  </body>
</html>