Bioinformatics Algorithms: An Active Learning Approach

Citation

Compeau, P., & Pevzner, P. (2018). Bioinformatics Algorithms: An Active Learning Approach (3rd ed.). Active Learning Publishers.

Chapter Summary

The book's website lists eleven chapters. Each is titled by a biological question and paired with a class of algorithms. The authors describe the method: each chapter begins with a central biological question and steadily develops the algorithmic sophistication needed to answer it. Hundreds of exercises are built into the text as soon as they are needed, with automatically graded coding challenges on the free Rosalind platform. The website offers Chapters 1–5 to read free of charge and lecture videos for every chapter. An interactive version of the text is sold separately.

Chapter 1: Where in the Genome Does DNA Replication Begin?

Described on the lecture page as an "algorithmic warm-up", this chapter searches for the replication origin of bacterial genomes. Its lessons move from hidden messages (frequent words) in the origin region, through the asymmetry of replication and the skew between the forward and reverse half-strands, to approximate pattern matching and a final attempt to find DnaA boxes in E. coli. An epilogue discusses complications in origin prediction.

Chapter 2: Which DNA Patterns Play the Role of Molecular Clocks?

This chapter introduces randomised algorithms through motif finding, the search for short regulatory patterns shared by the regulatory regions of genes. It starts from the question of whether there is a "clock" gene. It then explains why motif finding is harder than it looks, how motifs are scored, and the link to finding a median string. It continues with greedy motif search, randomised motif search and Gibbs sampling. The epilogue asks how tuberculosis bacteria hibernate.

Chapter 3: How Do We Assemble Genomes?

Genome assembly is the setting for graph algorithms. The chapter starts with the "exploding newspapers" analogy for sequencing and the string reconstruction problem. It compares overlap graphs with de Bruijn graphs. It then goes back to the Seven Bridges of Königsberg and Euler's theorem to build an algorithm for Eulerian cycles, before turning to read-pairs and, in the epilogue, the problems of real sequencing data.

Chapter 4: How Do We Sequence Antibiotics?

Brute force and branch-and-bound algorithms are introduced through the sequencing of antibiotic peptides by mass spectrometry. The lessons cover the discovery of antibiotics, how bacteria make them outside the central dogma (non-ribosomal peptides), cyclopeptide sequencing by brute force and by branch-and-bound, the case of more than twenty amino acids, and the spectral convolution, ending with real rather than simulated spectra.

Chapter 5: How Do We Compare Biological Sequences?

This chapter is the book's introduction to dynamic programming. It begins with the non-ribosomal code, introduces sequence alignment through the Manhattan Tourist problem and the change problem, and generalises to longest paths in a directed acyclic graph and backtracking. It then covers scoring, local alignment, other alignment variants, gap penalties, space-efficient alignment and multiple alignment.

Chapters 6–8: Are There Fragile Regions in the Human Genome?; Which Animal Gave Us SARS?; How Did Yeast Become a Wine Maker?

These chapters pair biological questions with combinatorial algorithms, evolutionary tree reconstruction and clustering. Chapter 6 treats genome rearrangements ("transforming men into mice"), sorting by reversals, the breakpoint theorem and rearrangements in tumour genomes. Chapter 7 builds evolutionary trees from distance matrices, including additive phylogeny, UPGMA, neighbour joining and small parsimony. Chapter 8 uses gene expression data from yeast to introduce clustering as an optimisation problem, the Lloyd algorithm for k-means, soft k-means and hierarchical clustering.

Chapters 9–11: How Do We Locate Disease-Causing Mutations?; Why Have Biologists Still Not Developed an HIV Vaccine?; Was T. rex Just a Big Chicken?

The final chapters cover combinatorial pattern matching, hidden Markov models and computational proteomics. Chapter 9 explains read mapping with tries, suffix trees, suffix arrays and the Burrows–Wheeler transform. Chapter 10 introduces hidden Markov models through a "crooked casino" and HIV classification, covering the decoding problem (Viterbi), profile HMMs and parameter estimation, including Baum–Welch learning. Chapter 11 turns to peptide sequencing from mass spectra and the search of proteomes against spectra, with paleontology as its motivating question.

Key Concepts

Chapters 1–3: Replication origins, motifs and assembly

• Frequent words and skew: finding over-represented patterns, and using the imbalance of nucleotides between strands to locate the replication origin.
• Randomised algorithms: randomised motif search and Gibbs sampling, which find good solutions where exhaustive search is impractical.
• de Bruijn graphs and Eulerian paths: representing reads as edges of a graph so that genome assembly becomes a path problem.

Chapters 4–5: Antibiotics and sequence comparison

• Branch-and-bound: pruning a brute-force search, applied to cyclopeptide sequencing.
• Spectral convolution: deducing likely amino acid masses from a mass spectrum.
• Dynamic programming: solving alignment as a longest path in a grid-like directed acyclic graph.
• Local, affine-gap and multiple alignment: variants of alignment for different biological questions.

Chapters 6–8: Rearrangements, phylogeny and clustering

• Breakpoints and reversals: measuring and computing the rearrangement distance between genomes.
• Distance-based phylogeny: additive phylogeny, UPGMA and neighbour joining.
• k-means clustering: grouping genes by expression profile through an optimisation problem.

Chapters 9–11: Pattern matching, HMMs and proteomics

• Suffix trees, suffix arrays and the Burrows–Wheeler transform: data structures for fast read mapping.
• Hidden Markov models: probabilistic models decoded with the Viterbi algorithm and trained by Baum–Welch learning.
• Peptide identification: matching mass spectra against peptides and proteomes.

Critical Analysis

Strengths

• Biology first, algorithms as needed. Each chapter starts from a concrete biological question and develops algorithms only as the question demands. The lesson titles show this: in Chapter 3, for example, the reader works through string reconstruction and two kinds of graph before reaching Euler's theorem.
• A broad survey of algorithm design. The chapter pairing covers warm-up string algorithms, randomised, graph, brute-force and branch-and-bound, dynamic programming, combinatorial, phylogenetic, clustering, string-indexing and probabilistic methods. Students meet the main families of algorithms used in computational biology.
• Practice built in. Exercises are integrated into the text, and the code challenges are on the free Rosalind "Bioinformatics Textbook Track", which lists 124 problems across the eleven chapters, from counting patterns in a string to Baum–Welch learning.
• Free supporting material. Five chapters can be read on the book's website, and lecture videos accompany every chapter. Readers can try the approach before buying, and instructors can use the material for flipped teaching, as the authors describe.

Limitations

• Requires programming. The book is built around implementing algorithms. Students who cannot yet program in any language will struggle with the code challenges that carry much of the learning.
• Little on databases and tools. The chapters cover algorithms rather than the databases, software packages and annotation workflows that practising bioinformaticians use daily. A course on using bioinformatics resources needs another text.
• Long, discursive chapters. The story-driven approach, with many lessons per chapter, takes time. Readers looking for a quick reference to an algorithm may find it slower than a conventional textbook.

Where It Fits in the Course

Among the bioinformatics books on this list, Compeau and Pevzner is the algorithm-centred, programming-based introduction. Arthur Lesk's Introduction to Bioinformatics presents the field as questions about genomes, proteins and evolution answered with data and computation. It emphasises interpreting results rather than writing software, and so makes a good complement: Lesk explains what the methods are used for, while Compeau and Pevzner show how they work inside. Baxevanis, Bader and Wishart's Bioinformatics is an edited textbook on the databases, algorithms and analysis methods in practical use, covering the tools side that this book leaves out. Zvelebil and Baum's Understanding Bioinformatics is a broader interdisciplinary treatment, including protein structure and systems topics.

Uri Alon's An Introduction to Systems Biology moves from sequence analysis to quantitative models of biological circuits and their design principles. It is a different subject, best taken after an algorithms course such as this one.

How to Use This Book

The book suits biology students who can program, and computer science students who want an introduction to biological problems. Basic programming in any language and school mathematics are needed. Probability helps for Chapters 2 and 10.

• Start free: read Chapters 1–5 on the website to judge the style. Chapters 1 (string algorithms), 3 (graphs) and 5 (dynamic programming) are the core of most courses.
• Core path: Chapters 1, 3, 5, 7 and 9 give the essential toolkit of pattern finding, assembly, alignment, phylogeny and read mapping.
• By interest: Chapters 2 and 10 for probabilistic methods, Chapters 4 and 11 for mass spectrometry and proteomics, Chapter 6 for genome rearrangements and Chapter 8 for expression data and clustering.
• Work the problems: solve the Rosalind Textbook Track problems for each chapter as you read rather than afterwards, and watch the lecture videos when a lesson is unclear.

Students who want certificates or auto-graded exercises inside the text can use the paid interactive version or the associated online courses. The print book and Rosalind together are enough for self-study.