Introduction to bioinformatics algorithms

1绪论1
2算法与复杂性6
21算法是什么？6
22生物学算法与计算机算法11
23找钱问题14
24正确的与错误的算法17
25递归算法20
26迭代算法与递归算法的比较24
27快速算法与慢速算法的比较28
28大O记号30
29算法设计技术33
210易处理与不易处理问题的比较39
211附注41
人物天地：Richard Karp42
212问题44
3分子生物学简介47
31生命是由什么组成的？47
32什么是遗传物质？48
33基因是干什么的？49
34哪些分子编码基因？50
35DNA的结构是怎样的？51
36在DNA和蛋白质间传递信息的物质是什么？52
37蛋白质是由什么组成的？53
38我们该如何去分析DNA？55
39一个物种的个体差异是怎样产生的？59
310不同物种间有怎样的差异？60
311为什么要搞生物信息学？61
人物天地：Russell F.Doolittle64
4穷举搜索67
41限制酶切作图67
42不实用的限制酶切作图算法71
43一个实用的限制酶切作图算法72
44DNA序列上的调控基序74
45序列剖面76
46基序发现问题79
47检索树81
48发现基序88
49发现一个中间字符串90
410附注93
人物天地：Gary Stormo95
411问题97
5贪婪算法101
51基因组重排101
52反序排序法103
53近似算法105
54断点：贪婪的另一面106
55 贪婪方法与基序发现109
56附注111
人物天地：David Sankoff112
57问题115
6动态规划算法118
61DNA序列比较的力量118
62找钱问题重述119
63曼哈顿游客问题122
64编辑距离与联配132
65最长共同子序列136
66全局序列联配140
67得分联配141
68局部序列联配142
69缺口罚分联配145
610多重联配146
611基因预测151
612基因预测的统计方法154
613基于相似性的基因预测方法156
614剪接联配158
615附注162
人物天地：Michael Waterman163
616问题165
7分而治之算法178
71排序问题的分治法178
72空间效率高的序列联配181
73模序联配和四个俄罗斯人的加速法184
74在亚二次时间内构建联配187
75附注188
人物天地：Webb Miller189
76问题192
8图算法194
81图194
82图与遗传学202
83DNA测序204
84最短超字符串问题205
85作为可选择测序技术的DNA阵列207
86杂交测序209
87SBH与Hamilton路问题210
88SBH与欧拉路问题211
89DNA测序中的片段装配214
810蛋白质测序和鉴定217
811肽测序问题220
812谱图222
813基于数据库搜索的蛋白质鉴定224
814谱的卷积226
815谱联配228
816附注232
817问题234
9组合模式匹配241
91重复序列发现241
92哈希表242
93精确模式匹配245
94关键词树247
95后缀树249
96启发式相似性搜索算法251
97近似模式匹配253
98BLAST：依靠数据库的序列比较256
99附注257
人物天地：Gene Myers258
910问题261
10聚类和树263
101基因表达分析263
102系统聚类265
103k簿值聚类268
104聚类和有瑕团270
105进化树274
106基于距离的树重构277
107由可加矩阵重构树279
108进化树与系统聚类283
109基于字符的树重构285
1010小简约问题286
1011大简约问题290
1012附注292
人物天地：Ron Shamir294
1013问题297
11隐马氏模型299
111CG岛和“公平赌场”299
112公平赌场和隐马氏模型301
113解码算法304
114隐马氏模型参数估计306
115剖面隐马氏模型联配307
116附注310
人物天地：David Haussler311
117问题314
12随机化算法316
121排序问题回顾316
122吉布斯抽样318
123随机投影320
124附注322
125问题323
参考文献325
索引332