基于Spark云計算及混沌遺傳的基因序列比對研究與實現

劉清雪 羅宇航

摘 要：針對現有比對方法速度和準確率不高問題，采用混沌遺傳算法快速搜索最優解，Spark云計算進行并行化比對，大幅降低比對執行時間以及提高比對準確度，為解密生物遺傳密碼提供有效工具。

關鍵詞：Spark云計算;混沌遺傳;基因序列比對

中圖分類號：TP391 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2021.03.011

本文著錄格式：劉清雪，羅宇航.基于Spark云計算及混沌遺傳的基因序列比對研究與實現[J].軟件，2021，42（03）：040-042

Research and Implementation of Gene Sequence Alignment Based on Spark Cloud Computing and Chaotic Inheritance

LIU Qingxue， LUO Yuhang

（Jilin University of Architecture and Technology， Changchun? Jilin? 130114）

【Abstract】：In view of the low speed and accuracy of existing comparison methods， chaotic genetic algorithm is used to quickly search for the optimal solution， and Spark cloud computing is used for parallel comparison， which greatly reduces the comparison execution time and improves the accuracy of the comparison， for decryption The biological genetic code provides an effective tool.

【Key words】：spark cloud computing;chaotic inheritance;gene sequence alignment

生物信息學是一門新興的領哉，是一門利用計算機技術研究生物系統之規律的學科，序列比對是生物信后序研究內容如進化樹、蛋白質結構預測、藥物設計等工作的基礎。在序列比對研究中通過查找到相似的基因序列，相似度推測及進化關系分析等來追溯序列的進化關系。生物序列比對是非?；钴S的領域，國內外對其進行了廣泛的研究并提出了許多方法。第一種方法是漸進對齊方法，通過動態規劃（DP）算法，Needleman-wunsch 或Smith-waterman，可以找到最高的得分一致性。然而，為了適應海量數據，大多的多重序列比對采用了啟發式算法。如T-coffee算法，該法速度快、直接，但易早熟。第二種方法是精確的多序列比對方法，它比漸進法結果更優，但計算量過于集中，因此待比序列數量受限。第三種方法是基于迭代的方法，如模擬退火、遺傳算法和進化編程等。遺傳算法通過自然選擇過程的類比，通過設計編碼方式、遺傳與變遺算子、設計目標函數、演化出一批候選解決方案。雖然遺傳算法易于并行化，能降低時間成本，但其自身存在局部優化、收斂速度慢等缺陷，為此引入混沌算法來實現種群多樣化以及快速收斂。隨著測序數據的增長，傳統的并行處理方法已經無法有效進行數據的存儲、分析和處理。而Spark云計算中對輸入數據在內存中采用的緩存的機制，數據只被加載一次，極大地節省了反復讀取的時間，極大的提高了運算效率[2]。

本文設計了一種基于混沌遺傳算法快速搜索算法，通過混沌計算提高比對速度和準確度。采用Spark云計算進一步提高基因序列并行比對速度，以及Hadoop HDFS的可擴展基因序列增量存儲系統提高存儲效率。

1基因序列比對原理分析及遺傳算法與混沌理論研究

基因比對通常用于比對兩條DNA序列或者蛋白質序列的同源性或者說相似性。首先對經典的動態規劃進行了分析，其將一個大問題變成小問題，并逐步求解。由第一個字符開始，假設為缺失，此后每增加一個字符，都有三種可能：mismatch，match，deletion/insert，計算對應的打分，得高分者為最優解，逐步迭代至最后一個字符[1]。

雙序列比對的實質就是在兩條待比較序列的任意位置插入一個或多個空位，使兩個序列具有最大的相似性，然后再根據比較結果推斷其生物學意義。

遺傳算法是計算數學中用于解決全局最優解的一種進化搜索算法。利用生物進化的規劃，首先對問題的解空間進行編碼，產生一定的個體，再通過遺傳、變遺、自然選擇及雜交等手段對個體進行演變，然后再始搜索。但傳統的遺傳算法亦存在不足，如早熟收斂、隨機漫游等。

混沌是決定動力學系統中出現的一種貌似隨機的運動，這種運動就是由系統內部的非線性因素引起的。

混沌是對確定性事物混亂無序狀態中潛在內在規律的一種描述，是非線性科學的重要分支?；煦绲幕舅枷肟梢岳斫鉃?，首先把原有混沌空間的混沌變量，線性映射到求解間，然后根據混沌的特性，在解空間對目標進行混沌搜索，混沌優化方法具有初始條件有很強的敏感性，初始條件下非常微小的變化，若經過n次不斷放大，也會造成巨大的影響。正是這種第三性，才使混沌算法容易跳出局部最優點，找到全局最優解。

鑒于混沌優化理論與遺傳算法的特點，將二者相結合提出一揚長避短的新的方法，即能提高收斂速度，又能跳出局部最優的局限。組織算法首先通過混沌優化過程產生初始個體，再以遺傳算法求得的最優解為中心加以小幅度混沌擾動，來進行搜索，找到全局最優點。

2基于混沌遺傳的雙序列比對改進算法

經典遺傳算法存在種群分布不均勻，收斂速度慢，常陷于局部最優解等問題。針對此問題提出基于Logistic映射的混沌遺傳算法，使用混沌映射產生混沌序列代替隨機個體產生過程來改進遺傳算法，保持種群多樣性的同時提升算法效率，降低迭代次數達到全局最優解。主要研究以下四個方面的內容。

（1）基因序列的遺傳編碼;

（2）適應度計算函數的設計;

（3）空位罰分;

（4）混沌與遺傳算子的融合，依據序列比對的主要操作和遺傳算法的進化過程，設計了選擇、混沌交叉和混沌變異三種算子。

2.1基因序列的遺傳編碼

例：對如圖1所示的序列S和序列T，根據Need-leman-Wunsch算法建立矩陣，在矩陣的當前位置向下一位置移動只有三種可能，向右、沿對角線向右下、向下，并分別用字符R、B和D表示，則兩個序列的比對的一個結果，便可用從矩陣左上角到右下角的一條路線，這個路線可以用一個字符串A來表示，且該字符串中的字符屬于集合{R，B，D}。向下或向右移動一格，表示在垂直或水平序列中插入一個空位，沿對角線移動一格，表示下一位兩序列的字符是匹配的。序列S與T的比對結果則可以表示為字符串：“BBBBBRBBBB”，即為染色體的編碼。

2.2適應度計算

對于每一個體，根據其對應的序列比對字符串及空位罰分公式計算出相應序列比對的分值，適應度值是個體是否能進行迭代的依據，在其計算的過程中要適應度值不為負，如出現負值則需要做一定的轉換。

2.3空位罰分

生物在進化過程中，必然會有基因的改變，因此在實際的序列比對時必須考慮堿基的插入或缺失的變化，而這種插入和缺失可能是一個也可能是多個堿基缺失或插入，空位罰分即是為反映這種變化的方法。為了能更真實的反應出序列的相似性，采用更能體現生物學意義的仿射空位打分法。單個空位與連續空位采用不同的賦值方法，單個的空位罰分采用定值Xg，連續空位中第一個空位為Xg，之后的每個空位用Yg表示，連續的空位長為K，則仿射空位打分法的計算方法為Xg+k*Yg。

2.4混沌遺傳算子設計

依據序列比對的主要操作和遺傳算法的進化過程，設計了選擇操作、混沌交叉操作和混沌變異操作。

（1）選擇操作：每次選擇兩個個體，僅保留適應度較大的個體進入下一代群體中待選，將生成的初始群體中的PopSize個個體進行適應度評價，適應度值越大的個體被遺傳到下一代的概率也越大。本算法采用隨機聯賽選擇（Stochastic Tournament Model）方，聯賽規模N的取值為2。

（2）混沌交叉操作：設有L位長染色體，在（0，1）區間上隨機取一個數xn為初值，利用Logistic 模型迭代產生一個（0，1）區間的混沌序列xn+1。利用公式C= （int）xn+1*L把序列xn+1映射至染色體基因位置空間，以此來確定交叉操作發生位置，并以概率Pc進行單點交叉。在形成新的子代的過程中，僅需小范圍更換部分點基因。

（3）混沌變異操作：利用混沌序列確定混沌交叉位置的方法來確定變異點位置，并以pm的概率從父代中隨機選取變異個體，在某一位或某幾位變異位置上作變異運算。

（4）結束條件：達到預定的迭代次數或者最大值不在變化時停止搜索。

3基于Spark云計算的基因序列比對實現實驗環境

本實驗的Spark集群是由一個主節點（NameNode）和3個從節點（DataNode）構成。以學院實驗室的虛擬化大數據平臺為基礎，采用如下的配置：64位虛擬機4臺，Centos6.5操作系統;服務器為Apache的hadoop- 2.5.2;Spark版本為Spark-3.0.6，JDK版本為1.8;Scala版本為2.12.6，并采用集成的開發環境Eclipse。

為了提高本實驗的可比性，在實驗室的同等配置的虛擬機上，安裝與Spark集群相同的操作系統，作為單機版實驗。并從NCBI（national center for biotechno-logy information）下載不同大小數據集的比對序列進行兩種實驗的比對，結果如表1所示：

4結論

該算法利用混沌算法與遺傳算法的互補性，一定程度上增強了序列比對的敏感性，改進了比對質量，優化了遺傳算法的局部搜索能力。由于Spark云計算的運行機制，本算法在處理大規模數據多步迭代計算時，能大大的提高計算效率，隨著文件大小的增加，處理相同的數據集時，集群方法明顯比單機法時間，且文件越大，這種優勢越明顯。但在分析小數據時則沒有更多的優勢。

參考文獻

[1] 王芳芳，馬志強，王素華.基于遺傳算法的序列比對方法[J].吉林大學學報（信息科學版），2013（3）：423-429.

[2] 劉振羽.基于Spark的基因組學數據比對算法的并行化研究與比對平臺構建[D].呼和浩特：內蒙古農業大學，2019.