Parida Pattern Discovery in Bioinformatics

Theory & Algorithms
1. Auflage 2007
ISBN: 978-1-4200-1073-2
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 512 Seiten

Reihe: Chapman & Hall/CRC Mathematical and Computational Biology

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.

Zielgruppe

Students, researchers, and practitioners in bioinformatics and computational biology; computer scientists in algorithms and pattern discovery; and biologists interested in informatics.

Autoren/Hrsg.

Parida, Laxmi

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Künstliche Intelligenz Mustererkennung, Biometrik
• Naturwissenschaften Biowissenschaften Biowissenschaften

Inhaltsverzeichnis

INTRODUCTION

Ubiquity of Patterns

Motivations Form Biology

The Need for Rigor
Who Is a Reader of This Book?

THE FUNDAMENTALS
BASIC ALGORITHMICS

Introduction

Graphs
Tree Problem 1: (Minimum Spanning Tree)

Tree Problem 2: (Steiner Tree)

Tree Problem 3: (Minimum Mutation Labeling)

Storing and Retrieving Elements

Asymptotic Functions

Recurrence Equations
NP-Complete Class of Problems

BASIC STATISTICS

Introduction

Basic Probability
The Bare Truth about Inferential Statistics
Summary

WHAT ARE PATTERNS?
Introduction
Common Thread

Pattern Duality

Irredundant Patterns

Constrained Patterns

When Is a Pattern Specification Non-Trivial?
Classes of Patterns

PATTERNS ON LINEAR STRINGS
MODELING THE STREAM OF LIFE

Introduction

Modeling a Biopolymer
Bernoulli Scheme

Markov Chain

Hidden Markov Model (HMM)

Comparison of the Schemes
Conclusion

STRING PATTERN SPECIFICATIONS
Introduction

Notation

Solid Patterns
Rigid Patterns
Extensible Patterns

Generalizations

ALGORITHMS AND PATTERN STATISTICS

Introduction

Discovery Algorithm

Pattern Statistics

Rigid Patterns
Extensible Patterns

Measure of Surprise

Applications

MOTIF LEARNING

Introduction: Local Multiple Alignment

Probabilistic Model: Motif Profile

The Learning Problem

Importance Measure
Algorithms to Learn a Motif Profile

An Expectation Maximization Framework

A Gibbs Sampling Strategy
Interpreting the Motif Profile in Terms of p

THE SUBTLE MOTIF

Introduction: Consensus Motif

Combinatorial Model: Subtle Motif

Distance between Motifs

Statistics of Subtle Motifs

Performance Score

Enumeration Schemes
A Combinatorial Algorithm

A Probabilistic Algorithm
A Modular Solution

Conclusion

PATTERNS ON META-DATA
PERMUTATION PATTERNS

Introduction
Notation
How Many Permutation Patterns?

Maximality
Parikh Mapping-Based Algorithm

Intervals
Intervals to PQ Trees

Applications

Conclusion

PERMUTATION PATTERN PROBABILITIES
Introduction

Unstructured Permutations

Structured Permutations

TOPOLOGICAL MOTIFS
Introduction

What Are Topological Motifs?

The Topological Motif

Compact Topological Motifs
The Discovery Method

Related Classical Problems

Applications

Conclusion

SET-THEORETIC ALGORITHMIC TOOLS
Introduction

Some Basic Properties of Finite Sets

Partial Order Graph G(S,E) of Sets

Boolean Closure of Sets

Consecutive (Linear) Arrangement of Set Members
Maximal 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 Orders
Redescriptions
Application: Partial Order of Expressions
Summary

REFERENCES

INDEX

Exercises appear at the end of every chapter.