Algebraic Genomics: The Combinatorics of Sequence Reconstruction and Representation

Sequencing does not read a genome; it reads its words. From short reads one learns, at best, the multiset of k-mers of a genome and of its reverse complement. This book determines exactly how much that multiset leaves undetermined: the set of genomes compatible with the data (the fibre) is counted exactly, the moves connecting its members are described, the point where exact counting becomes intractable is proved, and the same fibres are located in machine-learning representations of biological sequences. Part I, one strand. The fibre is the set of Eulerian circuits of a de Bruijn multigraph, and by the BEST theorem its size factors into a local part and the order of the graph's sandpile (critical) group. The global part is not determined by branch statistics. The group acts as a coordinate system on reconstructions, splits along repeats into a part that longer k-mers remove and a part that no k removes, and has no pairwise description for repeats with three or more copies. Part II, two strands. The reverse-complement double cover keeps every single-strand lemma, but its involution is an anti-automorphism of the Laplacian. The double-stranded count becomes a sum of determinants over the lattice points of a box: for bacteriophage φX174 at k = 10 the box has 2,481,687,900 points and the count is 31,925,753,246,212, obtained by frontier elimination, a fermionic (Berezin) form of the matrix-tree theorem, and exact multimodular enumeration. Double-stranded reconstruction counting is proved #P-hard. Part III, fibres and moves. Inversions at inverted repeats span the full anti-invariant lattice (a Tate-cohomology dichotomy), and a double-stranded Ukkonen–Pevzner conjecture is stated. Spectral fibres of all 20,431 reviewed human proteins are computed, with explicit protein pairs that pseudo amino acid composition and window-limited convolutional encoders cannot distinguish (chapter written with Zhengyi Chen). Polyploid phasing is treated as a decomposition of a pooled flow, and pan-genomes through a recombination group that can carry torsion. Part IV, algorithms. The E. coli K-12 de Bruijn graph (4.6 million vertices) reduces to a 115-vertex skeleton. The single-strand determinant is computed in linear time along the snarl tree by Schur complements. A BEST identity is given for the integer points of the isoform decomposition polytope of a splicing graph. 17 chapters, 154 pages. Every number in the text, tables and figures is produced by an accompanying verification script; scripts, reference transcripts and data are in the linked GitHub repository. Texts and figures: CC BY 4.0. Code: MIT License.