DNA Sequence Analysis
DNA sequencing is a fundamental technique in molecular biology that determines the precise order of nucleotides (A, C, G, and T) in a DNA molecule. One interesting mathematical problem in DNA sequencing involves reconstructing a DNA sequence from its constituent triplets.
When a DNA strand interacts with a sequencing array, each consecutive triplet (three consecutive nucleotides) in the strand is highlighted in the array. Given these highlights, can we determine the original DNA sequence?
This is an example of sequence reconstruction from triplets. In the array, each cell represents a possible triplet of nucleotides. When a DNA sequence is analyzed, all triplets present in the sequence are highlighted.
For example, the sequence AACTCCAGTATGGC contains these triplets:
- AAC (positions 1-3)
- ACT (positions 2-4)
- CTC (positions 3-5)
- TCC (positions 4-6)
- CCA (positions 5-7)
- CAG (positions 6-8)
- AGT (positions 7-9)
- GTA (positions 8-10)
- TAT (positions 9-11)
- ATG (positions 10-12)
- TGG (positions 11-13)
- GGC (positions 12-14)
The reverse problem is even more interesting: given only the highlighted cells in the array, can you determine the original DNA sequence? This is a classic example of sequence reconstruction from overlapping fragments, which has important applications in genome sequencing and assembly.
Middle Layer Graph
For an odd number n = 2r + 1, the middle layer graph has a vertex for every r-element subset and every (r+1)-element subset of {1, …, n}, with an edge between two subsets whenever one contains the other.
Session notes
We finished the second half of chapter 3 of Magical Mathematics, covering DNA sequencing via Euler walks and the middle-layers Hamiltonian cycle conjecture. Both problems grow from the same soil as de Bruijn sequences but land in very different places.
0:30 DNA sequencing: a chip with cells, one per triplet over , lights up every triplet a strand contains as a substring (left to right, no wraparound). The authors simplify heavily to extract a clean combinatorics-on-words problem, assuming reads are accurate.
3:32 The second problem previewed: a transition array recording consecutive-pair frequencies; reconstruct a string from the matrix alone.
5:39 A string of length has triplets but often fewer distinct highlights. A long run of A’s followed by G’s lights up only AAA, AAG, AGG, GGG.
7:45 The table does not determine the strand. gives those same four highlights for any , so the realistic goal is finding any compatible string.
8:47 The algorithm uses Euler walks. Vertices are the 16 letter-pairs; each highlighted triplet adds an edge . Walk every edge once, writing the start vertex’s label and then the second letter of each vertex reached: the output reproduces every highlight, by the same induction as for de Bruijn sequences.
12:58 No Euler walk means the table is inconsistent: any real string traces an Euler walk in its own graph.
15:01 An open Euler walk requires in-degree equal to out-degree everywhere except one start vertex (one extra out-edge) and one end vertex (one extra in-edge). Both conditions are polynomial-time checkable, and a DFS-with-a-stack algorithm recovers one compatible string.
17:04 Real sequencing has errors and shotgun data. De Bruijn graphs underlie the sophisticated assembly algorithms; the book leaves the details there.
19:19 Comparing strings requires a distance: Hamming for equal lengths, edit distance (insert, delete, or substitute one letter) otherwise. Distance 137 means nothing without a baseline.
21:23 Calibration: generate many random strings sharing the same signature and compare. I am treating “why this calibrates” as a black box.
22:29 The signature is the transition array: entry counts the consecutive pair as a substring, no wraparound, so entries range from 0 to .
23:30 To generate strings with a given signature, build a multigraph on with edge multiplicity equal to the matrix entry. Any Euler walk, decrementing each edge on use, spells out a string with exactly that signature.
26:38 Sunita asked why an Euler walk should exist. For an arbitrary matrix it need not; a matrix from a real string admits at least that string’s walk.
28:43 A difference between the two problems: the triplet version ignores multiplicities, so the A’s-then-G’s table always yields a length-6 string regardless of and , while the pair version keeps counts, so every Euler walk has the original string’s length. I do not know why the book does not count triplet multiplicities.
30:46 I skipped the probability remarks; the chapter closes with a story about a workshop at Banff and the feel of a good meeting.
31:48 From Euler circuits (every edge once, tractable) to Hamiltonian cycles (every vertex once, hard). Middle-layers problem: odd; vertices are the -subsets and -subsets of ; edges join each set to its one-element supersets.
33:55 The Hasse diagram of the Boolean lattice gives context. For odd the two middle layers have sizes and , and the induced graph is the one we want.
37:03 Examples: , singletons against pairs; , 2-subsets against 3-subsets. Conjecture: the middle-layers graph always has a Hamiltonian cycle. Verified by computer for all odd at the time of the book.
38:16 At the Banff meeting, Johnson proved a near-miss: for every odd , a path visiting all but a vanishingly small fraction of vertices. I did not check the current status; if anyone knows of updates, please share.
40:21 The book: “we felt the wheels in our heads turn.” The section also makes a case for fundamental research whose uses cannot be anticipated.
41:24 Up next: chapter 4, universal cycles. Five spectators draw from a cut deck arranged so there are no ties; the positions of whoever holds the top three by rank determine all five cards.
43:26 My worry: a spectator cannot unilaterally know they hold the highest card without conferring, which is clumsy and might leak information. To sort out: when can a cyclic arrangement make the top-three-rank ordering distinct at every cut, replacing bit patterns by orderings?
47:45 Thanks to Ravi, Prateek, Vinod and Sunita.
To think about
- Write out the induction showing an Euler walk in the pair graph reproduces the full signature.
- Show that a string’s own graph satisfies the open-Euler-walk degree condition.
- Redo the triplet reconstruction keeping multiplicities; compare output lengths.
- Draw the middle-layers graph for and find a Hamiltonian cycle by hand.
- Look up the current status of the middle-layers conjecture.