編輯推薦

介紹生物多序列比對的基礎知識，包括多序列比對的基本概念、原理、方法、常用數據庫、常用工具和應用等內容，並介紹進化算法和最優化理論的基礎知識，以及遺傳算法、粒子群優化算法和量子粒子群優化算法的優化過程及收斂性分析，為進行多序列比對的模擬提供理論基礎；然後詳細介紹各進化算法模擬多序列比對的過程與結果；*後對於多序列比對*重要的目標函數參數進行建模與分析。本書具有係統性強、可讀性強、可操作性強等特點。

內容簡介

本書全麵係統地介紹瞭進化算法在生物多序列比對中的應用，根據內容的分類，分為“多序列比對基礎篇”“多序列比對模擬篇”和“多序列比對參數篇”三個模塊。首先介紹生物多序列比對的基礎知識，包括多序列比對的基本概念、原理、方法、常用數據庫、常用工具和應用等內容，並介紹進化算法和最優化理論的基礎知識，以及遺傳算法、粒子群優化算法和量子粒子群優化算法的優化過程及收斂性分析，為進行多序列比對的模擬提供理論基礎；然後詳細介紹各進化算法模擬多序列比對的過程與結果；後對於多序列比對重要的目標函數參數進行建模與分析。本書具有係統性強、可讀性強、可操作性強等特點。

作者簡介

　　作者簡介作者簡介

　　龍海俠，1980年生，2007年獲江南大學計算機軟件與理論碩士學位，2010年獲江南大學輕工信息技術與工程博士學位，現就職於海南師範大學信息科學技術學院，副教授。研究方嚮：群體智能算法、進化算法、生物信息。碩士期間從事群體智能算法和進化算法的研究及其在聚類、圖像分割上的應用研究；博士期間從事生物信息的研究，重點研究多序列比對和培養基的優化；近5年從事深度學習算法和生物信息的研究。已齣版教材1部、專著1部，發錶論文30餘篇，主持省級課題2項，作為*完成人獲得省級奬勵2項。

　　李滿枝，1979年生，2004年6月獲西北工業大學計算數學專業理學碩士學位，現就職於海南師範大學數學與統計學院，副教授。主要研究方嚮：生物信息學、計算機數值模擬、算法構造等。碩士期間從事基於濛特卡羅方法的計算機模擬，近5年從事生物信息中的蛋白質功能預測研究。已在國內外核心期刊及學術會議上發錶多篇論文，齣版專著1部，並作為主要成員參與省級和*自然科學項目多項，現主持海南省自然科學基金“生物多序列比對的遺傳算法模擬及改進”。

　　王洪濤，1978年生，2008年6月獲海南師範大學應用數學專業理學碩士學位，現就職於海南師範大學數學與統計學院，副教授。主要研究方嚮：計算機數值模擬、算法構造、數學建模等。在國內外核心期刊及學術會議上發錶多篇論文，齣版專著1部，並作為主要成員參與海南省自然科學基金項目多項，目前是海南省自然科學基金“生物多序列比對的遺傳算法模擬及改進”的*二參與人。

　　付海艷，1978年生，2002年獲山東大學人工智能與模式識彆碩士學位，2009年獲山東大學係統理論博士學位，現就職於海南師範大學信息科學技術學院，教授。研究方嚮：評價理論與方法、決策理論與方法、不確定信息處理。碩士期間從事基於模糊集理論的評價方法和決策方法的研究，博士期間從事基於粗糙集理論和模糊集理論的不確定信息處理，近5年從事數據挖掘算法的研究。已齣版教材2部、專著1部，發錶論文30餘篇，主持*課題1項、省級課題6項，作為*完成人獲得省級奬勵2項。

目錄

上篇 多序列比對基礎篇
第1章 生物多序列比對 3
1.1 生物信息學 3
1.1.1 生物信息學的起源 3
1.1.2 生物信息學的概念 4
1.1.3 生物信息學的主要研究內容 4
1.2 序列比對的概念及其發展曆史 8
1.2.1 序列比對的提齣與基本概念 8
1.2.2 序列比對的目的和意義 8
1.2.3 國內外研究現狀 10
1.2.4 多序列比對麵臨的挑戰 10
1.3 多序列比對的基本原理 11
1.3.1 多序列比對的相關概念 11
1.3.2 序列比對的分類 12
1.3.3 多序列比對的數學定義 13
1.3.4 多序列比對的打分方法 14
1.4 多序列比對方法 22
1.4.1 比對方法 22
1.4.2 多序列比對算法 23
1.5 多序列比對常用數據庫 33
1.5.1 綜閤性數據庫 34
1.5.2 基準數據庫 36
1.6 多序列比對常用工具 40
1.6.1 搜索工具 40
1.6.2 常用的在綫多序列比對工具 42
1.7 多序列比對的應用 45
1.8 其他說明 46
1.8.1 多序列比對算法存在的問題 46
1.8.2 多序列比對算法的運算指標 47
1.8.3 多序列比對算法的展望 48
1.9 本章小結 48
參考文獻 49
第2章 進化算法和最優化理論 53
2.1 進化算法 53
2.1.1 遺傳算法 53
2.1.2 遺傳規劃 54
2.1.3 進化策略 56
2.1.4 進化規劃 57
2.1.5 粒子群優化算法 58
2.1.6 量子粒子群優化算法 61
2.2 最優化理論 63
2.2.1 最優化問題 64
2.2.2 局部優化算法 66
2.2.3 全局優化算法 67
2.2.4 最優化問題的求解 67
2.3 本章小結 69
參考文獻 69
第3章 遺傳算法、粒子群優化算法和量子粒子群優化算法 73
3.1 遺傳算法 73
3.1.1 遺傳算法的基本思想 73
3.1.2 遺傳算法中的基本術語 74
3.1.3 遺傳算法的步驟及流程圖 75
3.1.4 遺傳算法的構成要素 76
3.1.5 遺傳算法的優缺點 82
3.1.6 遺傳算法的應用現狀 84
3.1.7 遺傳算法的改進 86
3.2 粒子群優化算法 87
3.2.1 基本粒子群優化算法 87
3.2.2 帶慣性權重w的粒子群優化算法 89
3.2.3 帶收縮因子 的粒子群優化算法 91
3.3 量子粒子群優化算法 92
3.3.1 勢阱模型的建立 92
3.3.2 粒子的基本進化方程 95
3.3.3 QPSO算法的流程 96
3.3.4 QPSO算法的收斂性分析 97
3.4 QPSO算法的改進——基於選擇操作的QPSO算法 103
3.4.1 引言 103
3.4.2 采用錦標賽選擇操作的QPSO算法(QPSO-TS) 105
3.4.3 采用輪盤賭選擇操作的QPSO算法(QPSO-RS) 106
3.4.4 算法的收斂性分析 107
3.5 本章小結 110
參考文獻 110
中篇 多序列比對模擬篇
第4章 遺傳算法在多序列比對中的應用 115
4.1 基本遺傳算法模擬多序列比對 115
4.1.1 引言 115
4.1.2 多序列比對問題及數學描述 117
4.1.3 算法設計 117
4.1.4 實驗算例與分析 120
4.1.5 結論 123
4.2 改進遺傳算法之初始種群優化 124
4.2.1 引言 124
4.2.2 優化原理 125
4.2.3 幾種初始化方法的構造 127
4.2.4 加入MAFFT種子的初始化 130
4.2.5 實驗算例與結果 130
4.2.6 結論 135
4.3 改進遺傳算法之交叉算子優化 136
4.3.1 引言 136
4.3.2 交叉算子設計 137
4.3.3 實驗算例與結果 140
4.3.4 結論 143
4.4 本章小結 144
參考文獻 144
第5章 QPSO算法在多序列比對中的應用 149
5.1 多序列比對的含義 149
5.2 基於二進製QPSO算法的序列比對 151
5.2.1 二進製的PSO算法(BPSO) 151
5.2.2 二進製的QPSO算法(BQPSO) 152
5.2.3 基於BPSO或BQPSO的多序列比對 156
5.3 本章小結 163
參考文獻 165
第6章 基於隱馬爾可夫模型和QPSO算法的多序列比對 167
6.1 引言 167
6.2 隱馬爾可夫模型 168
6.2.1 隱馬爾可夫模型的基本原理 168
6.2.2 隱馬爾可夫模型的基本問題與算法 169
6.3 基於剖麵HMM和QPSO的多序列比對 172
6.3.1 融閤多樣性的QPSO算法 174
6.3.2 評估訓練算法的質量 179
6.3.3 模型的聯配問題 179
6.3.4 評估比對序列的質量 181
6.4 本章小結 191
參考文獻 191
第7章 多序列比對的並行計算 193
7.1 長序列首尾分段並行比對算法 193
7.1.1 引言 193
7.1.2 構造原理 195
7.1.3 數值模擬結果 196
7.1.4 結論 198
7.2 本章小結 198
參考文獻 199
下篇 多序列比對參數篇
第8章 多序列比對的參數研究 203
8.1 基於SP目標函數的多序列比對參數研究 203
8.1.1 引言 203
8.1.2 基本定義 204
8.1.3 公式推導 206
8.1.4 實驗結果與分析 210
8.1.5 結論 217
8.2 在綫工具MAFFT參數研究 218
8.2.1 引言 218
8.2.2 基本定義 220
8.2.3 實驗結果與分析 222
8.2.4 結論 229
8.3 本章小結 230
參考文獻 231
附錄 相關的源代碼 235
附錄A 基本遺傳算法總程序 235
附錄B 生成初始種群bio_var 239
附錄C 生成初始種群rand_var 243
附錄D 選擇算子selection 245
附錄E 橫嚮多行交叉算子hhor_crossover4to2 248
附錄F 縱嚮交叉算子ver_crossover4to2 253
附錄G 變異算子mutation 259
附錄H 適應度函數：SP函數 262
附錄I 多序列比對參數研究的相關程序 264
附錄J HMM和QPSO算法用於多序列比對的程序 266

前言/序言

　　隨著人類基因組計劃的實施和科技的發展，生物學數據呈爆炸式增長，這些海量的生物學數據必須通過生物信息學手段進行收集、分析和整理後，纔能成為有用的信息。而如何有效分析和處理這些大型序列數據(即序列分析)成為生物信息學的首要任務。序列比對是生物序列分析的主要方法，也是生物信息學中挑戰性的問題之一。序列比對在序列裝配、序列注釋、基因和蛋白質的結構和功能預測以及係統發育和進化分析等方麵均有廣泛應用，因此對它的研究一直以來都是熱點。

　　進化算法是一類藉鑒生物界自然選擇和自然遺傳機製的隨機搜索算法，主要包括遺傳算法(geneticalgorithm，GA)、遺傳規劃(geneticprogramming，GP)、進化策略(evolutionarystrategies，ES)、進化規劃(evolutionaryprogramming，EP)、粒子群優化(particleswarmoptimization，PSO)算法以及近年齣現的量子粒子群優化(quantum-behavedparticleswarmoptimization，QPSO)算法，它們通過一係列的進化算子和進化方程，尋找問題的最優解。本書把上述的進化算法及其改進的進化算法，結閤數學模型，用於解決生物多序列比對問題。

　　全書正文各章節結構如下圖所示，共分為“多序列比對基礎篇”“多序列比對模擬篇”和“多序列比對參數篇”三個模塊。

　　“多序列比對基礎篇”(第1章～第3章)介紹生物多序列比對的基礎知識，包括多序列比對的基本概念、原理、方法、常用數據庫、常用工具和應用等內容，並介紹進化算法和最優化理論的基礎知識，以及遺傳算法、粒子群優化算法和量子粒子群優化算法的優化過程及收斂性分析，為進行多序列比對的模擬提供理論基礎。

　　“多序列比對模擬篇”(第4章～第7章)是本書的核心部分，主要內容概括如下：

　　(1)應用基本遺傳算法及其改進的遺傳算法進行多序列比對。基本遺傳算法(GA)是通過對進化過程中的種群反復進行選擇、交叉、變異操作來模擬自然界中種群的演變過程，直到滿足一定性能要求纔結束計算，它本身的結構決定瞭它可以用在多序列比對上。遺傳算法可以有效地解決生物多序列比對問題，但是遺傳算法高度依賴於初始種群，好的初始種群方可以得到好的結果。為提高計算效率，提高比對質量，可從遺傳算法最關鍵的組成部分入手，通過優化初始種群的質量，達到改進算法的目的。另外，又針對遺傳算法最基本的交叉算子，設計瞭保優和選擇混閤的交叉操作後處理方法cross4to2。該方法不但服從保優原則，而且又再一次經過選擇操作的精英保留過程，使得最優秀的個體進入下一代。這種處理將算法的整體搜索能力和局部搜索能力大大提高。通過與經典CLUSTAL算法的比較，驗證瞭該算法的有效性。

　　(2)使用二進製的PSO算法和二進製的QPSO算法進行多序列的比對。為瞭避免算法的早熟，在算法中還加入瞭變異算子。首先對群體中的個體進行編碼，然後根據目標函數值(通常為序列的得分函數)找齣空位的最優位置，使序列比對的結果最優，確定序列的相似性以至於同源性。

　　(3)使用QPSO算法和改進的QPSO算法，結閤隱馬爾可夫模型(HMM)進行多序列的比對。這主要涉及兩個過程：優化過程和比對過程。優化過程主要研究剖麵HMM模型參數的訓練過程，獲得較優模型。前麵已經提及現有的訓練算法通常會陷入局部最優，因此研究全局優化算法對模型進行訓練極其重要。用並行的群體智能優化算法優化剖麵HMM時，優化的主要對象是轉移概率和符號發齣概率，優化對象的編碼方式以及參數的個數將會影響比對的速度，優化過程中算法的全局收斂性將會影響到比對的準確度。比對過程主要研究比對算法的實現過程，獲得比對結果。當使用HMM進行多序列比對時，每條序列從開始到結束通過這些狀態穿越模型，在這些待比對序列中進行空位字符“－”的插入和刪除操作，得到一個多序列比對結果的矩陣。但應確保在比對結果中有盡可能多的列由相同的非空字符組成，同時在由不同字符組成的列中某一個或某幾個非空字符的數目盡可能多，以便發現不同序列之間的相似部分，進而推斷它們在功能和結構上的相似性。

　　(4)多序列比對的並行計算。隨著計算機科學技術在第三代測序技術以及基因組拼接技術方麵的不斷發展，生物信息領域獲得瞭越來越多的長基因組序列數據，長序列比對成為急需解決的問題。傳統的算法對內存空間的龐大需求以及漫長的運行時間已經無法滿足對這種大規模數據的處理，因此長序列比對的並行計算成為研究的一個熱點問題。通常的並行模式有：基於“分而治之”策略，結閤並行計算的長序列首尾分段並行比對算法；基於“粗細粒度”的並行數據並行算法。

　　多序列比對是生物信息學的一個重要研究內容，比對結果高度依賴於目標函數和比對工具的參數設置，包括空位罰分(GOP和GEP)以及替換矩陣。“多序列比對參數篇”(第8章)主要做瞭兩方麵的工作：

　　(1)研究SP(sum-of-pair)目標函數，提齣確定各參數最優值的理論依據，給齣替換矩陣判斷公式和最佳空位罰分取值公式，結閤待測序列信息得齣與之相符的一組最優參數，從而得到更好的比對結果。通過與精度較高的多序列比對工具MAFFT、CLUSTALW的比較，結閤BAliBASE2.0數據庫進行實例驗證，結果錶明，根據公式得齣的參數可以得到比默認參數更優的比對結果，而且本書公式優化瞭多序列比對結果，具有可行性和高效性。

　　(2)基於BAliBASE3.0數據庫，應用MAFFT工具(MAFFT-7.220-WIN64version)進行多序列比對，得齣替換矩陣和空位罰分的最優參數組閤，從而得到更好的比對結果。實驗結果錶明，通過與MAFFT(MAFFT-7.220-WIN64version)、CLUSTALW(CLUSTALW-2.1-WIN)的默認參數比較，根據本研究得齣的最優參數組閤可以得到比默認參數更優的比對結果，而且研究結果給齣的最優參數組閤優化瞭多序列比對結果。

　　本書是由多人編撰完成的，編寫分工如下：第5章、第6章和附錄I～J由龍海俠編撰完成，共計9萬字；第4章、第8章和附錄A～H由李滿枝編撰完成，共計9萬字；第1章、第7章由王洪濤編撰完成，共計8.5萬字；第2章和第3章由付海艷編撰完成，共計8.5萬字。全書由龍海俠和李滿枝統稿和修改。本書的齣版獲海南師範大學學術著作齣版資助項目、海南省自然科學基金項目(20151003，614235)、國傢自然科學基金(71461008)、海南師範大學數學與統計學院“計算數學”重點學科和信息科學技術學院“計算機科學與技術”一級學科的資助，特此錶示感謝。

　　本書可作為生物信息學、計算生物學、計算機和計算數學等專業本科生或研究生的教材或學習參考書，也可作為相關研究人員的研究參考書。由於我們的專業知識與工作背景的限製，書中還有很多錯誤或不足之處，敬請希望讀者批評指正。

　　龍海俠李滿枝

　　2017年1月於海南師範大學