Magic & Math with Cards

Lecture 25 · Mathematics

When the same clues fit two sequences

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

Distinguish compatible assembly, unique reconstruction and robustness using exact small counterexamples.

Before this lecture

Ideas you will use

  • Overlap graphs

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 a compatible reconstruction from a unique answer

    • Exact three-mer multiset
    • One linear string; known orientation
    • One answer ≠ unique answer

  2. Verify two strings with identical complete evidence

    • AACAAGAA
    • AAGAACAA
    • Same six three-mers, once each

  3. Explain ambiguity through two excursions sharing a context

    • Two closed excursions meet at AA
    • C then G, or G then C
    • A tie-break is not evidence

  4. Add a longer linked read that distinguishes candidates

    • CAAG occurs only in AACAAGAA
    • CAA + AAG loses their linkage
    • A separating read must cross the ambiguity

  5. Show missing data changes the interpretation of edge usage

    • Exact data: five edges → seven letters
    • Missing data: absence need not exclude
    • Observed edge ≠ proposed edge

  6. Show errors can destroy a valid overlap traversal

    • Altered fragment AAC→AAT
    • Compatible alternative: ACAAGAAT
    • Known start AA detects this inconsistency

  7. Specify ambiguity game and certificates

    • Find two compatible strings
    • Add CAAG to distinguish them
    • State the search space for uniqueness

  8. Retrieve distinctions and connect to decoding

    • Construction
    • Identification
    • Robustness

Companion interactive

Planned

Exhibit ambiguity and identify a separating observation.

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 connection; the two eight-letter strings and diagnostic exercises are original checked teaching examples.