生物信息學(xué)算法導(dǎo)論

1緒論1
2算法與復(fù)雜性6
21算法是什么？6
22生物學(xué)算法與計(jì)算機(jī)算法11
23找錢問題14
24正確的與錯(cuò)誤的算法17
25遞歸算法20
26迭代算法與遞歸算法的比較24
27快速算法與慢速算法的比較28
28大O記號30
29算法設(shè)計(jì)技術(shù)33
210易處理與不易處理問題的比較39
211附注41
人物天地：Richard Karp42
212問題44
3分子生物學(xué)簡介47
31生命是由什么組成的？47
32什么是遺傳物質(zhì)？48
33基因是干什么的？49
34哪些分子編碼基因？50
35DNA的結(jié)構(gòu)是怎樣的？51
36在DNA和蛋白質(zhì)間傳遞信息的物質(zhì)是什么？52
37蛋白質(zhì)是由什么組成的？53
38我們該如何去分析DNA？55
39一個(gè)物種的個(gè)體差異是怎樣產(chǎn)生的？59
310不同物種間有怎樣的差異？60
311為什么要搞生物信息學(xué)？61
人物天地：Russell F.Doolittle64
4窮舉搜索67
41限制酶切作圖67
42不實(shí)用的限制酶切作圖算法71
43一個(gè)實(shí)用的限制酶切作圖算法72
44DNA序列上的調(diào)控基序74
45序列剖面76
46基序發(fā)現(xiàn)問題79
47檢索樹81
48發(fā)現(xiàn)基序88
49發(fā)現(xiàn)一個(gè)中間字符串90
410附注93
人物天地：Gary Stormo95
411問題97
5貪婪算法101
51基因組重排101
52反序排序法103
53近似算法105
54斷點(diǎn)：貪婪的另一面106
55 貪婪方法與基序發(fā)現(xiàn)109
56附注111
人物天地：David Sankoff112
57問題115
6動(dòng)態(tài)規(guī)劃算法118
61DNA序列比較的力量118
62找錢問題重述119
63曼哈頓游客問題122
64編輯距離與聯(lián)配132
65最長共同子序列136
66全局序列聯(lián)配140
67得分聯(lián)配141
68局部序列聯(lián)配142
69缺口罰分聯(lián)配145
610多重聯(lián)配146
611基因預(yù)測151
612基因預(yù)測的統(tǒng)計(jì)方法154
613基于相似性的基因預(yù)測方法156
614剪接聯(lián)配158
615附注162
人物天地：Michael Waterman163
616問題165
7分而治之算法178
71排序問題的分治法178
72空間效率高的序列聯(lián)配181
73模序聯(lián)配和四個(gè)俄羅斯人的加速法184
74在亞二次時(shí)間內(nèi)構(gòu)建聯(lián)配187
75附注188
人物天地：Webb Miller189
76問題192
8圖算法194
81圖194
82圖與遺傳學(xué)202
83DNA測序204
84最短超字符串問題205
85作為可選擇測序技術(shù)的DNA陣列207
86雜交測序209
87SBH與Hamilton路問題210
88SBH與歐拉路問題211
89DNA測序中的片段裝配214
810蛋白質(zhì)測序和鑒定217
811肽測序問題220
812譜圖222
813基于數(shù)據(jù)庫搜索的蛋白質(zhì)鑒定224
814譜的卷積226
815譜聯(lián)配228
816附注232
817問題234
9組合模式匹配241
91重復(fù)序列發(fā)現(xiàn)241
92哈希表242
93精確模式匹配245
94關(guān)鍵詞樹247
95后綴樹249
96啟發(fā)式相似性搜索算法251
97近似模式匹配253
98BLAST：依靠數(shù)據(jù)庫的序列比較256
99附注257
人物天地：Gene Myers258
910問題261
10聚類和樹263
101基因表達(dá)分析263
102系統(tǒng)聚類265
103k均值聚類268
104聚類和有瑕團(tuán)270
105進(jìn)化樹274
106基于距離的樹重構(gòu)277
107由可加矩陣重構(gòu)樹279
108進(jìn)化樹與系統(tǒng)聚類283
109基于字符的樹重構(gòu)285
1010小簡約問題286
1011大簡約問題290
1012附注292
人物天地：Ron Shamir294
1013問題297
11隱馬氏模型299
111CG島和“公平賭場”299
112公平賭場和隱馬氏模型301
113解碼算法304
114隱馬氏模型參數(shù)估計(jì)306
115剖面隱馬氏模型聯(lián)配307
116附注310
人物天地：David Haussler311
117問題314
12隨機(jī)化算法316
121排序問題回顧316
122吉布斯抽樣318
123隨機(jī)投影320
124附注322
125問題323
參考文獻(xiàn)325
索引332