生物信息学自20世纪80年代后期诞生以来发展迅速，不仅在于其自身的内涵和外延方面都有了明显的拓展，而且也确已成为当今生命科学研究不可或缺的重要技术之一。本书从基本的算法入手，系统而深入地展示了生物信息学研究中涉及到的数学技术问题，并对此作了活泼而不失严谨、深刻而又明晰的阐述。

这是一本关于生物信息学算法和计算思想的导论性教科书，原著由国际上的权威学者撰写，经国内知名专家精心翻译为中文，系统介绍推动生物信息学不断进步的算法原理。全书强调的是算法中思想的运用，而不是对表面上并不相关的各类问题进行简单的堆砌。体现了以下特色：阐述生物学中的相关问题，涉及对问题的模型化处理并提供一种或多种解决方案；简要介绍生物信息学领域领军人物；饶有趣味的小插图使得概念更加具体和形象，方法更容易被领会，激励学生学习的兴趣并鼓励他们加入到生物信息学研究工作中来。书中的大量论述表明：较少的几种设计思想就能解决大量的生物学难题。

目前，可供本科学生使用的生物信息学著作为数不多，本书恰恰是其中的一本。国内生物信息学，计算生物学、计算数学等领域的本科生、研究生和其他研究人员，会从书中汲取基本的算法原理、解决实际问题的方法和技巧，进而更好地从事相关研究工作。

1 绪论

2 算法与复杂性

 2.1 算法是什么？

 2.2 生物学算法与计算机算法

 2.3 找钱问题

 2.4 正确的与错误的算法

 2.5 递归算法

 2.6 迭代算法与递归算法的比较

 2.7 快速算法与慢速算法的比较

 2.8 大O记号

 2.9 算法设计技术

 2.10 易处理与不易处理问题的比较

 2.11 附注

 人物天地：Richard Karp

 2.12 问题

3 分子生物学简介

 3.1 生命是由什么组成的？

 3.2 什么是遗传物质？

 3.3 基因是干什么的？

 3.4 哪些分子编码基因？

 3.5 DNA的结构是怎样的？

 3.6 在DNA和蛋白质间传递信息的物质是什么？

 3.7 蛋白质是由什么组成的？

 3.8 我们该如何去分析DNA？

 3.9 一个物种的个体差异是怎样产生的？

 3.10 不同物种间有怎样的差异？

 3.11 为什么要搞生物信息学？

 人物天地：Russell F.Doolittle

4 穷举搜索

 4.1 限制酶切作图

 4.2 不实用的限制酶切作图算法

 4.3 一个实用的限制酶切作图算法

 4.4 DNA序列上的调控基序

 4.5 序列剖面

 4.6 基序发现问题

 4.7 检索树

 4.8 发现基序

 4.9 发现一个中间字符串

 4.10 附注

 人物天地：Gary Stormo

 4.11 问题

5 贪婪算法

 5.1 基因组重排

 5.2 反序排序法

 5.3 近似算法

 5.4 断点：贪婪的另一面

 5.5 贪婪方法与基序发现

 5.6 附注

 人物天地：David Sankoff

 5.7 问题

6 动态规划算法

 6.1 DNA序列比较的力量

 6.2 找钱问题重述

 6.3 曼哈顿游客问题

 6.4 编辑距离与联配

 6.5 最长共同子序列

 6.6 全局序列联配

 6.7 得分联配

 6.8 局部序列联配

 6.9 缺口罚分联配

 6.10 多重联配

 6.11 基因预测

 6.12 基因预测的统计方法

 6.13 基于相似性的基因预测方法

 6.14 剪接联配

 6.15 附注

 人物天地：Michael Waterman

 6.1 6 问题

7 分而治之算法

 7.1 排序问题的分治法

 7.2 空间效率高的序列联配

 7.3 模序联配和四个俄罗斯人的加速法

 7.4 在亚二次时间内构建联配

 7.5 附注

 人物天地：Webb Miller

 7.6 问题

8 图算法

 8.1 图

 8.2 图与遗传学

 8.3 DNA测序

 8.4 最短超字符串问题

 8.5 作为可选择测序技术的DNA阵列

 8.6 杂交测序

 8.7 SBH与Hamilton路问题

 8.8 SBH与欧拉路问题

 8.9 DNA测序中的片段装配

 8.10 蛋白质测序和鉴定

 8.11 肽测序问题

 8.12 谱图

 8.13 基于数据库搜索的蛋白质鉴定

 8.14 谱的卷积

 8.15 谱联配

 8.16 附注

 8.17 问题

9 组合模式匹配

 9.1 重复序列发现

 9.2 哈希表

 9.3 精确模式匹配

 9.4 关键词树

 9.5 后缀树

 9.6 启发式相似性搜索算法

 9.7 近似模式匹配

 9.8 BLAST：依靠数据库的序列比较

 9.9 附注

 人物天地：Gene Myers

 9.10 问题

10 聚类和树

 10.1 基因表达分析

 10.2 系统聚类

 10.3 k-均值聚类

 10.4 聚类和有瑕团

 10.5 进化树

 10.6 基于距离的树重构

 10.7 由可加矩阵重构树

 10.8 进化树与系统聚类

 10.9 基于字符的树重构

 10.10 小简约问题

 10.11 大简约问题

 10.12 附注

 人物天地：Ron Shamir

 10.13 问题

11 隐马氏模型

 11.1 CG岛和“公平赌场”

 11.2 公平赌场和隐马氏模型

 11.3 解码算法

 11.4 隐马氏模型参数估计

 11.5 剖面隐马氏模型联配

 11.6 附注

 人物天地：David Haussler

 11.7 问题

12 随机化算法

 12.1 排序问题回顾

 12.2 吉布斯抽样

 12.3 随机投影

 12.4 附注

 12.5 问题

参考文献

索引