劉清雪 羅宇航

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

關(guān)鍵詞：Spark云計(jì)算;混沌遺傳;基因序列比對(duì)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2021.03.011

本文著錄格式：劉清雪，羅宇航.基于Spark云計(jì)算及混沌遺傳的基因序列比對(duì)研究與實(shí)現(xiàn)[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

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

本文設(shè)計(jì)了一種基于混沌遺傳算法快速搜索算法，通過混沌計(jì)算提高比對(duì)速度和準(zhǔn)確度。采用Spark云計(jì)算進(jìn)一步提高基因序列并行比對(duì)速度，以及Hadoop HDFS的可擴(kuò)展基因序列增量存儲(chǔ)系統(tǒng)提高存儲(chǔ)效率。

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

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

雙序列比對(duì)的實(shí)質(zhì)就是在兩條待比較序列的任意位置插入一個(gè)或多個(gè)空位，使兩個(gè)序列具有最大的相似性，然后再根據(jù)比較結(jié)果推斷其生物學(xué)意義。

遺傳算法是計(jì)算數(shù)學(xué)中用于解決全局最優(yōu)解的一種進(jìn)化搜索算法。利用生物進(jìn)化的規(guī)劃，首先對(duì)問題的解空間進(jìn)行編碼，產(chǎn)生一定的個(gè)體，再通過遺傳、變遺、自然選擇及雜交等手段對(duì)個(gè)體進(jìn)行演變，然后再始搜索。但傳統(tǒng)的遺傳算法亦存在不足，如早熟收斂、隨機(jī)漫游等。

混沌是決定動(dòng)力學(xué)系統(tǒng)中出現(xiàn)的一種貌似隨機(jī)的運(yùn)動(dòng)，這種運(yùn)動(dòng)就是由系統(tǒng)內(nèi)部的非線性因素引起的。

混沌是對(duì)確定性事物混亂無序狀態(tài)中潛在內(nèi)在規(guī)律的一種描述，是非線性科學(xué)的重要分支?；煦绲幕舅枷肟梢岳斫鉃椋紫劝言谢煦缈臻g的混沌變量，線性映射到求解間，然后根據(jù)混沌的特性，在解空間對(duì)目標(biāo)進(jìn)行混沌搜索，混沌優(yōu)化方法具有初始條件有很強(qiáng)的敏感性，初始條件下非常微小的變化，若經(jīng)過n次不斷放大，也會(huì)造成巨大的影響。正是這種第三性，才使混沌算法容易跳出局部最優(yōu)點(diǎn)，找到全局最優(yōu)解。

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

2基于混沌遺傳的雙序列比對(duì)改進(jìn)算法

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

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

（2）適應(yīng)度計(jì)算函數(shù)的設(shè)計(jì);

（3）空位罰分;

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

2.1基因序列的遺傳編碼

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

2.2適應(yīng)度計(jì)算

對(duì)于每一個(gè)體，根據(jù)其對(duì)應(yīng)的序列比對(duì)字符串及空位罰分公式計(jì)算出相應(yīng)序列比對(duì)的分值，適應(yīng)度值是個(gè)體是否能進(jìn)行迭代的依據(jù)，在其計(jì)算的過程中要適應(yīng)度值不為負(fù)，如出現(xiàn)負(fù)值則需要做一定的轉(zhuǎn)換。

2.3空位罰分

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

2.4混沌遺傳算子設(shè)計(jì)

依據(jù)序列比對(duì)的主要操作和遺傳算法的進(jìn)化過程，設(shè)計(jì)了選擇操作、混沌交叉操作和混沌變異操作。

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

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

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

（4）結(jié)束條件：達(dá)到預(yù)定的迭代次數(shù)或者最大值不在變化時(shí)停止搜索。

3基于Spark云計(jì)算的基因序列比對(duì)實(shí)現(xiàn)實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)的Spark集群是由一個(gè)主節(jié)點(diǎn)（NameNode）和3個(gè)從節(jié)點(diǎn)（DataNode）構(gòu)成。以學(xué)院實(shí)驗(yàn)室的虛擬化大數(shù)據(jù)平臺(tái)為基礎(chǔ)，采用如下的配置：64位虛擬機(jī)4臺(tái)，Centos6.5操作系統(tǒng);服務(wù)器為Apache的hadoop- 2.5.2;Spark版本為Spark-3.0.6，JDK版本為1.8;Scala版本為2.12.6，并采用集成的開發(fā)環(huán)境Eclipse。

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

4結(jié)論

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

參考文獻(xiàn)

[1] 王芳芳，馬志強(qiáng)，王素華.基于遺傳算法的序列比對(duì)方法[J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2013（3）：423-429.

[2] 劉振羽.基于Spark的基因組學(xué)數(shù)據(jù)比對(duì)算法的并行化研究與比對(duì)平臺(tái)構(gòu)建[D].呼和浩特：內(nèi)蒙古農(nóng)業(yè)大學(xué)，2019.