Magic & Math with Cards

Lecture 24 · Mathematics

From card windows to DNA reads

Video in production

This lecture is still face down. Its script is written; filming and animation are under way.

Meanwhile, read the outline

What you will learn

Assemble a clean toy DNA string from its exact multiset of overlapping 3-mers using a directed edge trail.

Before this lecture

Ideas you will use

  • Directed word graphs
  • DNA alphabet A, C, G, T introduced here

In this lecture

An outline of the lecture, scene by scene, with the statements that appear on screen. It follows the draft script, so details may change in production.

  1. Distinguish localization from reconstruction

    • Toy model: all 3-letter windows, exact multiplicity
    • Known direction; no errors or missing data
    • Assembly≠full de Bruijn cycle

  2. Build edges from 3 mer prefix suffix

    • ATG: AT→TG
    • Overlap TG written once
    • Vertices=contexts; edges=fragment occurrences

  3. Find start and end using degree imbalance

    • Start: out=in+1
    • End: in=out+1
    • Internal contexts: in=out

  4. Spell sequence and verify reads backwards

    • AT +G+C+T+A+C=ATGCTAC
    • Length=m+k−1
    • Re-extract windows to check data

  5. Explain multiset and duplicate edge occurrences

    • AAA×3, not{AAA}
    • Three edge occurrences at AA
    • Exact multiplicity is a toy assumption

  6. Connect longer reads and k-mer graph without false uniqueness

    • k-mer=edge between(k−1)-contexts
    • Long reads contain linkage information
    • Existence≠uniqueness

  7. Companion assembly task with actual multiset checks

    • Match the exact multiset
    • Continuity, coverage and boundaries
    • Worked answer ATGCTAC

  8. Retrieve correspondence and prepare ambiguity

    • Localization uses a known sequence
    • Assembly infers a sequence from windows
    • Next: two answers from same evidence

Companion interactive

Planned

Spell a linear string whose 3-mer multiset equals the input.

The interactive for this lecture is being built and will appear here.

Notes

Written notes for this lecture will appear here.

Sources

How these sources were used
  • Persi Diaconis and Ron Graham, Magical Mathematics: DNA overlap-graph motivation.
  • Pavel Pevzner, Haixu Tang and Michael Waterman, “An Eulerian path approach to DNA fragment assembly”: Primary Eulerian assembly reference; clean examples here are explicit teaching models.