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

1緒論1
2算法與復(fù)雜性6
21算法是什么？6
22生物學(xué)算法與計(jì)算機(jī)算法11
23找錢問(wèn)題14
24正確的與錯(cuò)誤的算法17
25遞歸算法20
26迭代算法與遞歸算法的比較24
27快速算法與慢速算法的比較28
28大O記號(hào)30
29算法設(shè)計(jì)技術(shù)33
210易處理與不易處理問(wèn)題的比較39
211附注41
人物天地：Richard Karp42
212問(wèn)題44
3分子生物學(xué)簡(jiǎn)介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我們?cè)撊绾稳シ治鯠NA？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)問(wèn)題79
47檢索樹(shù)81
48發(fā)現(xiàn)基序88
49發(fā)現(xiàn)一個(gè)中間字符串90
410附注93
人物天地：Gary Stormo95
411問(wèn)題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問(wèn)題115
6動(dòng)態(tài)規(guī)劃算法118
61DNA序列比較的力量118
62找錢問(wèn)題重述119
63曼哈頓游客問(wèn)題122
64編輯距離與聯(lián)配132
65最長(zhǎng)共同子序列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ù)測(cè)151
612基因預(yù)測(cè)的統(tǒng)計(jì)方法154
613基于相似性的基因預(yù)測(cè)方法156
614剪接聯(lián)配158
615附注162
人物天地：Michael Waterman163
616問(wèn)題165
7分而治之算法178
71排序問(wèn)題的分治法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問(wèn)題192
8圖算法194
81圖194
82圖與遺傳學(xué)202
83DNA測(cè)序204
84最短超字符串問(wèn)題205
85作為可選擇測(cè)序技術(shù)的DNA陣列207
86雜交測(cè)序209
87SBH與Hamilton路問(wèn)題210
88SBH與歐拉路問(wèn)題211
89DNA測(cè)序中的片段裝配214
810蛋白質(zhì)測(cè)序和鑒定217
811肽測(cè)序問(wèn)題220
812譜圖222
813基于數(shù)據(jù)庫(kù)搜索的蛋白質(zhì)鑒定224
814譜的卷積226
815譜聯(lián)配228
816附注232
817問(wèn)題234
9組合模式匹配241
91重復(fù)序列發(fā)現(xiàn)241
92哈希表242
93精確模式匹配245
94關(guān)鍵詞樹(shù)247
95后綴樹(shù)249
96啟發(fā)式相似性搜索算法251
97近似模式匹配253
98BLAST：依靠數(shù)據(jù)庫(kù)的序列比較256
99附注257
人物天地：Gene Myers258
910問(wèn)題261
10聚類和樹(shù)263
101基因表達(dá)分析263
102系統(tǒng)聚類265
103k均值聚類268
104聚類和有瑕團(tuán)270
105進(jìn)化樹(shù)274
106基于距離的樹(shù)重構(gòu)277
107由可加矩陣重構(gòu)樹(shù)279
108進(jìn)化樹(shù)與系統(tǒng)聚類283
109基于字符的樹(shù)重構(gòu)285
1010小簡(jiǎn)約問(wèn)題286
1011大簡(jiǎn)約問(wèn)題290
1012附注292
人物天地：Ron Shamir294
1013問(wèn)題297
11隱馬氏模型299
111CG島和“公平賭場(chǎng)”299
112公平賭場(chǎng)和隱馬氏模型301
113解碼算法304
114隱馬氏模型參數(shù)估計(jì)306
115剖面隱馬氏模型聯(lián)配307
116附注310
人物天地：David Haussler311
117問(wèn)題314
12隨機(jī)化算法316
121排序問(wèn)題回顧316
122吉布斯抽樣318
123隨機(jī)投影320
124附注322
125問(wèn)題323
參考文獻(xiàn)325
索引332