多目標遺傳算法的含假結(jié)RNA二級結(jié)構(gòu)預(yù)測

顧 倜，蔡磊鑫，王 帥，呂 強

(1.蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，蘇州 215006;2.江蘇省計算機信息處理技術(shù)重點實驗室(蘇州大學(xué))，蘇州 215006)

多目標遺傳算法的含假結(jié)RNA二級結(jié)構(gòu)預(yù)測

顧 倜1，蔡磊鑫1，王 帥1，呂 強2*

(1.蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，蘇州 215006;2.江蘇省計算機信息處理技術(shù)重點實驗室(蘇州大學(xué))，蘇州 215006)

假結(jié)是RNA中一種重要的結(jié)構(gòu)，由于建模的困難導(dǎo)致它更難被預(yù)測。通過堿基之間的配對概率來預(yù)測含假結(jié)RNA二級結(jié)構(gòu)的ProbKnot算法具有很高的精度，但該算法僅用了配對概率作為預(yù)測依據(jù)，導(dǎo)致陰性配對大量出現(xiàn)，因此精度中的特異性較低。實驗結(jié)合ProbKnot算法中堿基配對概率模型，通過使用多目標遺傳算法，從而提高預(yù)測含假結(jié)RNA二級結(jié)構(gòu)的特異性，以此促進總體精度的提高。實驗過程中，首先計算出每個堿基成為單鏈的概率，作為新增的預(yù)測依據(jù)，然后使用遺傳算法對RNA二級結(jié)構(gòu)進行交叉、變異和迭代，最后得到Pareto最優(yōu)解，進一步得出最高的最大期望精度。實驗結(jié)果表明，在使用的RNA案例中，采用該方法比現(xiàn)有方法精度平均提高約4%。

RNA二級結(jié)構(gòu); 假結(jié); 多目標優(yōu)化; 遺傳算法; 最大期望精度

在最初的生物中心法則中，RNA被認為在表達遺傳信息時作為蛋白質(zhì)翻譯，發(fā)揮了短暫的作用。后來發(fā)現(xiàn)RNA除了翻譯蛋白質(zhì)，還具有多種其他功能，如調(diào)控基因表達，轉(zhuǎn)運RNA，催化肽鏈形成和指導(dǎo)蛋白質(zhì)合成等。隨著研究的深入，RNA的形象已經(jīng)由功能單一的簡單線性堿基序列演變成種類多樣、結(jié)構(gòu)復(fù)雜、功能特異的生命核心物，同時它在中心法則中取得了與DNA和蛋白質(zhì)同樣重要的地位。許多RNA序列具有準確定義的結(jié)構(gòu)，想要理解這些RNA序列如何實現(xiàn)它們的功能，知道它們的結(jié)構(gòu)是非常重要的[1]。

RNA中最基本的4種堿基為A(腺嘌呤)、U(尿嘧啶)、G(鳥嘌呤)、C(胞嘧啶)。RNA一級結(jié)構(gòu)是堿基的有序序列。RNA二級結(jié)構(gòu)是由堿基之間相互作用形成的3種規(guī)范堿基對AU，GC和GU以及未配對堿基的單鏈組成的結(jié)構(gòu)[2]。RNA三級結(jié)構(gòu)是原子的三維排列。因為RNA的結(jié)構(gòu)一般是分層次的，所以二級結(jié)構(gòu)可以在不用知道三級結(jié)構(gòu)的情況下得到確定，同樣也可以為預(yù)測三級結(jié)構(gòu)提供很大的幫助。RNA二級結(jié)構(gòu)承擔著由RNA一級結(jié)構(gòu)推測其三級結(jié)構(gòu)的橋梁作用。研究RNA二級結(jié)構(gòu)，可以為提高RNA及蛋白質(zhì)結(jié)構(gòu)預(yù)測的準確率提供幫助。因此，RNA結(jié)構(gòu)研究的一個重要切入點是對其二級結(jié)構(gòu)的研究。

鑒于二級結(jié)構(gòu)的重要性，對二級結(jié)構(gòu)的預(yù)測研究顯得尤為重要。預(yù)測RNA二級結(jié)構(gòu)的方法主要有序列比對法和最小自由能法。其中, 序列比對法需要耗費大量人力，預(yù)測效率較低，因而最小自由能法是預(yù)測RNA二級結(jié)構(gòu)時廣泛采用的一種方法。Zuker[3]提出的Mfold算法是早期基于最小自由能方法的二級結(jié)構(gòu)預(yù)測算法，該算法有很高的正確率，但不能預(yù)測含假結(jié)的復(fù)雜結(jié)構(gòu)。二級結(jié)構(gòu)預(yù)測中，假結(jié)作為一種特殊的結(jié)構(gòu)，是實現(xiàn)結(jié)構(gòu)功能的重要因素。但是因為堿基相互重疊的特性，生物信息計算對假結(jié)的預(yù)測難以奏效。預(yù)測包含假結(jié)的RNA二級結(jié)構(gòu)問題是NP難的[4]，但要分析RNA的真實結(jié)構(gòu)，對假結(jié)的準確預(yù)測是必須解決的問題。

通過加入假結(jié)約束來預(yù)測假結(jié)的最小自由能算法是目前使用比較多的預(yù)測方法，其中Probknot算法[5-6]在幾種RNA含假結(jié)二級結(jié)構(gòu)預(yù)測算法[7-10]中精準度較高。Probknot算法的配分函數(shù)(partition function)[11]利用機器學(xué)習法和熱力學(xué)模型[12]計算出每個堿基之間的配對概率，各個堿基通過配對概率相互配對，然后解除形成的結(jié)構(gòu)中連續(xù)配對堿基數(shù)較少的莖區(qū)，以確保穩(wěn)定性[13]，最終得出預(yù)測結(jié)果。本文運用多目標遺傳算法，通過提高特異性從而提高總體精度的方式來改進Probknot算法，并與Probknot算法以及其他算法的結(jié)果進行對比和總結(jié)。

1 打分函數(shù)與預(yù)測性能指標

1.1 打分函數(shù)MaxExpect

相比最小自由方法的最小自由能結(jié)構(gòu)，MaxExpect利用RNA結(jié)構(gòu)中各個堿基配對情況打分得到的最大期望精度結(jié)構(gòu)比最小自由能結(jié)構(gòu)具有更高的精度[14]。

MaxExpect的打分公式如下

(1)

式中:γ取1;Pbp(ij)為堿基i與j相互配對的概率;Pss(k)為堿基k是單鏈的概率。ProbKnot算法中Pbp(i,j)是已知的，本文通過Pbp(i,j)計算出Pss(k)為

(2)

1.2 預(yù)測性能指標

預(yù)測性能指標是用來評價RNA二級結(jié)構(gòu)預(yù)測結(jié)果好壞的標準。

馬休茲相互作用系數(shù)(Matthews correlation coefficient, MCC)是通過比對天然結(jié)構(gòu)與預(yù)測結(jié)構(gòu)而計算出來的值，最小值為-1，表示預(yù)測結(jié)構(gòu)與天然結(jié)構(gòu)堿基配對相似度為0；最大值為1，表示預(yù)測結(jié)構(gòu)與天然結(jié)構(gòu)相似度為1。 具體衡量公式如下：

(3)

(4)

(5)

式中：TP(true positive)為正確預(yù)測堿基對的個數(shù)；FN(false negative)為真實結(jié)構(gòu)中存在但沒有被正確預(yù)測出的堿基對個數(shù)；FP(false positive)為真實結(jié)構(gòu)中不存在卻被錯誤預(yù)測到的堿基對個數(shù)；TN(true negative)為正確預(yù)測的不配對的堿基的個數(shù)；敏感性X(sensitivity)指真實結(jié)構(gòu)中所有的堿基對中被正確預(yù)測到的百分比；特異性Y(specificity)指在所有預(yù)測到的堿基對中正確預(yù)測的百分比。

在評價RNA二級結(jié)構(gòu)預(yù)測的結(jié)果時，如果天然結(jié)構(gòu)中i與j配對，那么預(yù)測結(jié)構(gòu)中除了i與j配對，i與j+1或j-1以及j與i-1或i+1配對都被認為是正確的配對，這是考慮到了多種因素，包括確定確切配對的困難性，以及這些預(yù)測的配對在質(zhì)量上與正確配對的一致性[15]。

2 多目標遺傳算法

2.1 多目標優(yōu)化問題

多目標優(yōu)化問題的關(guān)鍵點在于如何使各個目標之間同時達到最優(yōu)[16-17]。多目標優(yōu)化問題的解不僅僅是一個全局最優(yōu)解，而是一個解集，本文稱這個解集為Pareto最優(yōu)解集[18]。在這個解集中彼此任意解都不相互支配，并且解集外的解都會被解集中至少一個解支配。

遺傳算法是一種可用于尋找最優(yōu)解的搜索算法，它借鑒了生物界的進化規(guī)律，通過模擬自然進化過程以此來搜索最優(yōu)解。由于遺傳算法運行一次能找到多目標優(yōu)化問題的多個Pareto最優(yōu)解，因而它是求解多目標優(yōu)化問題的一個有效手段[19]。

NSGA-II是目前多目標優(yōu)化領(lǐng)域中最優(yōu)秀的多目標遺傳算法之一，它被國內(nèi)外學(xué)者廣泛引用，本文將主要結(jié)合該算法的思想來進行實驗。

2.2 NSGA-II

NSGA-II(Non-dominated sorting genetic algorithm)是一種新型多目標優(yōu)化遺傳算法，相對于 NSGA 的缺陷，NSGA-II 有如下改進：計算復(fù)雜性從O(mN3)降至O(mN2)，具備最優(yōu)保留機制及無需確定一個共享參數(shù)的優(yōu)點，從而進一步提高計算效率和算法的魯棒性。NSGA-II該算法求得的 Pareto 最優(yōu)解分布均勻，收斂性和魯棒性好，具有良好的優(yōu)化效果，是求解多目標優(yōu)化問題的一種新思路[20-23]。

NSGA-II的遺傳算法中，通過適應(yīng)度函數(shù)計算每個個體的適應(yīng)度并對其進行排序，排序算法分為兩個步驟。

Step1Non-dominated sorting(非支配排序). 種群基于Pareto順序分為k個子集(Q1,…,Qk)，每個Qi中的個體都不會被Qj中的個體支配(i

Step2Crowding-distance sorting(擁擠距離排序).子群Qi用擁擠距離排序。在不擁擠局域內(nèi)的解優(yōu)先度更高。

2.2.1 非支配排序

快速非支配排序是基于非支配排序的改進算法見表1。

非支配排序。m個個體和種群中的其他個體進行支配關(guān)系比較，是否支配其他全部個體，復(fù)雜度為O(mN)；循環(huán)進行直到等級1中的非支配個體全部被搜索到，復(fù)雜度為O(mN2)；最壞的情況下，有N個等級，每個等級只存在一個解，復(fù)雜度為O(mN3)。

表1 快速非支配排序Table 1 Rapid non dominated sorting

2.2.2 擁擠距離排序

擁擠距離排序用于保持解的多樣性。每個個體的擁擠距離是通過計算與其相鄰的兩個個體在每個子目標函數(shù)上的距離差之和來求取,如圖1所示。

圖1 二目標函數(shù)的擁擠距離計算Fig.1 The crowding distance calculation of two objective functions

圖1所示個體i的擁擠距離為

Di=(fi+1,1-fi-1,1)+(fi-1,2-fi+1,2),

(6)

即圖1中虛線四邊形的長與寬之和。

排序時當兩個個體屬于不同等級的非支配解集時，等級較小的優(yōu)先度高，當兩個個體屬于相同等級的非支配解集時，擁擠距離較大的優(yōu)先度高,即

if(irankjdistance))then(i≥nj)

2.2.3 遺傳算法

NSGA-II中遺傳算法流程如圖2所示。

Step1創(chuàng)造一個初始父代種群P0，使用交叉和變異操作產(chǎn)生子代種群Q0。

Step2對P0和Q0組成的整體R0進行非支配排序，構(gòu)造所有不同等級的非支配解集Z1,Z2,Z3,……。

Step3對分好等級的非支配解集進行擁擠距離排序，根據(jù)適應(yīng)度高低得到前N個解，構(gòu)成下一次迭代的父代種群P1。

Step4重復(fù)上述3個步驟，直到結(jié)果收斂。

圖2 NSGA-II步驟Fig.2 Steps of NSGA-II

3 數(shù)據(jù)與實驗流程

3.1 數(shù)據(jù)集

本文采用ASE以及CRW的RNA數(shù)據(jù)集作為實驗的研究對象，對ASE與CRW的RNA天然結(jié)構(gòu)進行計算，提取出每個RNA結(jié)構(gòu)的一級序列，通過ProbKnot算法的配分函數(shù)，得到包含堿基配對概率的pfs文件，將此文件作為本文輸入。經(jīng)過計算，有效的數(shù)據(jù)集為877個。其中ASE案例450個，CRW案例427個(見表2)。ASE的序列長度大多數(shù)在200～500之間，CRW的序列長度大多數(shù)在1 000以上。

表2 實驗數(shù)據(jù)集表Table 2 The experimental dataset

3.2 實驗過程

基于多目標遺傳算法的含假結(jié)RNA二級結(jié)構(gòu)預(yù)測方法，實驗過程如下。

Step1首先通過對單個RNA序列進行變異算法得到不同的RNA二級結(jié)構(gòu)作為遺傳算法的初始種群，然后通過對初始種群內(nèi)的個體進行變異交叉算法形成數(shù)量相同的新的RNA二級結(jié)構(gòu)，再對每個RNA二級結(jié)構(gòu)進行適應(yīng)度計算排序，選擇適應(yīng)度較高的個體組成新的種群。

Step2重復(fù)該步驟直到結(jié)果收斂，將種群中的最優(yōu)個體作為結(jié)果輸出，得到這個RNA序列的二級結(jié)構(gòu)預(yù)測結(jié)果。

Step3輸入其他每個RNA序列來完成上述兩個步驟，得到所有RNA序列的二級結(jié)構(gòu)預(yù)測結(jié)果，作為實驗結(jié)果。其中，為了適應(yīng)遺傳算法中的交叉與變異，算法對RNA二級結(jié)構(gòu)采用如圖3所示的精英保留策略。圖3中，位于上方的結(jié)構(gòu)(a)表示1號和4號堿基配對、2號和3號堿基為單鏈的RNA二級結(jié)構(gòu)，它通過變異算法可能形成結(jié)構(gòu)(b)與結(jié)構(gòu)(c)。同樣的，位于下方的結(jié)構(gòu)(a)與結(jié)構(gòu)(b)通過交叉算法可能形成結(jié)構(gòu)(c)與結(jié)構(gòu)(d)。

圖3 RNA二級結(jié)構(gòu)的交叉和變異Fig.3 Crossing and mutating of RNA secondary structure

3.3 實驗參數(shù)設(shè)置

實驗的參數(shù)設(shè)置會對實驗結(jié)果產(chǎn)生影響。本次實驗中有4個參數(shù)對實驗結(jié)果影響較大，它們是populations，iterations， minloop與α，其中：Populations是初始種群數(shù)，iterations是收斂后迭代次數(shù)。這兩個參數(shù)值設(shè)置的越大，遺傳算法搜索到最優(yōu)解的可能性越高，但運行時間也會越長。根據(jù)RNA序列的長度大小，本次實驗populations的取值為1 000～2 000。由于RNA序列長度與種群數(shù)的區(qū)別，不同的結(jié)構(gòu)使用遺傳算法的迭代次數(shù)相差較大，所以iterations表示收斂后的迭代次數(shù)而不是總迭代次數(shù)，它的取值為500～1 000。

Minloop是最小螺旋長度，α是用于比較配對概率與單鏈概率的一個數(shù)值。為了提高交叉變異算法的效率，算法對形成的結(jié)構(gòu)進行了兩方面的約束：一是在每次交叉變異形成RNA二級結(jié)構(gòu)后，算法會去除長度小于minloop的螺旋來保證RNA結(jié)構(gòu)的穩(wěn)定性，因為天然結(jié)構(gòu)中螺旋長度小于3的結(jié)構(gòu)較為少見，所以minloop取值為3；二是在交叉變異時，只進行概率大于α的配對與解除配對，這樣可以減少結(jié)構(gòu)中配對概率與單鏈概率為0或很小的堿基對與單鏈，避免采用完全隨機交叉變異會消耗大量不必要資源的情況，α取值為0.001～0.1，這個值越大，算法收斂速度越快，但會降低結(jié)果的多樣性。

4 結(jié)果與分析

4.1 多目標遺傳算法與ProbKnot算法結(jié)果對比

在877個實驗結(jié)果中，有9個案例(其中ASE案例2個，CRW案例7個)的敏感性和特異性在兩種算法的計算下都為0，因此之后的數(shù)據(jù)統(tǒng)計中刪除了這9個案例。

圖4、5比較了實驗案例的敏感性與特異性，多目標遺傳算法的結(jié)果用黑色的點表示，Probknot算法的結(jié)果用灰色的點表示，點所在的位置越是接近右上，結(jié)果越好。圖4、5中表明,單從敏感性與特異性的結(jié)果上看，多目標遺傳算法的優(yōu)勢并不明顯。

圖4 448個ASE案例敏感性與特異性值統(tǒng)計Fig.4 The statistic of sensitivity and specificity about 448 cases of ASE

MCC值是綜合敏感性與特異性的評價指標，如圖6、7所示。多目標遺傳算法的結(jié)果用黑色的點表示，Probknot算法的結(jié)果用灰色的點表示，點所在的位置越是接近上方，結(jié)果越好。從圖6、7中可以看出，大多數(shù)黑色的點在灰色點的上方，這意味著在大多數(shù)實驗案例上，多目標遺傳算法的結(jié)果優(yōu)于Probknot算法。

圖5 420個CRW案例敏感性與特異性值統(tǒng)計Fig.5 The statistic of sensitivity and specificity about 420 cases of CRW

圖6 448個ASE案例MCC值統(tǒng)計Fig.6 The statistic of MCC about 448 cases of ASE

圖7 420個CRW案例MCC值統(tǒng)計Fig.7 The statistic of MCC about 420 cases of CRW

表3整理了ProbKnot算法和多目標遺傳算法的實驗數(shù)據(jù)的平均值。表3中數(shù)據(jù)表明，多目標遺傳算法在ASE和CRW數(shù)據(jù)集上有更高的特異性與MCC值。

表3 RNA二級結(jié)構(gòu)預(yù)測方法實驗對比表Table 3 Comparison of methods for predicting RNA secondary structure

4.2多目標遺傳算法與其他RNA二級結(jié)構(gòu)預(yù)測算法結(jié)果對比

本文選取了263個案例(其中ASE案例158個，CRW案例105個)，采用ProbKnot算法、多目標遺傳算法、MaxExpect算法、Fold算法[24]進行對比實驗。

表4整理了ProbKnot算法、多目標遺傳算法、MaxExpect算法、Fold算法的實驗數(shù)據(jù)的平均值。表4中數(shù)據(jù)表明,4種RNA二級結(jié)構(gòu)預(yù)測方法中，多目標遺傳算法在ASE和CRW數(shù)據(jù)集上有更高的特異性與MCC值，在CRW數(shù)據(jù)集上的特異性也較高。

由于CRW數(shù)據(jù)集中RNA序列長度相差較大，第2次對比實驗選取了一些長度較短的案例，表3中CRW數(shù)據(jù)集的總體精度比表2要高。

表4 4種RNA二級結(jié)構(gòu)預(yù)測方法實驗對比Table 4 Comparison of four methods for predicting RNA secondary structure

4.3 實驗小結(jié)

兩次對比實驗中，多目標遺傳算法在ASE和CRW數(shù)據(jù)集上的特異性與MCC的平均值更高，大多數(shù)案例在改進算法后MCC值得到提高，敏感性提升不明顯。因此本文可以得出結(jié)論，多目標遺傳算法的精度更高，得到的結(jié)果與天然結(jié)構(gòu)更接近。

5 結(jié) 論

1)本文基于多目標遺傳算法，使用概率模型進行RNA二級結(jié)構(gòu)打分，在多目標優(yōu)化部分計算出堿基的單鏈概率，以此完善概率模型。在遺傳算法部分根據(jù)RNA二級結(jié)構(gòu)的特征編寫適合的交叉變異算法，以此提高程序運行效率。

2)實驗結(jié)果表明，在ASE和CRW數(shù)據(jù)集上的對比試驗中，多目標遺傳算法的精度更高，相比ProbKnot算法，MCC值平均提高4%。

3)本文運用多目標優(yōu)化算法對假結(jié)RNA二級結(jié)構(gòu)進行了實驗預(yù)測，證明了多目標遺傳算法可以有效地增加含假結(jié)RNA二級結(jié)構(gòu)預(yù)測的精度，但仍然具有發(fā)展和改進的空間。

References)

[1]WAN Yue, QU Kun, ZHANG Qiangfeng, et al. Landscape and variation of RNA secondary structure across the human transcriptome[J]. Nature, 2014, 505(7485): 706-709. DOI:10.1038/nature12946.

[2]PENALVA L O F. RNA secondary structure[M]. New York: Encyclopedia of Systems Biology, 2013: 1864-1864. DOI:10.1007/978-1-4419-9863-7_319.

[3]ZUKER M. Mfold web server for nucleic acid folding and hybridization prediction[J]. Nucleic acids research, 2003, 31(13): 3406-3415.DOI: 10.1093/nar/gkg595.

[4]RUAN Jianhua, STORMO G D, ZHANG Weixiong. An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots[J]. Bioinformatics, 2004, 20(1): 58-66. DOI: 10.1093/bioinformatics/btg373.

[5]MATHEWS D H, DISNEY M D, CHILDS J L, et al. Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(19): 7287-7292. DOI: 10.1073/pnas.0401799101.

[6]BELLAOUSOV S, MATHEWS D H. ProbKnot: fast prediction of RNA secondary structure including pseudoknots[J]. Rna, 2010, 16(10): 1870-1880.DOI:10.1261/rna.2125310.

[7]BINDEWALD E, KLUTH T, SHAPIRO B A. CyloFold: secondary structure prediction including pseudoknots[J]. Nucleic Acids Research, 2010, 38(suppl_2): W368-W372.DOI:10.1093/nar/gkq432.

[8]SATO K, KATO Y, HAMADA M, et al. IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming[J]. Bioinformatics, 2011,27(13): i85-i93.DOI:10.1093/bioinformatics/btr215.

[9]JABBARI H, CONDON A. A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures[J]. BMC Bioinformatics, 2014, 15: 147. DOI: 10.1186/1471-2105-15-147.

[10]DAWSON W K, TAKAI T, ITO N, et al. A new entropy model for RNA: part III. Is the folding free energy landscape of RNA funnel shaped?[J]. Journal of Nucleic Acids Investigation, 2014, 5: 2652.DOI: 10.4081/jnai.2014.2652.

[11]MATHEWS D H. Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization[J]. Rna, 2004, 10(8): 1178-1190. DOI:10.1261/rna.7650904.

[12]SEETIN M G, MATHEWS D H. TurboKnot: rapid prediction of conserved RNA secondary structures including pseudoknots[J]. Bioinformatics, 2012, 28(6): 792-798. DOI: 10.1093/bioinformatics/bts044.

[13]YONEMOTO H, ASAI K, HAMADA M. A semi-supervised learning approach for RNA secondary structure prediction[J]. Computational Biology and Chemistry, 2015, 57: 72-79.DOI:10.1016/j.compbiolchem.2015.02.002.

[14]LU Z J, GLOOR J W, MATHEWS D H. Improved RNA secondary structure prediction by maximizing expected pair accuracy[J]. Rna, 2009, 15(10): 1805-1813. DOI:10.1261/rna.1643609.

[15]DEIGAN K E, LI T W, MATHEWS D H, et al. Accurate SHAPE-directed RNA structure determination[J]. Proceedings of the National Academy of Sciences, 2009, 106(1): 97-102. DOI:10.1073 pnas.0806929106.

[16]DEB K. Multi-objective optimization[M]. Springer US: Search Methodologies, 2014: 403-449.

[17]DEB K. Multi-objective optimization using evolutionary algorithms[M]. New York, NY: John Wiley & Sons, 2001: 3-34. DOI: 10.1007/978-0-85729-652-8_1.

[18]ARNOLD B C. Pareto distribution[M]. New York, NY: John Wiley & Sons, Ltd, 2015. DOI: 10.1002/9781118445112.stat01100.pub2.

[19]LI Hui, ZHANG Qingfu. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 284-302. DOI: 10.1109/TEVC.2008.925798.

[20]DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI: 10.1109/4235.996017.

[21]DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//International Conference on Parallel Problem Solving From Nature. Berlin Heidelberg: Springer, 2000: 849-858. DOI: 10.1007/3-540-45356-3_83.

[22]DEB K, JAIN H. Handling many-objective problems using an improved NSGA-II procedure[C]//2012 IEEE Congress on Evolutionary Computation. Brisbane, QLD, Australia: IEEE, 2012: 1-8.DOI: 10.1109/CEC.2012.6256519

[23]SEADA H, DEB K. U-nsga-III: A unified evolutionary optimization procedure for single, multiple, and many objectives: Proof-of-principle results[C]//International Conference on Evolutionary Multi-Criterion Optimization. Cham: Springer, 2015: 34-49. DOI: 10.1007/978-3-319-15892-1_3.

[24]BELLAOUSOV S, REUTER J S, SEETIN M G, et al. RNAstructure: Web servers for RNA secondary structure prediction and analysis[J]. Nucleic acids research, 2013, 41:W471-W474.DOI:10.1093/nar/gkt290.

PredictionofRNAsecondarystructureincludingpseudoknotsbasedonmulti-objectivegeneticalgorithm

GU Ti1，CAI Leixin1，WANG Shuai1，Lü Qiang2*

(1.SchoolofComputerScience&Technology,SoochowUniversity,Suzhou215006,China;2.ProvincialKeyLaboratoryforComputerInformationProcessingTechnologyofJiangsu(SoochowUniversity),Suzhou215006,China)

Pseudoknot is a kind of important structure in RNA, which is more difficult to be predicted due to the difficulty in training the prediction model. ProbKnot algorithm has a high accuracy in predicting the secondary structure of pseudoknotted RNA based on base-pair probabilities. However, this algorithm only makes use of the base-pair probabilities as a predictive feature, which leads to a large number of negative pairs and lower specificity. The overall accuracy can be improved which follows the improvement of specificity by combining the probabilistic model of base pairing in ProbKnot algorithm and multi-objective genetic algorithm. In the experiments, we will first calculate the single-stranded probability as a new predictive feature, and then use genetic algorithm to cross, mutate and iterate the secondary structure of RNA. Finally, we can get the Pareto optimal solutions and the highest maximum expected accuracy. The experiment results showed that in the RNA cases, applying this method could achieve an average increase of 4% in the accuracy compared with the current existing methods.

RNA secondary structure; Pseudoknot; Multi-objective optimization; Genetic algorithm; Maximum expected accuracy

TP391

A

1672-5565(2017)03-142-07

10.3969/j.issn.1672-5565.201701006

2017-01-20；

2017-04-11.

國家自然科學(xué)基金(61170125).

顧倜，男，碩士研究生，研究方向：生物信息計算；E-mail：20145227032@stu.suda.edu.cn.

*通信作者：呂強，男，教授，研究方向：生物信息計算、元啟發(fā)搜索、并行計算；E-mail：qiang@suda.edu.cn.