Thoroughly Describes Biological Applications, Computational Problems, and Various Algorithmic Solutions
Developed from the author’s own teaching material, Algorithms in Bioinformatics: A Practical Introduction provides an in-depth introduction to the algorithmic techniques applied in bioinformatics. For each topic, the author clearly details the biological motivation and precisely defines the corresponding computational problems. He also includes detailed examples to illustrate each algorithm and end-of-chapter exercises for students to familiarize themselves with the topics. Supplementary material is available at http://www.comp.nus.edu.sg/~ksung/algo_in_bioinfo/
This classroom-tested textbook begins with basic molecular biology concepts. It then describes ways to measure sequence similarity, presents simple applications of the suffix tree, and discusses the problem of searching sequence databases. After introducing methods for aligning multiple biological sequences and genomes, the text explores applications of the phylogenetic tree, methods for comparing phylogenetic trees, the problem of genome rearrangement, and the problem of motif finding. It also covers methods for predicting the secondary structure of RNA and for reconstructing the peptide sequence using mass spectrometry. The final chapter examines the computational problem related to population genetics.
Table of Contents
Introduction to Molecular Biology
DNA, RNA, Protein
Genome, Chromosome, and Gene
Replication and Mutation of DNA
Central Dogma (From DNA to Protein)
Post-Translation Modification (PTM)
Basic Biotechnological Tools
Brief History of Bioinformatics
Global Alignment Problem
Simple Applications of Suffix Tree
Construction of Suffix Tree
Approximate Searching Problem
Variations of the BLAST Algorithm
Q-Gram Alignment Based on Suffix ARrays (QUASAR)
Are Existing Database Searching Methods Sensitive Enough?
Multiple Sequence Alignment
Formal Definition of Multiple Sequence Alignment Problem
Dynamic Programming Method
Center Star Method
Progressive Alignment Method
Maximum Unique Match (MUM)
Mutation Sensitive Alignment
Dot Plot for Visualizing the Alignment
Character-Based Phylogeny Reconstruction Algorithm
Distance-Based Phylogeny Reconstruction Algorithm
Can Tree Reconstruction Methods Infer the Correct Tree?
Consensus Tree Problem
Types of Genome Rearrangements
Sorting Unsigned Permutation by Reversals
Sorting Signed Permutation by Reversals
Identifying Binding Regions of TFs
The Motif Finding Problem
Scanning for Known Motifs
Motif Ensemble Methods
Can Motif Finders Discover the Correct Motifs?
Motif Finding Utilizing Additional Information
RNA Secondary Structure Prediction
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
Structure Prediction with Pseudoknots
Obtaining the Mass Spectrum of a Peptide
Modeling the Mass Spectrum of a Fragmented Peptide
De novo Peptide Sequencing Using Dynamic Programming
De novo Sequencing Using Graph-Based Approach
Peptide Sequencing via Database Search
Tag SNP Selection
Exercises appear at the end of each chapter.
Wing-Kin Sung is an associate professor at the National University of Singapore.
Featured Author Profiles
This aptly titled book is a timely publication that details several algorithms widely used in bioinformatics. … This work can serve as a reference guide for students and researchers attempting to implement or learn algorithms relevant to bioinformatics. Although some concepts referenced in the book specifically target advanced bioinformatics experts, general users should not be discouraged from reading this work. …Summing Up: Recommended.
—CHOICE, June 2010
… an excellent guide. The book is appropriate for advanced undergraduates and graduates in mathematics or CS. … The 27-page introduction is the most efficient concept-building summary and explication of molecular biology that I have encountered. … Section 1.8 sets a new, high standard for science-history exposition, covering Gregor Mendel to the present. …This self-contained, well-designed, and well-written book, with its many good exercises, bibliographic references, and photo-quality figures, is an ideal introduction to bioinformatics.
—George Hacken, Computing Reviews, March 2010