Skip to content

Algorithms in Bioinformatics A Practical Introduction

Spend $50 to get a free DVD!

ISBN-10: 1420070339

ISBN-13: 9781420070330

Edition: 2009

Authors: Wing-Kin Sung

List price: $95.95
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
Rent eBooks
Buy eBooks
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

This text focuses on using algorithms and discrete mathematics to solve biological problems. It systematically describes biological applications, the corresponding mathematical/computational problems, and various algorithmic solutions. The author also discusses the practical use of many algorithmic methods and describes what algorithms should be used in different situations. Each chapter contains an overview of the biological problem, a precise definition of the computational problem, a description of various methods, practical issues and further research, references to further reading, and a set of knowledge-testing exercises. Instruction and data for practical exercises are provided on the authors website.
Customers also bought

Book details

List price: $95.95
Copyright year: 2009
Publisher: CRC Press LLC
Publication date: 11/24/2009
Binding: Hardcover
Pages: 407
Size: 6.25" wide x 9.25" long x 1.00" tall
Weight: 1.826
Language: English

Preface
Introduction to Molecular Biology
DNA, RNA, and Protein
Proteins
DNA
RNA
Genome, Chromosome, and Gene
Genome
Chromosome
Gene
Complexity of the Organism versus Genome Size
Number of Genes versus Genome Size
Replication and Mutation of DNA
Central Dogma (from DNA to Protein)
Transcription (Prokaryotes)
Transcription (Eukaryote)
Translation
Post-Translation Modification (PTM)
Population Genetics
Basic Biotechnological Tools
Restriction Enzymes
Sonication
Cloning
PCR
Gel Electrophoresis
Hybridization
Next Generation DNA Sequencing
Brief History of Bioinformatics
Exercises
Sequence Similarity
Introduction
Global Alignment Problem
Needleman-Wunsch Algorithm
Running Time Issue
Space Efficiency Issue
More on Global Alignment
Local Alignment
Semi-Global Alignment
Gap Penalty
General Gap Penalty Model
Affine Gap Penalty Model
Convex Gap Model
Scoring Function
Scoring Function for DNA
Scoring Function for Protein
Exercises
Suffix Tree
Introduction
Suffix Tree
Simple Applications of a Suffix Tree
Exact String Matching Problem
Longest Repeated Substring Problem
Longest Common Substring Problem
Longest Common Prefix (LCP)
Finding a Palindrome
Extracting the Embedded Suffix Tree of a String from the Generalized Suffix Tree
Common Substring of 2 or More Strings
Construction of a Suffix Tree
Step 1: Construct the Odd Suffix Tree
Step 2: Construct the Even Suffix Tree
Step 3: Merge the Odd and the Even Suffix Trees
Suffix Array
Construction of a Suffix Array
Exact String Matching Using a Suffix Array
FM-Index
Definition
The occ Data Structure
Exact String Matching Using the FM-Index
Approximate Searching Problem
Exercises
Genome Alignment
Introduction
Maximum Unique Match (MUM)
How to Find MUMs
MUMmer1: LCS
Dynamic Programming Algorithm in 0(n<sup>2</sup>) Time
An O (n log n)-Time Algorithm
MUMmer2 and MUMmer3
Reducing Memory Usage
Employing a New Alternative Algorithm for Finding MUMs
Clustering Matches
Extension of the Definition of MUM
Mutation Sensitive Alignment
Concepts and Definitions
The Idea of the Heuristic Algorithm
Experimental Results
Dot Plot for Visualizing the Alignment
Further Reading
Exercises
Database Search
Introduction
Biological Database
Database Searching
Types of Algorithms
Smith-Waterman Algorithm
FastA
FastP Algorithm
FastA Algorithm
Blast
Blast1
Blast2
Blast1 versus Blast2
Blast versus FastA
Statistics for Local Alignment
Variations of the Blast Algorithm
MegaBlast
Blat
PatternHunter
PSI-Blast (Position-Specific Iterated Blast)
Q-gram Alignment based on Suffix A Rrays (QUASAR)
Algorithm
Speeding Up and Reducing the Space for QUASAR
Time Analysis
Locality-Sensitive Hashing
BWT-SW
Aligning Query Sequence to Suffix Tree
Meaningful Alignment
Are Existing Database Searching Methods Sensitive Enough?
Exercises
Multiple Sequence Alignment
Introduction
Formal Definition of the Multiple Sequence Alignment Problem
Methods for Solving the MSA Problem
Dynamic Programming Method
Center Star Method
Progressive Alignment Method
ClustalW
Profile-Profile Alignment
Limitation of Progressive Alignment Construction
Iterative Method
Muscle
Log-Expectation (LE) Score
Further Reading
Exercises
Phylogeny Reconstruction
Introduction
Mitochondrial DNA and Inheritance
The Constant Molecular Clock
Phylogeny
Applications of Phylogeny
Phylogenetic Tree Reconstruction
Character-Based Phylogeny Reconstruction Algorithm
Maximum Parsimony
Compatibility
Maximum Likelihood Problem
Distance-Based Phylogeny Reconstruction Algorithm
Additive Metric and Ultrametric
Unweighted Pan Group Method with Arithmetic Mean (UPGMA)
Additive Tree Reconstruction
Nearly Additive Tree Reconstruction
Can We Apply Distance-Based Methods Given a Character-State Matrix?
Bootstrapping
Can Tree Reconstruction Methods Infer the Correct Tree?
Exercises
Phylogeny Comparison
Introduction
Similarity Measurement
Computing MAST by Dynamic Programming
MAST for Unrooted Trees
Dissimilarity Measurements
Robinson-Foulds Distance
Nearest Neighbor Interchange Distance (NNI)
Subtree Transfer Distance (STT)
Quartet Distance
Consensus Tree Problem
Strict Consensus Tree
Majority Rule Consensus Tree
Median Consensus Tree
Greedy Consensus Tree
R* Tree
Further Reading
Exercises
Genome Rearrangement
Introduction
Types of Genome Rearrangements
Computational Problems
Sorting an Unsigned Permutation by Reversals
Upper and Lower Bound on an Unsigned Reversal Distance
4-Approximation Algorithm for Sorting an Unsigned Permutation
2-Approximation Algorithm for Sorting an Unsigned Permutation
Sorting a Signed Permutation by Reversals
Upper Bound on Signed Reversal Distance
Elementary Intervals, Cycles, and Components
The Hannenhalli-Pevzner Theorem
Further Reading
Exercises
Motif Finding
Introduction
Identifying Binding Regions of TFs
Motif Model
The Motif Finding Problem
Scanning for Known Motifs
Statistical Approaches
Gibbs Motif Sampler
MEME
Combinatorial Approaches
Exhaustive Pattern-Driven Algorithm
Sample-Driven Approach
Suffix Tree-Based Algorithm
Graph-Based Method
Scoring Function
Motif Ensemble Methods
Approach of MotifVoter
Motif Filtering by the Discriminative and Consensus Criteria
Sites Extraction and Motif Generation
Can Motif Finders Discover the Correct Motifs?
Motif Finding Utilizing Additional Information
Regulatory Element Detection Using Correlation with Expression
Discovery of Regulatory Elements by Phylogenetic Footprinting
Exercises
RNA Secondary Structure Prediction
Introduction
Base Interactions in RNA
RNA Structures
Obtaining RNA Secondary Structure Experimentally
RNA Structure Prediction Based on Sequence Only
Structure Prediction with the Assumption That There is No Pseudoknot
Nussinov Folding Algorithm
ZUKER Algorithm
Time Analysis
Speeding up Multi-Loops
Speeding up Internal Loops
Structure Prediction with Pseudoknots
Definition of a Simple Pseudoknot
Akutsu's Algorithm for Predicting an RNA Secondary Structure with Simple Pseudoknots
Exercises
Peptide Sequencing
Introduction
Obtaining the Mass Spectrum of a Peptide
Modeling the Mass Spectrum of a Fragmented Peptide
Amino Acid Residue Mass
Fragment Ion Mass
De Novo Peptide Sequencing Using Dynamic Programming
Scoring by Considering y-Ions
Scoring by Considering y-Ions and b-Ions
De Novo Sequencing Using Graph-Based Approach
Peptide Sequencing via Database Search
Further Reading
Exercises
Population Genetics
Introduction
Locus, Genotype, Allele, and SNP
Genotype Frequency and Allele Frequency
Haplotype and Phenotype
Technologies for Studying the Human Population .
Bioinformatics Problems
Hardy-Weinberg Equilibrium
Linkage Disequilibrium
D and D'
r<sup>2</sup>
Genotype Phasing
Clark's Algorithm
Perfect Phylogeny Haplotyping Problem
Maximum Likelihood Approach
Phase Algorithm
Tag SNP Selection
Zhang et al's Algorithm
IdSelect
Association Study
Categorical Data Analysis
Relative Risk and Odds Ratio
Linear Regression
Logistic Regression
Exercises
References
Index