| Introduction | p. 1 |
| Ubiquity of Patterns | p. 1 |
| Motivations from Biology | p. 2 |
| The Need for Rigor | p. 2 |
| Who is a Reader of this Book? | p. 3 |
| About this book | p. 4 |
| The Fundamentals | p. 7 |
| Basic Algorithmics | p. 9 |
| Introduction | p. 9 |
| Graphs | p. 9 |
| Tree Problem 1: Minimum Spanning Tree | p. 14 |
| Prim's algorithm | p. 17 |
| Tree Problem 2: Steiner Tree | p. 21 |
| Tree Problem 3: Minimum Mutation Labeling | p. 22 |
| Fitch's algorithm | p. 23 |
| Storing & Retrieving Elements | p. 27 |
| Asymptotic Functions | p. 30 |
| Recurrence Equations | p. 32 |
| Counting binary trees | p. 34 |
| Enumerating unrooted trees (Prufer sequence) | p. 36 |
| NP-Complete Class of Problems | p. 40 |
| Exercises | p. 41 |
| Basic Statistics | p. 47 |
| Introduction | p. 47 |
| Basic Probability | p. 48 |
| Probability space foundations | p. 48 |
| Multiple events (Bayes' theorem) | p. 50 |
| Inclusion-exclusion principle | p. 51 |
| Discrete probability space | p. 54 |
| Algebra of random variables | p. 57 |
| Expectations | p. 58 |
| Discrete probability distribution (binomial, Poisson) | p. 60 |
| Continuous probability distribution (normal) | p. 64 |
| Continuous probability space ([ohm] is R) | p. 66 |
| The Bare Truth about Inferential Statistics | p. 69 |
| Probability distribution invariants | p. 70 |
| Samples & summary statistics | p. 72 |
| The central limit theorem | p. 77 |
| Statistical significance (p-value) | p. 80 |
| Summary | p. 82 |
| Exercises | p. 82 |
| What Are Patterns? | p. 89 |
| Introduction | p. 89 |
| Common Thread | p. 90 |
| Pattern Duality | p. 90 |
| Operators on p | p. 92 |
| Irredundant Patterns | p. 92 |
| Special case: maximality | p. 93 |
| Transitivity of redundancy | p. 95 |
| Uniqueness property | p. 95 |
| Case studies | p. 96 |
| Constrained Patterns | p. 99 |
| When is a Pattern Specification Nontrivial? | p. 99 |
| Classes of Patterns | p. 100 |
| Exercises | p. 103 |
| Patterns on Linear Strings | p. 111 |
| Modeling the Stream of Life | p. 113 |
| Introduction | p. 113 |
| Modeling a Biopolymer | p. 113 |
| Repeats in DNA | p. 114 |
| Directionality of biopolymers | p. 115 |
| Modeling a random permutation | p. 117 |
| Modeling a random string | p. 119 |
| Bernoulli Scheme | p. 120 |
| Markov Chain | p. 121 |
| Stationary distribution | p. 123 |
| Computing probabilities | p. 127 |
| Hidden Markov Model (HMM) | p. 128 |
| The decoding problem (Viterbi algorithm) | p. 130 |
| Comparison of the Schemes | p. 133 |
| Conclusion | p. 133 |
| Exercises | p. 134 |
| String Pattern Specifications | p. 139 |
| Introduction | p. 139 |
| Notation | p. 140 |
| Solid Patterns | p. 142 |
| Maximality | p. 144 |
| Counting the maximal patterns | p. 144 |
| Rigid Patterns | p. 149 |
| Maximal rigid patterns | p. 150 |
| Enumerating maximal rigid patterns | p. 152 |
| Density-constrained patterns | p. 156 |
| Quorum-constrained patterns | p. 157 |
| Large- [Sigma] input | p. 158 |
| Irredundant patterns | p. 160 |
| Extensible Patterns | p. 164 |
| Maximal extensible patterns | p. 165 |
| Generalizations | p. 165 |
| Homologous sets | p. 165 |
| Sequence on reals | p. 167 |
| Exercises | p. 170 |
| Algorithms & Pattern Statistics | p. 183 |
| Introduction | p. 183 |
| Discovery Algorithm | p. 183 |
| Pattern Statistics | p. 191 |
| Rigid Patterns | p. 191 |
| Extensible Patterns | p. 193 |
| Nondegenerate extensible patterns | p. 194 |
| Degenerate extensible patterns | p. 196 |
| Correction factor for the dot character | p. 197 |
| Measure of Surprise | p. 198 |
| z-score | p. 199 |
| x-square ratio | p. 199 |
| Interplay of combinatorics & statistics | p. 200 |
| Applications | p. 201 |
| Exercises | p. 203 |
| Motif Learning | p. 213 |
| Introduction: Local Multiple Alignment | p. 213 |
| Probabilistic Model: Motif Profile | p. 214 |
| The Learning Problem | p. 215 |
| Importance Measure | p. 216 |
| Statistical significance | p. 216 |
| Information content | p. 219 |
| Algorithms to Learn a Motif Profile | p. 220 |
| An Expectation Maximization Framework | p. 222 |
| The initial estimate [rho subscript o] | p. 222 |
| Estimating z given [rho] | p. 223 |
| Estimating [rho] given z | p. 224 |
| A Gibbs Sampling Strategy | p. 227 |
| Estimating [rho] given an alignment | p. 227 |
| Estimating background probabilities given Z | p. 228 |
| Estimating Z given [rho] | p. 228 |
| Interpreting the Motif Profile in Terms of p | p. 229 |
| Exercises | p. 230 |
| The Subtle Motif | p. 235 |
| Introduction: Consensus Motif | p. 235 |
| Combinatorial Model: Subtle Motif | p. 236 |
| Distance between Motifs | p. 238 |
| Statistics of Subtle Motifs | p. 240 |
| Performance Score | p. 245 |
| Enumeration Schemes | p. 246 |
| Neighbor enumeration (exact) | p. 246 |
| Submotif enumeration (inexact) | p. 249 |
| A Combinatorial Algorithm | p. 252 |
| A Probabilistic Algorithm | p. 255 |
| A Modular Solution | p. 257 |
| Conclusion | p. 259 |
| Exercises | p. 260 |
| Patterns on Meta-Data | p. 263 |
| Permutation Patterns | p. 265 |
| Introduction | p. 265 |
| Notation | p. 266 |
| How Many Permutation Patterns? | p. 267 |
| Maximality | p. 268 |
| P[subscript = 1]: Linear notation & PQ trees | p. 269 |
| P[subscript > i]: Linear notation? | p. 271 |
| Parikh Mapping-based Algorithm | p. 273 |
| Tagging technique | p. 275 |
| Time complexity analysis | p. 275 |
| Intervals | p. 278 |
| The naive algorithm | p. 280 |
| The Uno-Yagiura RC algorithm | p. 281 |
| Intervals to PQ Trees | p. 294 |
| Irreducible intervals | p. 295 |
| Encoding intervals as a PQ tree | p. 297 |
| Applications | p. 307 |
| Case study I: Human and rat | p. 308 |
| Case study II: E. Coli K-12 and B. Subtilis | p. 309 |
| Conclusion | p. 311 |
| Exercises | p. 312 |
| Permutation Pattern Probabilities | p. 323 |
| Introduction | p. 323 |
| Unstructured Permutations | p. 323 |
| Multinomial coefficients | p. 325 |
| Patterns with multiplicities | p. 328 |
| Structured Permutations | p. 329 |
| P-arrangement | p. 330 |
| An incremental method | p. 331 |
| An upper bound on P-arrangements | p. 336 |
| A lower bound on P-arrangements | p. 341 |
| Estimating the number of frontiers | p. 342 |
| Combinatorics to probabilities | p. 345 |
| Exercises | p. 346 |
| Topological Motifs | p. 355 |
| Introduction | p. 355 |
| Graph notation | p. 355 |
| What Are Topological Motifs? | p. 356 |
| Combinatorics in topologies | p. 357 |
| Input with self-isomorphisms | p. 358 |
| The Topological Motif | p. 359 |
| Maximality | p. 367 |
| Compact Topological Motifs | p. 369 |
| Occurrence-isomorphisms | p. 369 |
| Vertex indistinguishability | p. 372 |
| Compact list | p. 373 |
| Compact vertex, edge & motif | p. 373 |
| Maximal compact lists | p. 374 |
| Conjugates of compact lists | p. 374 |
| Characteristics of compact lists | p. 378 |
| Maximal operations on compact lists | p. 380 |
| Maximal subsets of location lists | p. 381 |
| Binary relations on compact lists | p. 384 |
| Compact motifs from compact lists | p. 384 |
| The Discovery Method | p. 392 |
| The algorithm | p. 393 |
| Related Classical Problems | p. 399 |
| Applications | p. 400 |
| Conclusion | p. 402 |
| Exercises | p. 402 |
| Set-Theoretic Algorithmic Tools | p. 417 |
| Introduction | p. 417 |
| Some Basic Properties of Finite Sets | p. 418 |
| Partial Order Graph G(S, E) of Sets | p. 419 |
| Reduced partial order graph | p. 420 |
| Straddle graph | p. 421 |
| Boolean Closure of Sets | p. 423 |
| Intersection closure | p. 423 |
| Union closure | p. 424 |
| Consecutive (Linear) Arrangement of Set Members | p. 426 |
| PQ trees | p. 426 |
| Straddling sets | p. 429 |
| Maximal Set Intersection Problem (maxSIP) | p. 434 |
| Ordered enumeration trie | p. 435 |
| Depth first traversal of the trie | p. 436 |
| Minimal Set Intersection Problem (minSIP) | p. 447 |
| Algorithm | p. 447 |
| Minimal from maximal sets | p. 448 |
| Multi-Sets | p. 450 |
| Ordered enumeration trie of multi-sets | p. 451 |
| Enumeration algorithm | p. 453 |
| Adapting the Enumeration Scheme | p. 455 |
| Exercises | p. 458 |
| Expression & Partial Order Motifs | p. 469 |
| Introduction | p. 469 |
| Motivation | p. 470 |
| Extracting (Monotone CNF) Boolean Expressions | p. 471 |
| Extracting biclusters | p. 475 |
| Extracting patterns in microarrays | p. 478 |
| Extracting Partial Orders | p. 480 |
| Partial orders | p. 480 |
| Partial order construction problem | p. 481 |
| Excess in partial orders | p. 483 |
| Statistics of Partial Orders | p. 485 |
| Computing Cex(B) | p. 489 |
| Redescriptions | p. 493 |
| Application: Partial Order of Expressions | p. 494 |
| Summary | p. 495 |
| Exercises | p. 496 |
| References | p. 503 |
| Index | p. 515 |
| Table of Contents provided by Ingram. All Rights Reserved. |
