Read Mapping

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.

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">{{hint}}</p>
<div class="ref">ref&nbsp;=&nbsp;<span id="refstr"></span></div>
<label class="readpick">{{read_label}}
  <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">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

How hard is read mapping, really?

• Brute force slides each read across every position of the reference: about $genome \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 \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)$, 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.

"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.

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.