1st Edition

Algorithms in Bioinformatics
A Practical Introduction

ISBN 9781420070330
Published November 24, 2009 by Chapman and Hall/CRC
408 Pages - 16 Color & 225 B/W Illustrations

USD $105.00

Prices & shipping based on shipping country


Book Description

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)

Population Genetics

Basic Biotechnological Tools

Brief History of Bioinformatics

Sequence Similarity


Global Alignment Problem

Local Alignment

Semi-Global Alignment

Gap Penalty

Scoring Function

Suffix Tree


Suffix Tree

Simple Applications of Suffix Tree

Construction of Suffix Tree

Suffix Array


Approximate Searching Problem

Database Search


Smith–Waterman Algorithm



Variations of the BLAST Algorithm

Q-Gram Alignment Based on Suffix ARrays (QUASAR)

Locality-Sensitive Hashing


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

Iterative Method

Genome Alignment


Maximum Unique Match (MUM)

Mutation Sensitive Alignment

Dot Plot for Visualizing the Alignment

Phylogeny Reconstruction


Character-Based Phylogeny Reconstruction Algorithm

Distance-Based Phylogeny Reconstruction Algorithm


Can Tree Reconstruction Methods Infer the Correct Tree?

Phylogeny Comparison


Similarity Measurement

Dissimilarity Measurements

Consensus Tree Problem

Genome Rearrangement


Types of Genome Rearrangements

Computational Problems

Sorting Unsigned Permutation by Reversals

Sorting Signed Permutation by Reversals

Motif Finding


Identifying Binding Regions of TFs

Motif Model

The Motif Finding Problem

Scanning for Known Motifs

Statistical Approaches

Combinatorial Approaches

Scoring Function

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

ZUKER Algorithm

Structure Prediction with Pseudoknots

Peptide Sequencing


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

Population Genetics


Hardy–Weinberg Equilibrium

Linkage Disequilibrium

Genotype Phasing

Tag SNP Selection

Association Study



Exercises appear at the end of each chapter.

View More



Wing-Kin Sung is an associate professor at the National University of Singapore.

Featured Author Profiles

Author - Wing-Kin  Sung

Wing-Kin Sung

Professor, National University of Singapore / Genome Institute of Singapore

Learn more about Wing-Kin Sung »


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