Pattern Discovery in Bioinformatics: Theory & Algorithms

by Parida; Laxmi

• ISBN13: 9781584885498
• ISBN10: 1584885491
• Edition: 1st
• Format: Hardcover
• Copyright: 2007-07-04
• Publisher: Chapman & Hall/

Summary

The computational methods of bioinformatics are being used more and more to process the large volume of current biological data. Promoting an understanding of the underlying biology that produces this data, Pattern Discovery in Bioinformatics: Theory and Algorithms provides the tools to study regularities in biological data.Taking a systematic approach to pattern discovery, the book supplies sound mathematical definitions and efficient algorithms to explain vital information about biological data. It explores various data patterns, including strings, clusters, permutations, topology, partial orders, and boolean expressions. Each of these classes captures a different form of regularity in the data, providing possible answers to a wide range of questions. The book also reviews basic statistics, including probability, information theory, and the central limit theorem.This self-contained book provides a solid foundation in computational methods, enabling the solution of difficult biological questions.

Table of Contents

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.