《生物信息學導論——面向高性能計算的算法與套用》是2011年出版的圖書，作者是王勇獻、王正華。
基本介紹
- 書名：《生物信息學導論——面向高性能計算的算法與套用》
- 作者：王勇獻、王正華
- ISBN：9787302250227
- 定價：49元
- 出版時間：2011-9-19
- 裝幀：平裝
基本信息,圖書簡介,第一篇預備知識篇1,第1 章分子生物學基礎3,第2 章數學及計算機科學基礎20,第二篇序列分析篇57,第3 章序列比對的基本方法59,第4 章序列比對的並行計算103,第5 章基於字元串精確匹配的序列比較127,第6 章基因識別142,第7 章馬氏鏈與隱馬氏模型156,第8 章序列進化的基本模型186,第9 章分子進化樹的重構198,第三篇蛋白質組學分析篇255,第10章蛋白質的結構預測257,第11章蛋白質序列鑑定的質譜分析291,第四篇生物學網路分析篇333,第12章蛋白質相互作用的預測335,第13章生物學網路的模組劃分359,第14章大規模網路的數據挖掘技術385,
基本信息
作者：王勇獻、王正華
ISBN：9787302250227
定價：49元
印次：1-1
裝幀：平裝
印刷日期：2011-9-19
圖書簡介
本書主要針對生物信息學中的典型套用，從計算方法角度介紹相關算法的原理及套用；內容分成生物學及數理基礎、生物序列分析、蛋白質組學分析以及大規模生物學網路分析等四個專題，涉及生物分子序列分析、基因發現、分子進化分析、蛋白質結構預測、蛋白質肽測序、生物學網路模組劃分等具體問題的求解原理及算法實現。
本書的讀者對象是具有現代分子生物學及計算機科學基本知識的研究生及相關科研人員，在附加習題後也可作為生物信息學方面的入門及進階教材，供生物醫學工程、計算機套用等專業學生使用。
第一篇預備知識篇1
第1 章分子生物學基礎3
1.1 生命的演化與分類............................... 4
1.2核酸：DNA與RNA.............................. 5
1.3 蛋白質...................................... 7
1.4 DNA 的複製.................................. 9
1.5 基因與染色體.................................. 10
1.6 基因表達.................................... 10
1.6.1 轉錄................................... 11
1.6.2 遺傳密碼................................ 11
1.6.3 基因的進化——遺傳與變異...................... 14
1.7 現代生物工程技術............................... 16
1.8 現代分子生物學中的經典計算問題...................... 18
第2 章數學及計算機科學基礎20
2.1 線性代數理論.................................. 20
2.1.1 記號與約定............................... 20
2.1.2 矩陣的範數............................... 20
2.1.3 矩陣的特徵值與特徵向量....................... 21
2.1.4 矩陣的廣義逆.............................. 22
2.2 機率論基礎知識................................. 22
2.2.1 隨機事件................................ 22
2.2.2 機率的三種定義............................. 23
2.2.3 機率的加法原理............................. 24
2.2.4 條件機率................................ 24
2.2.5全機率公式和Bayes公式....................... 24
2.2.6 獨立隨機試驗與貝努利定律...................... 25
2.2.7 隨機變數及其分布........................... 26
2.2.8 常用的隨機分布............................. 27
2.2.9 機率分布的熵與相對熵......................... 30
X 目錄
2.2.10 隨機過程................................ 31
2.2.11 一階馬氏鏈............................... 31
2.2.12 隨機遊動................................ 34
2.2.13 高階馬氏鏈............................... 34
2.2.14 統計推斷與假設檢驗.......................... 35
2.3 最最佳化理論................................... 35
2.3.1 問題描述................................ 35
2.3.2 Lagrange 理論............................. 37
2.4 統計學習理論.................................. 41
2.4.1 引言................................... 41
2.4.2 機器學習的基本問題和方法...................... 42
2.4.3 統計學習理論的核心內容....................... 45
2.5 函式增長速度的比較.............................. 54
第二篇序列分析篇57
第3 章序列比對的基本方法59
3.1 序列的相似性與同源性............................. 59
3.2 點陣圖...................................... 60
3.3 兩序列比對概述................................. 61
3.4 全局比對的動態規劃方法........................... 62
3.5 局部比對的動態規劃方法........................... 64
3.6 重疊區域匹配的準全局比對算法........................ 66
3.7 空位罰分模型.................................. 68
3.8 仿射空位罰分模型下的全局比對算法..................... 69
3.9 仿射空位罰分模型下的局部比對算法..................... 72
3.10 降價空間存儲的兩序列比對算法........................ 75
3.10.1 線性空間複雜性算法.......................... 75
3.10.2 CheckPoint 算法............................ 77
3.11 降低時間開銷的兩序列比對算法........................ 82
3.11.1 分塊比對算法.............................. 82
3.11.2 帶狀比對算法.............................. 83
3.12 比對得分的正則化............................... 85
3.13 啟發式的近似尋優比對算法.......................... 86
3.13.1 FASTA ................................. 86
3.13.2 BLAST ................................. 88
3.14 比對得分的統計學顯著性........................... 90
目錄XI
3.15 多序列比對................................... 90
3.15.1 MSA................................... 93
3.15.2 漸進式比對............................... 94
3.15.3 Gibbs 採樣方法............................. 97
3.15.4 啟發式多序列比對軟體與工具..................... 98
3.16 胺基酸替換矩陣................................. 99
3.16.1 PAM 胺基酸替換矩陣......................... 99
3.16.2 BLOSUM 胺基酸替換矩陣....................... 101
3.17 小結....................................... 102
第4 章序列比對的並行計算103
4.1 並行編程模型.................................. 103
4.1.1 並行計算的粒度............................. 103
4.1.2 進程間的通信.............................. 104
4.2 並行計算機系統結構.............................. 105
4.2.1 通用並行計算機系統.......................... 105
4.2.2 專用並行處理硬體........................... 105
4.3 序列比對及其並行化方案........................... 106
4.4 Smith-Waterman 算法的細粒度並行實現................... 107
4.4.1 SWMMX 並行算法........................... 108
4.4.2 SWSSE2 並行算法........................... 109
4.4.3 條帶型並行算法............................. 110
4.4.4 基於分塊分治策略的並行算法..................... 111
4.4.5 其他並行算法.............................. 115
4.5 序列資料庫搜尋的粗粒度並行算法...................... 116
4.5.1並行FASTA.............................. 116
4.5.2 TurboBLAST.............................. 117
4.5.3 mpiBLAST ............................... 117
4.6 多序列比對的並行算法............................. 118
4.6.1 HMMER 及其並行算法........................ 118
4.6.2 ClustalW ................................ 119
4.6.3 ClustalW-MPI ............................. 121
4.6.4並行ClustalW、HTClustal和MULTICLUSTAL......... 121
4.7基於專用硬體FPGA的序列比對....................... 123
4.7.1 FPGA 硬體設備............................ 123
4.7.2 FPGA 並行計算............................ 124
XII 目錄
第5 章基於字元串精確匹配的序列比較127
5.1 模式的精確匹配與非精確匹配......................... 127
5.2 樸素的模式匹配算法.............................. 128
5.3 線性時間的字元串搜尋算法.......................... 128
5.4 基於關鍵字樹的模式集合匹配算法...................... 130
5.5 後綴樹...................................... 132
5.6 後綴樹的構造.................................. 134
5.7 後綴數組.................................... 135
5.8 基因組中的重複序列.............................. 136
5.9 後綴樹用於搜尋重複子串和獨特子串..................... 136
5.10 最長重複序列的搜尋算法........................... 137
5.11 廣義後綴樹................................... 138
5.12 最長公共子串問題............................... 138
5.13 k 次失配問題.................................. 139
5.14 小結....................................... 141
第6 章基因識別142
6.1 基因識別與預測的計算方法.......................... 142
6.2 預測算法的準確性度量............................. 144
6.3 獨立識別法................................... 145
6.3.1 用於基因識別的常用序列信號..................... 146
6.3.2 閱讀框的相位及基因中的外顯子類型................. 146
6.3.3 密碼子使用偏好............................. 147
6.3.4 用序列特徵圖尋找剪接位點...................... 149
6.3.5 外顯子鏈問題.............................. 151
6.4 基於比較的基因識別方法........................... 153
第7 章馬氏鏈與隱馬氏模型156
7.1 馬爾可夫鏈................................... 156
7.2 隱馬爾可夫模型................................. 159
7.3 計算全機率的正向算法............................. 162
7.4 計算全機率的反向算法............................. 164
7.5解碼問題的Viterbi算法............................ 166
7.5.1 各時間點獨立考慮的最可能路徑.................... 166
7.5.2 各時間點綜合考慮的最可能路徑.................... 167
7.6 模型參數的估計................................. 169
7.6.1 已知路徑時的參數重估......................... 169
7.6.2 Baum-Welch 方法........................... 170
目錄XIII
7.6.3 Baum-Welch 算法的推導....................... 173
7.6.4參數重估的Baldi-Chauvin梯度下降法................ 174
7.6.5 Baldi–Chauvin 梯度下降法的推導.................. 175
7.6.6 Mamitsuka 算法............................ 177
7.6.7 Mamitsuka 參數重估算法的推導................... 177
7.7帶有啞狀態的HMM.............................. 178
7.8譜HMM..................................... 181
7.9採用譜HMM進行多序列比對建模...................... 183
7.10利用HMM對基因識別問題進行建模..................... 184
第8 章序列進化的基本模型186
8.1 核苷酸替代的進化模型............................. 186
8.2 連續時間下的進化模型............................. 190
8.2.1 Jukes-Cantor 進化模型......................... 190
8.2.2 Kimura 進化模型............................ 191
8.2.3 Felsenstein 進化模型.......................... 192
8.2.4 HKY 進化模型............................. 192
8.3 離散時間下的進化模型............................. 193
8.3.1 Jukes-Cantor 進化模型......................... 193
8.3.2 Kimura 進化模型............................ 194
8.3.3 Felsenstein 進化模型.......................... 196
8.3.4 HKY 進化模型............................. 197
第9 章分子進化樹的重構198
9.1 進化樹的概念與術語.............................. 198
9.1.1 二叉樹.................................. 198
9.1.2 樹的標度................................ 198
9.1.3 有根樹與無根樹............................. 199
9.1.4 樹的定根方法.............................. 199
9.1.5 物種樹與基因樹............................. 200
9.1.6 分歧經歷的時間............................. 202
9.1.7 樹的文本表示法............................. 202
9.1.8 進化樹拓撲結構的計數......................... 202
9.1.9 不同樹之間的拓撲距離......................... 204
9.1.10 一致樹.................................. 206
9.1.11 分子進化樹重構的基本流程...................... 207
9.2 進化樹重構的簡約類方法........................... 208
9.3 進化樹重構的距離類方法........................... 213
XIV 目錄
9.3.1 距離................................... 213
9.3.2 鄰居加入方法.............................. 215
9.3.3 UPGMA 方法.............................. 223
9.3.4 誤差平方和最小方法.......................... 226
9.4 進化樹重構的統計類方法........................... 228
9.4.1 樹的似然度............................... 229
9.4.2 Horner 規則與修剪算法........................ 230
9.4.3 算法加速的策略............................. 232
9.4.4 時間可逆性、樹的根結點及分子鐘樹間的關聯性........... 233
9.4.5 數據缺失及比對空位的處理...................... 234
9.4.6 進化速率關於位點可變的建模方法.................. 235
9.5 樹拓撲空間的搜尋技術............................. 238
9.5.1 最近鄰居交換法............................. 238
9.5.2 子樹剪枝嫁接法............................. 239
9.5.3 分支界限法............................... 240
9.6 似然度最大化的數值算法........................... 240
9.6.1 一元函式最佳化問題........................... 241
9.6.2 多變數最佳化問題............................. 242
9.6.3 進化樹分析中參數估計的套用問題.................. 244
9.7 模型選擇與假設檢驗問題........................... 245
9.7.1 似然比檢驗............................... 245
9.7.2 Akaike 信息準則方法.......................... 246
9.7.3 Bayes 信息準則方法.......................... 246
9.8 進化樹拓撲結構的建模、估計與檢驗..................... 246
9.8.1 估計與假設檢驗............................. 246
9.8.2 Bootstrap 方法............................. 247
9.8.3 內部分支檢驗法............................. 252
9.8.4 KH 檢驗與修正............................. 253
9.8.5 簡約類方法中的指標.......................... 254
第三篇蛋白質組學分析篇255
第10章蛋白質的結構預測257
10.1 蛋白質的層次性結構.............................. 257
10.2 常見的二級結構單元.............................. 258
10.2.1 螺旋結構................................ 259
10.2.2 β 摺疊結構............................... 261
目錄XV
10.2.3 β 轉角結構............................... 262
10.3 蛋白質二級結構檢測.............................. 263
10.4 蛋白質二級結構預測的計算方法........................ 265
10.4.1 早期的預測方法............................. 266
10.4.2 判別分析法............................... 266
10.4.3 基於神經網路的預測算法....................... 270
10.4.4 最近鄰居法............................... 272
10.4.5基於譜HMM的結構預測....................... 273
10.4.6 結構預測的線索化方法......................... 273
10.4.7 結構預測的分子動力學方法...................... 274
10.4.8蛋白質摺疊預測的格子化HP模型.................. 276
10.5 蛋白質二級結構預測算法的性能評價..................... 277
10.5.1 問題描述................................ 278
10.5.2 蛋白質結構預測算法性能評估指標.................. 279
10.5.3 性能評估指標對結構預測建模的指導作用.............. 283
10.5.4 各評估指標的比較及使用原則..................... 285
10.6 蛋白質結構的比對方法............................. 286
10.6.1 肽鏈局部結構特徵的提取....................... 286
10.6.2 結構特徵的規範化及廣義後綴樹的構建................ 288
10.6.3 蛋白質結構的比較與搜尋....................... 289
第11章蛋白質序列鑑定的質譜分析291
11.1 質譜技術.................................... 291
11.1.1 質譜儀的基本工作原理......................... 291
11.1.2 串聯質譜儀............................... 292
11.2 質譜數據分析.................................. 292
11.2.1 串聯質譜中的離子類型......................... 292
11.2.2 質譜圖.................................. 294
11.2.3 碎片離子質量與母離子質量的關係.................. 295
11.2.4 理論質譜與實驗質譜.......................... 296
11.3 實驗質譜數據的預處理............................. 297
11.3.1 噪聲過濾的基線確定方法....................... 298
11.3.2 同位素峰識別方法........................... 299
11.4 質譜比較的非機率型打分方法......................... 299
11.4.1 基於單峰或區間匹配的打分...................... 299
11.4.2 基於向量夾角餘弦的打分....................... 299
11.4.3 基於信號互相關性的打分....................... 300
XVI 目錄
11.4.4 基於排名的打分............................. 300
11.5 質譜比較的機率型打分方法.......................... 301
11.5.1 Bayes 類打分方法........................... 301
11.5.2 對數似然比打分方法.......................... 303
11.6 基於串聯質譜的蛋白質鑑定.......................... 305
11.7 蛋白質鑑定的從頭測序法........................... 307
11.7.1 從訓練數據中學習離子類型信息.................... 308
11.7.2 質譜網路圖............................... 309
11.7.3 為質譜網路圖中的結點打分...................... 312
11.7.4 構建質譜網路圖............................. 314
11.7.5 使用質譜網路圖完成肽段的從頭測序................. 314
11.7.6 為質譜網路圖中的路徑打分...................... 316
11.7.7 肽序列測定求解與反對稱路徑..................... 317
11.7.8 多個質譜進行組合以改進從頭測序效果................ 318
11.7.9肽序列測定的PepNovo方法..................... 319
11.7.10 蛋白質從頭測序技術的新進展.................... 322
11.8 含有修飾的質譜比較與肽鑑定......................... 324
11.8.1 含有突變和翻譯後修飾的肽序列鑑定................. 324
11.8.2 分塊搜尋方法.............................. 324
11.8.3 質譜卷積與質譜比對.......................... 326
第四篇生物學網路分析篇333
第12章蛋白質相互作用的預測335
12.1 蛋白質之間的相互作用............................. 335
12.1.1 蛋白質相互作用的概述......................... 335
12.1.2 蛋白質相互作用網路.......................... 336
12.2 蛋白質相互作用測定的實驗方法........................ 337
12.3 研究蛋白質相互作用的生物信息學分析方法................. 339
12.3.1 基於系統發育譜相似性的預測方法.................. 340
12.3.2 基於基因融合事件的預測方法..................... 341
12.3.3 基於基因鄰接關係的預測方法..................... 342
12.3.4 基於進化信息的分析方法....................... 342
12.3.5 其他分析方法.............................. 350
12.4 蛋白質結構域水平的相互作用預測...................... 352
12.4.1 蛋白質的結構域............................. 352
12.4.2 基於共同進化相關性的結構域相互作用分析方法........... 353
目錄XVII
12.4.3基於PPI網路進行結構域相互作用預測............... 353
12.5 小結....................................... 358
第13章生物學網路的模組劃分359
13.1 引言....................................... 359
13.2 複雜網路的結構特徵.............................. 361
13.2.1 常用網路結構特徵度量指標...................... 361
13.2.2 複雜網路的三個系統化特徵...................... 364
13.2.3 刻畫網路結構特徵的其他指標..................... 364
13.3 複雜網路結構特徵度量指標的計算方法.................... 366
13.4 生物學網路結構分析的並行計算........................ 369
13.5 複雜網路的結構模組劃分及生物學網路功能模組挖掘............ 370
13.6 生物學網路模組劃分的傳統聚類方法..................... 372
13.6.1 ADJW 層次式聚類算法........................ 372
13.6.2 Kernighan-Lin 聚類算法........................ 373
13.6.3基於邊介數的聚類：GN算法..................... 374
13.6.4 快速分裂算法.............................. 375
13.6.5 Newman 快速算法........................... 375
13.6.6 層次式聚類結果的可視化輸出..................... 376
13.7 生物學網路模組劃分的譜聚類方法...................... 377
13.7.1 基於鄰接矩陣的譜分析......................... 378
13.7.2 譜平分法................................ 379
13.7.3基於Normal矩陣的譜平分法..................... 380
13.8 生物學網路模組劃分的混合式聚類算法.................... 382
13.9 網路模組劃分結果的評價........................... 384
第14章大規模網路的數據挖掘技術385
14.1 聚類分析.................................... 385
14.1.1 相似性測度............................... 385
14.1.2 聚類準則................................ 386
14.1.3 聚類算法................................ 387
14.2 層次聚類法................................... 388
14.2.1 單一連結聚類法............................. 388
14.2.2 完全連結聚類法............................. 389
14.2.3 平均連結聚類法............................. 389
14.2.4 平均簇連結法.............................. 390
14.2.5 組對質心法............................... 390
14.2.6 Ward 層次式聚類法.......................... 390
XVIII目錄
14.3K均值聚類方法................................391
14.4核分析方法...................................393
14.4.1線性分類器與非線性分類器......................393
14.4.2支持向量機...............................400
14.4.3支持向量機的套用與實踐.......................403
14.5基於核的K均值聚類方法...........................407
14.6譜聚類方法...................................408
14.6.1常用圖論記號與概念..........................409
14.6.2基於數據相似性構建圖結構......................410
14.6.3拉普拉斯矩陣及其性質.........................411
14.6.4譜聚類算法...............................414
14.6.5從最小割的角度解釋譜聚類......................416
14.6.6從隨機遊動角度解釋譜聚類......................422
14.6.7從矩陣擾動理論角度解釋譜聚類....................426
14.6.8從矩陣外形縮減角度解釋譜聚類....................429
14.6.9譜聚類中如何確定最終簇的數目....................433
14.7K均值聚類與譜聚類的統一..........................434
14.7.1K均值聚類算法的形式化.......................434
14.7.2最小化規範割問題與核K均值聚類的等價性主題索引人名索引插圖索引表格索引算法索引參考文獻
............ 436 438 462
