Algorithmic Foundations of
Computational Biology

Foundational Genomics

Mastery of central dogma transformations, string parsing, frequency counting, Mendelian probability, and Python standard data structures.

• DNA Transcription, Reverse Complement, GC Skew
• Mendelian Inheritance & Expected Offspring
• Point Mutations & Hamming Distance
• Rosalind Armory FASTQ Quality Filtering
• Python Village syntax & file manipulation

Core Algorithms & DP

Dynamic programming alignments, Eulerian graph de novo genome assembly, motif finding heuristics, and distance-based phylogenetics.

• Needleman-Wunsch, Smith-Waterman & Affine Gaps
• Hirschberg Linear-Space Alignment ($O(|v|+|w|)$)
• De Bruijn Graphs & Eulerian Walk Assembly
• Median String, Gibbs Sampler & Randomized Motif Search
• Additive Phylogeny, UPGMA & Neighbor-Joining

Complex Stochastic Modeling

Baum-Welch Expectation-Maximization for HMMs, mass spectrometry spectral dictionaries, 2-break genome synteny distances, and suffix trees.

• Baum-Welch Parameter Estimation & Profile HMMs
• De Novo Peptide Sequencing from Mass Spectra
• Genome Rearrangements (2-Break & Reversal Distances)
• Suffix Trees & Burrows-Wheeler Transform Matching
• Catalan Numbers & RNA Secondary Structures

Dynamic Programming Alignment Paradigms

Mathematical recurrences, boundary conditions, and space/time trade-offs across 7 alignment models: Global, Local, Fitting, Overlap, Semiglobal, Affine Gaps, and Hirschberg's linear space $O(n+m)$ algorithm.

Genome Assembly Paradigms

The paradigm shift from Overlap-Layout-Consensus (Hamiltonian path, NP-complete) to De Bruijn graph sequence assembly (Eulerian walk, linear $O(V+E)$ time), plus paired-end $(k, d)$-mer gapped reconstruction.

Complexity & Asymptotic Bounds Matrix

Master classification matrix mapping all 284 solved problems to their asymptotic time bounds ($O(n)$ streaming scans, $O(n \log n)$ divide-and-conquer, $O(nm)$ dynamic programming, $O(n^3)$ cubic RNA folding, and NP-complete heuristics).

Hidden Markov Models in Computational Biology

Unified mathematical treatment of the Three HMM Problems: Evaluation (Forward-Backward $P(x)$), Decoding (Viterbi $\pi^*$, Soft Decoding), and Parameter Learning (Baum-Welch EM), plus Profile HMMs for protein families.

Phylogenetics & Tree Reconstruction Paradigms

Mathematical taxonomy of evolutionary tree reconstruction: Additive metric spaces, 4-point condition, UPGMA, Neighbor-Joining, Small Parsimony (Fitch-Sankoff), Large Parsimony (NNI heuristics), and split distance metrics.

Peptide Sequencing & Mass Spectrometry

Tandem MS/MS ion fragmentation ($b$/$y$ series), branch-and-bound cyclopeptide sequencing, leaderboard beam search, spectral convolution for amino acid discovery, spectrum graph DAGs, and PSM dictionaries.

String Indexing & Pattern Matching Synthesis

From Suffix Tries and compact Suffix Trees to Suffix Arrays, the Burrows-Wheeler Transform (BWT), and the FM-Index with $O(m)$ exact backward search and inexact approximate matching via Pigeonhole seeds.

Genome Rearrangements & Synteny Synthesis

Signed permutations, Hannenhalli-Pevzner duality theorem, breakpoint graphs, alternating cycle decompositions, and the universal 2-Break Distance Theorem $d(P, Q) = b - c$ for multi-chromosomal karyotypes.

Combinatorics & Population Genetics Synthesis

Mendelian inheritance laws, the Wright-Fisher Markov model of genetic drift and allele fixation, Catalan/Motzkin non-crossing matchings in RNA secondary structure, and Nussinov/Zuker DP folding algorithms.