Fundamentals of Stringology II: Probability and Statistics for Sequence Alignment
summary
Distinguishes exact versus non-overlapping vs overlapping pattern counts, shows non-overlap increases mean waiting time (example HTHTH gives probability P Q Q^2), and warns naive binomial tests misestimate variance; longest common subsequence has a Kingman limit but the constant is unknown (empirical 0.82 vs 0.5), local alignment scores sit at log n growth or linear growth with a sharp phase transition between log and linear growth, BLAST E‑values use Poisson heuristics, D2 word counts need Stein's method because variance can be order n^2 or n^3.
AI-written summary · about
chapters (10)
- 0:00Pattern counting basics
- 2:26Overlap and variance
- 7:19Global vs local alignment
- 11:12Statistical significance
- 13:36Alignment scoring theory
- 19:25Intuition and heuristics
- 24:20Limit laws and robustness
- 30:13Local alignment statistics
- 36:28Multivariate word counts
- 44:55Applications and conclusions
related talks
24mString Comparison in Real Life
29mApplying Randomized Methods for Zonotope Enumeration and...
28mSome Current Computational Challenges in Bioinformatics
47mTypical Bioinformatics Tasks
43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust
41mGeneralization Bounds for Uniformly Stable Algorithms
26mMathematical Approaches to Clustering
27mSampling Algorithms to Count Frequent Patterns in Graphs