生物信息算法导论

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附注

人物天地：RichardKarp

2.12问题

3分子生物学简介

3.1生命是由什么组成的？

3.2什么是遗传物质？

3.3基因是干什么的？

3.4哪些分子编码基因？

3.5DNA的结构是怎样的？

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

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

3.8我们该如何去分析DNA？

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

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

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

人物天地：RussellF.Doolittle

4穷举搜索

4.1限制酶切作图

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

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

4.4DNA序列上的调控基序

4.5序列剖面

4.6基序发现问题

4.7检索树

4.8发现基序

4.9发现一个中间字符串

4.10附注

人物天地：GaryStormo

4.11问题

5贪婪算法

5.1基因组重排

5.2反序排序法

5.3近似算法

5.4断点：贪婪的另一面

5.5贪婪方法与基序发现

5.6附注

人物天地：DavidSankoff

5.7问题

6动态规划算法

6.1DNA序列比较的力量

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附注

人物天地：MichaelWaterman

6.16问题

7分而治之算法

7.1排序问题的分治法

7.2空间效率高的序列联配

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

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

7.5附注

人物天地：WebbMiller

7.6问题

8图算法

8.1图

8.2图与遗传学

8.3DNA测序

8.4最短超字符串问题

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

8.6杂交测序

8.7SBH与Hamilton路问题

8.8SBH与欧拉路问题

8.9DNA测序中的片段装配

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.8BLAST：依靠数据库的序列比较

9.9附注

人物天地：GeneMyers

9.10问题

10聚类和树

10.1基因表达分析

10.2系统聚类

10.3k-均值聚类

10.4聚类和有瑕团

10.5进化树

10.6基于距离的树重构

10.7由可加矩阵重构树

10.8进化树与系统聚类

10.9基于字符的树重构

10.10小简约问题

10.11大简约问题

10.12附注

人物天地：RonShamir

10.13问题

11隐马氏模型

11.1CG岛和“公平赌场”

11.2公平赌场和隐马氏模型

11.3解码算法

11.4隐马氏模型参数估计

11.5剖面隐马氏模型联配

11.6附注

人物天地：DavidHaussler

11.7问题

12随机化算法

12.1排序问题回顾

12.2吉布斯抽样

12.3随机投影

12.4附注

12.5问题

参考文献

索引

　　生物信息学自20世纪80年代后期诞生以来发展迅速，不仅在于其自身的内涵和外延方面都有了明显的拓展，而且也确已成为当今生命科学研究不可或缺的重要技术之一。本书从基本的算法入手，系统而深入地展示了生物信息学研究中涉及到的数学技术问题，并对此作了活泼而不失严谨、深刻而又明晰的阐述。　　这是一本关于生物信息学算法和计算思想的导论性教科书，原著由国际上的权威学者撰写，经国内知名专家精心翻译为中文，系统介绍推动生物信息学不断进步的算法原理。全书强调的是算法中思想的运用，而不是对表面上并不相关的各类问题进行简单的堆砌。体现了以下特色：阐述生物学中的相关问题，涉及对问题的模型化处理并提供一种或多种解决方案；简要介绍生物信息学领域领军人物；饶有趣味的小插图使得概念更加具体和形象，方法更容易被领会，激励学生学习的兴趣并鼓励他们加入到生物信息学研究工作中来。书中的大量论述表明：较少的几种设计思想就能解决大量的生物学难题。