Introduction

A modern DNA sequencer does not read your genome from start to finish. It shreds it into millions of overlapping fragments — short reads, often just 100–150 letters of A, C, G and T — and reads those. To make sense of them, each read has to be placed back where it came from on a known reference genome: roughly three billion letters for a human.

That is read mapping: for every one of the hundreds of millions of reads, find the spot in the reference where it matches. Done naively — slide each read along the whole genome — it would take a single experiment days of computer time.

The surprise is that it doesn't. Tools like BWA and Bowtie map a read in time that barely depends on how long the genome is. The secret is to pay a one-time cost to index the reference cleverly — and the cleverness comes from a 1994 text-compression trick.

Try It: Align a Read with the FM-Index

Below is a tiny reference genome and a sorted table of all its suffixes — the heart of a suffix array / FM-index. Pick a short read, then press Step search. The index reads your read backwards, one letter at a time. Each letter shrinks the highlighted block of rows; when the read runs out, the rows that remain point straight at every place it occurs.

<p class="hint">A reference genome is one long string. The <b>FM-index</b> (built from the Burrows-Wheeler transform) lets you find where a short read occurs by reading the read <b>backwards</b>, one letter at a time, each step shrinking a range of matches. Pick a read and step through it.</p>
<div class="ref">ref&nbsp;=&nbsp;<span id="refstr"></span></div>
<label class="readpick">read:
  <select id="read">
    <option value="ACG">ACG</option>
    <option value="GCA">GCA</option>
    <option value="TAC">TAC</option>
    <option value="GGG">GGG</option>
  </select>
</label>
<div id="rotations" class="rot"></div>
<div class="status" id="status">Press "Step search" to read the pattern backwards.</div>
<div class="btns">
  <button id="step" type="button">Step search</button>
  <button id="auto" type="button">Find all matches</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ref { font: 600 15px ui-monospace, monospace; margin: .3rem 0 .6rem; letter-spacing: 1px; }
.ref .hit { background: #ffd166; border-radius: 3px; padding: 0 1px; }
.readpick { font-size: .9rem; display: inline-block; margin-bottom: .5rem; }
select { font: 600 14px ui-monospace, monospace; padding: .2rem .4rem; border-radius: 6px; border: 1px solid #1d3557; }
.rot { display: grid; gap: 2px; margin: .4rem 0; font: 600 14px ui-monospace, monospace; }
.row { display: flex; align-items: center; gap: 8px; padding: 1px 4px; border-radius: 4px; }
.row.inrange { background: #e8eef3; }
.row .idx { color: #8a96a3; width: 1.6em; text-align: right; }
.row .sfx { letter-spacing: 1px; }
.row .mk { color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// FM-index backward search. Reference T (ending in sentinel $) has a suffix array; sorting all rotations/suffixes groups every occurrence of any substring into one contiguous BLOCK of rows. Backward search reads the pattern right-to-left, and at each step the matching block [lo,hi) shrinks. The width of the final block = number of times the read occurs in the reference. This runs in O(read length), independent of how long the genome is — that is the trick behind BWA/Bowtie.
const T = "ACGTACGGGCA";            // reference (no sentinel shown to the player)
const S = T + "$";                  // sentinel sorts first
const n = S.length;

// Suffix array: indices of all suffixes, sorted lexicographically.
const SA = Array.from({length:n}, (_,i)=>i)
  .sort((a,b)=> S.slice(a) < S.slice(b) ? -1 : 1);
const suffix = i => S.slice(i);

// C[c] = number of chars in S strictly smaller than c. rank(c,k) = occurrences of c in BWT[0..k). We use the suffix array directly here for clarity (same result).
function backward(pattern){
  // Returns the SA range [lo,hi) of rows whose suffix starts with `pattern`.
  let lo = 0, hi = n, steps = [];
  for(let i = pattern.length - 1; i >= 0; i--){
    const ch = pattern[i];
    const want = pattern.slice(i);
    let nlo = n, nhi = 0;
    for(let r = 0; r < n; r++){
      if(suffix(SA[r]).startsWith(want)){ if(r<nlo)nlo=r; if(r+1>nhi)nhi=r+1; }
    }
    if(nlo>nhi){ nlo=0; nhi=0; }
    lo = nlo; hi = nhi;
    steps.push({ ch, want, lo, hi });
  }
  return { lo, hi, steps };
}

let pattern = "ACG", stepIdx = 0, cur = null;

function renderRef(positions){
  const cells = T.split('').map((c,i)=>
    positions.includes(i) ? '<span class="hit">'+c+'</span>' : c);
  document.getElementById('refstr').innerHTML = cells.join('');
}
function renderRows(lo,hi){
  const box = document.getElementById('rotations'); box.innerHTML='';
  for(let r=0;r<n;r++){
    const row=document.createElement('div');
    const inr = r>=lo && r<hi;
    row.className='row'+(inr?' inrange':'');
    row.innerHTML='<span class="idx">'+SA[r]+'</span>'+
      '<span class="sfx">'+suffix(SA[r]).replace('


Notice what is not happening: at no point do we scan the whole reference looking for the read. We add one letter and the matching block instantly narrows. The number of steps equals the length of the read, not the length of the genome — that is why a tool can map a 100-letter read against three billion letters almost as fast as against three thousand. Compare this to brute-force pattern search, which slides the read along every position; the same idea powers fast pattern matching and genome assembly.

,'·')+'</span>'+
      (inr?'<span class="mk">◀</span>':'');
    box.appendChild(row);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function reset(){
  pattern = document.getElementById('read').value;
  stepIdx = 0; cur = backward(pattern);
  renderRef([]); renderRows(0,n);
  setStatus(fmt('Range = whole table (%n% rows). Press "Step search".', { n: n }),'');
}
function positionsFor(lo,hi){
  const ps=[]; for(let r=lo;r<hi;r++) ps.push(SA[r]); return ps.filter(p=>p<T.length);
}
function step(){
  if(stepIdx >= cur.steps.length){
    const matches = positionsFor(cur.lo,cur.hi).sort((a,b)=>a-b);
    if(matches.length){ renderRef(matches);
      setStatus(fmt('Done. "%pattern%" occurs %length% time(s) at position(s) %matches%.', { pattern: pattern, length: matches.length, matches: matches.join(', ') }),'ok'); }
    else setStatus(fmt('"%pattern%" does not occur in the reference.', { pattern: pattern }),'bad');
    return;
  }
  const st = cur.steps[stepIdx++];
  renderRows(st.lo, st.hi);
  const w = st.hi - st.lo;
  setStatus(fmt('Add "%ch%" → match block for "%want%" is %w% row(s).', { ch: st.ch, want: st.want, w: w }), w>0?'':'bad');
  if(w===0) stepIdx = cur.steps.length; // collapsed: jump to final report
}
function auto(){ reset(); while(stepIdx < cur.steps.length) step(); step(); }

document.getElementById('step').addEventListener('click',step);
document.getElementById('auto').addEventListener('click',auto);
document.getElementById('reset').addEventListener('click',reset);
document.getElementById('read').addEventListener('change',reset);
reset();
Result
Console

Notice what is not happening: at no point do we scan the whole reference looking for the read. We add one letter and the matching block instantly narrows. The number of steps equals the length of the read, not the length of the genome — that is why a tool can map a 100-letter read against three billion letters almost as fast as against three thousand. Compare this to brute-force pattern search, which slides the read along every position; the same idea powers fast pattern matching and genome assembly.

The Real Complexity

How hard is read mapping, really?

  • Brute force slides each read across every position of the reference: about genome×readgenome \times read character comparisons per read. For a human genome and hundreds of millions of reads, that is hopeless.
  • Suffix array. Sort every suffix of the reference once. Now any read can be found by binary search in O(read×log⁡genome)O(read \times \log genome) time — and finding all of its occurrences comes for free, because they sit in one contiguous block.
  • Burrows-Wheeler transform + FM-index. In 1994 Michael Burrows and David Wheeler described a reversible reordering of a text (originally for compression). In 2000 Paolo Ferragina and Giovanni Manzini turned it into the FM-index, which supports backward search: scanning a read right-to-left, each step in O(1)O(1), for total time O(read length) — essentially independent of the genome — while the index itself is compressed close to the size of the genome.
  • Status: solved. Exact matching is not an open or hard problem; it is a textbook near-linear algorithm. The interactive demo above is verified to return exactly the same positions as brute-force search.

The genuine difficulty in real genomics is inexact matching — reads carry sequencing errors and real biological variants, so tools allow a few mismatches and gaps. That turns mapping into a controlled search around the exact-match machinery, and unlike the clean problems behind P vs NP, the core indexing question here is firmly on the easy side of the line.

Where It Matters

"Search one enormous text for many short strings" is a shape that shows up far beyond DNA:

  • Variant calling: map a patient's reads to the reference, then read off where their letters differ — the basis of diagnosing genetic disease and profiling tumors.
  • Metagenomics: match reads from a soil or gut sample against thousands of microbial genomes to see who is present.
  • RNA and epigenetics: the same mappers place reads from gene-expression and methylation experiments.
  • Beyond biology: the FM-index is a general compressed full-text index — useful for searching log archives, source-code corpora, and other big texts where you want both small storage and fast substring queries.

Learn how read mapping works and you've met the suffix array and the Burrows-Wheeler transform — the same indexing ideas behind fast pattern matching and the overlap detection in genome assembly.

Conclusion

Read mapping is a small miracle of the right data structure. Searching three billion letters for a short read sounds hopeless, yet by indexing the genome once — with a transform invented for compression — every read finds its home in steps counted by the read's own length, not the genome's.

It is a clean reminder that not every important problem is intractable. While questions like P vs NP sit unresolved, modern genomics rests on an algorithm that is provably fast, exact, and beautiful — and it runs millions of times a day in labs around the world.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/read-mapping/Content licensed under CC BY-NC 4.0.