Bioinformatics Algorithms: An Active Learning Approach（生物信息学算法：主动学习方法）

引用

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

章节概要

本书网站列出了十一章，每章都以一个生物学问题为标题，并与一类算法相配。作者这样描述其方法：每章从一个核心生物学问题出发，逐步发展出回答该问题所需的算法技巧。数百道练习在需要时直接嵌入正文，读者还可以在免费的 Rosalind 平台上完成自动评分的编程挑战。网站免费提供第1–5章的阅读，并为每一章配有讲课视频；正文的交互式版本单独销售。

第1章：DNA复制从基因组的何处开始？

讲课页面称这一章为"算法热身"。它寻找细菌基因组的复制起点：各课从起点区域中"隐藏的信息"（高频词）讲起，经过复制的不对称性、前导与后随半链之间的偏斜（skew）和近似模式匹配，最后尝试在大肠杆菌中找到DnaA盒。尾声讨论起点预测中的复杂情况。

第2章：哪些DNA模式扮演分子钟的角色？

本章通过模体发现——寻找基因调控区共有的短调控模式——来介绍随机化算法。它从"是否存在'时钟'基因"这一问题出发，解释为什么模体发现比看起来更难、如何给模体打分，以及它与寻找中位字符串的联系；随后依次讲解贪心模体搜索、随机化模体搜索和吉布斯抽样。尾声探讨结核杆菌如何"冬眠"。

第3章：如何组装基因组？

基因组组装是讲授图算法的场景。本章从把测序比作"爆炸的报纸"以及字符串重建问题讲起，比较重叠图和德布鲁因图，然后回到柯尼斯堡七桥问题和欧拉定理，构建寻找欧拉回路的算法，最后讨论读段对（read-pairs），并在尾声中讨论真实测序数据带来的问题。

第4章：如何测定抗生素的序列？

本章通过质谱法测定抗生素肽的序列来介绍穷举算法和分支限界法。各课内容包括抗生素的发现、细菌如何绕过中心法则合成抗生素（非核糖体肽）、用穷举法和分支限界法测定环肽序列、氨基酸超过20种的情形，以及谱卷积，最后从模拟谱转向真实谱。

第5章：如何比较生物序列？

这一章是全书对动态规划的入门。它从非核糖体密码讲起，通过曼哈顿游客问题和找零问题引入序列比对，再推广到有向无环图中的最长路径和回溯；随后讨论打分、局部比对、其他比对变体、空位罚分、节省空间的比对以及多序列比对。

第6–8章：人类基因组中有脆弱区域吗？；哪种动物把SARS传给了我们？；酵母是如何成为酿酒师的？

这几章把生物学问题分别与组合算法、进化树重建和聚类相结合。第6章讨论基因组重排（"把人变成小鼠"）、反转排序、断点定理以及肿瘤基因组中的重排。第7章从距离矩阵构建进化树，包括加性系统发育、UPGMA、邻接法和小简约问题。第8章利用酵母的基因表达数据，介绍作为优化问题的聚类、k均值的劳埃德算法、软k均值和层次聚类。

第9–11章：如何定位致病突变？；为什么生物学家至今仍未研制出HIV疫苗？；霸王龙只是一只大鸡吗？

最后几章涉及组合模式匹配、隐马尔可夫模型和计算蛋白质组学。第9章讲解利用字典树、后缀树、后缀数组和Burrows–Wheeler变换进行读段比对。第10章通过"作弊赌场"和HIV分类引入隐马尔可夫模型，内容包括解码问题（维特比算法）、谱隐马尔可夫模型以及参数估计（包括Baum–Welch学习）。第11章以古生物学为引子，讨论从质谱测定肽序列以及用质谱检索蛋白质组。

核心概念

第1–3章：复制起点、模体与组装

• 高频词与偏斜：寻找过度出现的模式，并利用两条链之间核苷酸的不平衡来定位复制起点。
• 随机化算法：随机化模体搜索和吉布斯抽样，在穷举搜索不可行时找到好的解。
• 德布鲁因图与欧拉路径：把读段表示为图的边，使基因组组装变成路径问题。

第4–5章：抗生素与序列比较

• 分支限界法：对穷举搜索进行剪枝，应用于环肽测序。
• 谱卷积：从质谱推断可能的氨基酸质量。
• 动态规划：把比对问题当作网格状有向无环图中的最长路径来求解。
• 局部比对、仿射空位比对与多序列比对：针对不同生物学问题的比对变体。

第6–8章：重排、系统发育与聚类

• 断点与反转：度量和计算基因组之间的重排距离。
• 基于距离的系统发育：加性系统发育、UPGMA和邻接法。
• k均值聚类：通过优化问题，按表达谱把基因分组。

第9–11章：模式匹配、隐马尔可夫模型与蛋白质组学

• 后缀树、后缀数组与Burrows–Wheeler变换：用于快速读段比对的数据结构。
• 隐马尔可夫模型：用维特比算法解码、用Baum–Welch学习训练的概率模型。
• 肽段鉴定：把质谱与肽段和蛋白质组进行匹配。

评析

优点

• 生物学先行，算法按需引入。 每章都从一个具体的生物学问题出发，只在问题需要时才发展算法。各课标题体现了这一点：例如在第3章中，读者先学习字符串重建和两种图，然后才接触欧拉定理。
• 对算法设计的广泛概览。 各章所配的算法涵盖热身用的字符串算法、随机化算法、图算法、穷举与分支限界、动态规划、组合算法、系统发育方法、聚类、字符串索引和概率方法。学生会接触到计算生物学中使用的主要算法类别。
• 练习融入其中。 练习融入正文，编程挑战则放在免费的 Rosalind"Bioinformatics Textbook Track"上，那里列出了覆盖十一章的124道题，从统计字符串中的模式到Baum–Welch学习。
• 免费的辅助材料。 五章可在本书网站上阅读，每章都配有讲课视频。读者可以在购买前试用这种方法，教师也可以像作者所描述的那样，用这些材料进行翻转课堂教学。

局限

• 需要编程能力。 本书围绕算法实现展开。还不会用任何语言编程的学生，在承担大部分学习任务的编程挑战上会很吃力。
• 很少涉及数据库和工具。 各章讲的是算法，而不是生物信息学从业者日常使用的数据库、软件包和注释流程。讲授如何使用生物信息学资源的课程需要另选教材。
• 章节冗长，叙述迂回。 以故事为主线、每章包含许多课的方式比较费时。想快速查阅某个算法的读者可能会觉得它比传统教科书慢。

在课程中的定位

在本书单的生物信息学书目中，Compeau 与 Pevzner 是以算法为中心、以编程为基础的入门书。Arthur Lesk 的 Introduction to Bioinformatics 把这一领域呈现为可以用数据和计算来回答的关于基因组、蛋白质和进化的问题，强调结果的解读而非软件编写，因此是很好的补充：Lesk 说明方法用来做什么，Compeau 与 Pevzner 则展示方法内部如何运作。Baxevanis、Bader 与 Wishart 的 Bioinformatics 是一部编著教科书，介绍实际使用的数据库、算法和分析方法，涵盖了本书没有涉及的工具方面。Zvelebil 与 Baum 的 Understanding Bioinformatics 是一部范围更广的跨学科论著，也涉及蛋白质结构和系统层面的主题。

Uri Alon 的 An Introduction to Systems Biology 从序列分析转向生物回路的定量模型及其设计原理。这是另一门学科，最好在学完本书这样的算法课程之后再学。

如何使用本书

本书适合会编程的生物学学生，以及想了解生物学问题的计算机科学学生。读者需要掌握任意一种语言的基础编程和中学数学；学习第2章和第10章时，概率知识会有帮助。

• 免费开始： 先在网站上阅读第1–5章，判断这种风格是否适合自己。第1章（字符串算法）、第3章（图）和第5章（动态规划）是大多数课程的核心。
• 核心路线： 第1、3、5、7、9章提供模式查找、组装、比对、系统发育和读段比对等基本工具。
• 按兴趣选读： 概率方法读第2和第10章，质谱与蛋白质组学读第4和第11章，基因组重排读第6章，表达数据与聚类读第8章。
• 动手做题： 一边阅读一边解答各章在 Rosalind Textbook Track 上的题目，而不是读完再做；某一课看不懂时，就看讲课视频。

想获得证书或在正文中使用自动评分练习的学生，可以使用付费的交互式版本或相关的在线课程。若是自学，印刷版加上 Rosalind 就足够了。