Pattern Discovery in Bioinform

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.

INTRODUCTION Ubiquity of Patterns Motivations Form Biology The Need for RigorWho Is a Reader of This Book? THE FUNDAMENTALSBASIC ALGORITHMICS Introduction GraphsTree Problem 1: (Minimum Spanning Tree) Tree Problem 2: (Steiner Tree) Tree Problem 3: (Minimum Mutation Labeling) Storing and Retrieving Elements Asymptotic Functions Recurrence EquationsNP-Complete Class of ProblemsBASIC STATISTICS Introduction Basic ProbabilityThe Bare Truth about Inferential StatisticsSummaryWHAT ARE PATTERNS?IntroductionCommon Thread Pattern Duality Irredundant Patterns Constrained Patterns When Is a Pattern Specification Non-Trivial?Classes of PatternsPATTERNS ON LINEAR STRINGSMODELING THE STREAM OF LIFE Introduction Modeling a BiopolymerBernoulli Scheme Markov Chain Hidden Markov Model (HMM) Comparison of the SchemesConclusionSTRING PATTERN SPECIFICATIONSIntroduction Notation Solid PatternsRigid PatternsExtensible Patterns GeneralizationsALGORITHMS AND PATTERN STATISTICS Introduction Discovery Algorithm Pattern Statistics Rigid PatternsExtensible Patterns Measure of Surprise ApplicationsMOTIF LEARNING Introduction: Local Multiple Alignment Probabilistic Model: Motif Profile The Learning Problem Importance MeasureAlgorithms to Learn a Motif Profile An Expectation Maximization Framework A Gibbs Sampling StrategyInterpreting the Motif Profile in Terms of pTHE SUBTLE MOTIF Introduction: Consensus Motif Combinatorial Model: Subtle Motif Distance between Motifs Statistics of Subtle Motifs Performance Score Enumeration SchemesA Combinatorial Algorithm A Probabilistic AlgorithmA Modular Solution ConclusionPATTERNS ON META-DATAPERMUTATION PATTERNS IntroductionNotationHow Many Permutation Patterns? MaximalityParikh Mapping-Based Algorithm IntervalsIntervals to PQ Trees Applications ConclusionPERMUTATION PATTERN PROBABILITIESIntroduction Unstructured Permutations Structured PermutationsTOPOLOGICAL MOTIFSIntroduction What Are Topological Motifs? The Topological Motif Compact Topological MotifsThe Discovery Method Related Classical Problems Applications Conclusion SET-THEORETIC ALGORITHMIC TOOLSIntroduction Some Basic Properties of Finite Sets Partial Order Graph G(S,E) of Sets Boolean Closure of Sets Consecutive (Linear) Arrangement of Set MembersMaximal Set Intersection Problem (maxSIP)Minimal Set Intersection Problem (minSIP) Multi-Sets Adapting the Enumeration Scheme EXPRESSION AND PARTIAL ORDER MOTIFS Introduction Extracting (monotone CNF) Boolean Expressions Extracting Partial Orders Statistics of Partial OrdersRedescriptionsApplication: Partial Order of ExpressionsSummaryREFERENCESINDEXExercises appear at the end of every chapter.