Analytic Pattern Matching: From DNA to Twitter
summary
Counts occurrence distributions for patterns in memoryless and Markov texts using combinatorial generating functions built from R, M, U language decompositions and an autocorrelation polynomial to encode overlaps; this yields a system of algebraic equations whose analytic continuation gives exact probabilities for “exactly k” occurrences, and produces central limit and large-deviation laws. Joint substring counts define string complexity for pairs (used on Twitter) and conditional-entropy thresholds shift motif significance massively (example: rank 5 → rank ~4,000 after conditioning).
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:32Google
- 3:08Twitter
- 4:22General Definition
- 5:09General Pattern Matching
- 6:24Unconstrained Pattern Matching
- 7:48Book
- 9:26Application
- 11:18Analogies
- 14:26Language
- 17:56Relation between languages
- 20:23Non trivial example
related talks
53mApplied Functional Programming in Computational Genomics
27mTed Dunning, Chief Application Architect, MapR
01h 20mIntroduction to Regulatory Genomics and Epigenomics II: Motif Finding
13mGenetic Regex
47mPattern Search (Data Mining: Pattern Discovery)
42mDetecting novel anomalies in Twitter
31mUsing Simpson’s Paradox to Discover Interesting Patterns in...
01h 08mTutorial: Methods from Statistical Physics III