
An Introduction to Bioinformatics Algorithms
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Persons
Pavel Pevzner is Ronald R. Taylor Professor of Computer Science at the University of California, San Diego. He is the author of Computational Molecular Biology: An Algorithmic Approach (MIT Press, 2000).
Content
- Intro
- Copyright
- Contents
- Preface
- 1 Introduction
- 2 Algorithms and Complexity
- 2.1 What Is an Algorithm?
- 2.2 Biological Algorithms versus Computer Algorithms
- 2.3 The Change Problem
- 2.4 Correct versus Incorrect Algorithms
- 2.5 Recursive Algorithms
- 2.6 Iterative versus Recursive Algorithms
- 2.7 Fast versus Slow Algorithms
- 2.8 Big-O Notation
- 2.9 Algorithm Design Techniques
- 2.9.1 Exhaustive Search
- 2.9.2 Branch-and-Bound Algorithms
- 2.9.3 Greedy Algorithms
- 2.9.4 Dynamic Programming
- 2.9.5 Divide-and-Conquer Algorithms
- 2.9.6 Machine Learning
- 2.9.7 Randomized Algorithms
- 2.10 Tractable versus Intractable Problems
- 2.11 Notes
- Biobox: Richard Karp
- 2.12 Problems
- 3 Molecular Biology Primer
- 3.1 What Is Life Made Of?
- 3.2 What Is the Genetic Material?
- 3.3 What Do Genes Do?
- 3.4 What Molecule Codes for Genes?
- 3.5 What Is the Structure of DNA?
- 3.6 What Carries Information between DNA and Proteins?
- 3.7 How Are Proteins Made?
- 3.8 How Can We Analyze DNA?
- 3.8.1 Copying DNA
- 3.8.2 Cutting and Pasting DNA
- 3.8.3 Measuring DNA Length
- 3.8.4 Probing DNA
- 3.9 How Do Individuals of a Species Differ?
- 3.10 How Do Different Species Differ?
- 3.11 Why Bioinformatics?
- Biobox: Russell Doolittle
- 4 Exhaustive Search
- 4.1 Restriction Mapping
- 4.2 Impractical Restriction Mapping Algorithms
- 4.3 A Practical Restriction Mapping Algorithm
- 4.4 Regulatory Motifs in DNA Sequences
- 4.5 Profiles
- 4.6 The Motif Finding Problem
- 4.7 Search Trees
- 4.8 Finding Motifs
- 4.9 Finding a Median String
- 4.10 Notes
- Biobox: Gary Stormo
- 4.11 Problems
- 5 Greedy Algorithms
- 5.1 Genome Rearrangements
- 5.2 Sorting by Reversals
- 5.3 Approximation Algorithms
- 5.4 Breakpoints: A Different Face of Greed
- 5.5 A Greedy Approach to Motif Finding
- 5.6 Notes
- Biobox: David Sankoff
- 5.7 Problems
- 6 Dynamic Programming Algorithms
- 6.1 The Power of DNA Sequence Comparison
- 6.2 The Change Problem Revisited
- 6.3 The Manhattan Tourist Problem
- 6.4 Edit Distance and Alignments
- 6.5 Longest Common Subsequences
- 6.6 Global Sequence Alignment
- 6.7 Scoring Alignments
- 6.8 Local Sequence Alignment
- 6.9 Alignment with Gap Penalties
- 6.10 Multiple Alignment
- 6.11 Gene Prediction
- 6.12 Statistical Approaches to Gene Prediction
- 6.13 Similarity-Based Approaches to Gene Prediction
- 6.14 Spliced Alignment
- 6.15 Notes
- Biobox: Michael Waterman
- 6.16 Problems
- 7 Divide-and-Conquer Algorithms
- 7.1 Divide-and-Conquer Approach to Sorting
- 7.2 Space-Efficient Sequence Alignment
- 7.3 Block Alignment and the Four-Russians Speedup
- 7.4 Constructing Alignments in Subquadratic Time
- 7.5 Notes
- Biobox: Webb Miller
- 7.6 Problems
- 8 Graph Algorithms
- 8.1 Graphs
- 8.2 Graphs and Genetics
- 8.3 DNA Sequencing
- 8.4 Shortest Superstring Problem
- 8.5 DNA Arrays as an Alternative Sequencing Technique
- 8.6 Sequencing by Hybridization
- 8.7 SBH as a Hamiltonian Path Problem
- 8.8 SBH as an Eulerian Path Problem
- 8.9 Fragment Assembly in DNA Sequencing
- 8.10 Protein Sequencing and Identification
- 8.11 The Peptide Sequencing Problem
- 8.12 Spectrum Graphs
- 8.13 Protein Identification via Database Search
- 8.14 Spectral Convolution
- 8.15 Spectral Alignment
- 8.16 Notes
- 8.17 Problems
- 9 Combinatorial Pattern Matching
- 9.1 Repeat Finding
- 9.2 Hash Tables
- 9.3 Exact Pattern Matching
- 9.4 Keyword Trees
- 9.5 Suffix Trees
- 9.6 Heuristic Similarity Search Algorithms
- 9.7 Approximate Pattern Matching
- 9.8 BLAST: Comparing a Sequence against a Database
- 9.9 Notes
- Biobox: Gene Myers
- 9.10 Problems
- 10 Clustering and Trees
- 10.1 Gene Expression Analysis
- 10.2 Hierarchical Clustering
- 10.3 k-Means Clustering
- 10.4 Clustering and Corrupted Cliques
- 10.5 Evolutionary Trees
- 10.6 Distance-Based Tree Reconstruction
- 10.7 Reconstructing Trees from Additive Matrices
- 10.8 Evolutionary Trees and Hierarchical Clustering
- 10.9 Character-Based Tree Reconstruction
- 10.10 Small Parsimony Problem
- 10.11 Large Parsimony Problem
- 10.12 Notes
- Biobox: Ron Shamir
- 10.13 Problems
- 11 Hidden Markov Models
- 11.1 CG-Islands and the "Fair Bet Casino"
- 11.2 The Fair Bet Casino and Hidden Markov Models
- 11.3 Decoding Algorithm
- 11.4 HMM Parameter Estimation
- 11.5 Profile HMM Alignment
- 11.6 Notes
- Biobox: David Haussler
- 11.7 Problems
- 12 Randomized Algorithms
- 12.1 The Sorting Problem Revisited
- 12.2 Gibbs Sampling
- 12.3 Random Projections
- 12.4 Notes
- 12.5 Problems
- Using Bioinformatics Tools
- Bibliography
- Index
System requirements
File format: ePUB
Copy protection: Adobe-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Install the free reader Adobe Digital Editions prior to download (see eBook Help).
- Tablet/smartphone (Android; iOS): Install the free app Adobe Digital Editions or the app PocketBook before downloading (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (not Kindle).
The file format ePub works well for novels and non-fiction books – i.e., „flowing” text without complex layout. On an e-reader or smartphone, line and page breaks automatically adjust to fit the small displays.
This eBook uses Adobe-DRM, a „hard” copy protection. If the necessary requirements are not met, unfortunately you will not be able to open the eBook. You will therefore need to prepare your reading hardware before downloading.
Please note: We strongly recommend that you authorise using your personal Adobe ID after installation of any reading software.
For more information, see our ebook Help page.