顧 倜，蔡磊鑫，王 帥，呂 強(qiáng)

(1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，蘇州 215006;2.江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室(蘇州大學(xué))，蘇州 215006)

多目標(biāo)遺傳算法的含假結(jié)RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)

顧 倜1，蔡磊鑫1，王 帥1，呂 強(qiáng)2*

(1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，蘇州 215006;2.江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室(蘇州大學(xué))，蘇州 215006)

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

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

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

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

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

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

1 打分函數(shù)與預(yù)測(cè)性能指標(biāo)

1.1 打分函數(shù)MaxExpect

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

MaxExpect的打分公式如下

(1)

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

(2)

1.2 預(yù)測(cè)性能指標(biāo)

預(yù)測(cè)性能指標(biāo)是用來(lái)評(píng)價(jià)RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)結(jié)果好壞的標(biāo)準(zhǔn)。

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

(3)

(4)

(5)

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

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

2 多目標(biāo)遺傳算法

2.1 多目標(biāo)優(yōu)化問(wèn)題

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

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

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

2.2 NSGA-II

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

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

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

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

2.2.1 非支配排序

快速非支配排序是基于非支配排序的改進(jìn)算法見表1。

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

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

2.2.2 擁擠距離排序

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

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

圖1所示個(gè)體i的擁擠距離為

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

(6)

即圖1中虛線四邊形的長(zhǎng)與寬之和。

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

if(irankjdistance))then(i≥nj)

2.2.3 遺傳算法

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

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

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

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

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

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

3 數(shù)據(jù)與實(shí)驗(yàn)流程

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

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

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

3.2 實(shí)驗(yàn)過(guò)程

基于多目標(biāo)遺傳算法的含假結(jié)RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)方法，實(shí)驗(yàn)過(guò)程如下。

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

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

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

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

3.3 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

4 結(jié)果與分析

4.1 多目標(biāo)遺傳算法與ProbKnot算法結(jié)果對(duì)比

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

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

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

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

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

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

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

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

表3 RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)方法實(shí)驗(yàn)對(duì)比表Table 3 Comparison of methods for predicting RNA secondary structure

4.2多目標(biāo)遺傳算法與其他RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)算法結(jié)果對(duì)比

本文選取了263個(gè)案例(其中ASE案例158個(gè)，CRW案例105個(gè))，采用ProbKnot算法、多目標(biāo)遺傳算法、MaxExpect算法、Fold算法[24]進(jìn)行對(duì)比實(shí)驗(yàn)。

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

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

表4 4種RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)方法實(shí)驗(yàn)對(duì)比Table 4 Comparison of four methods for predicting RNA secondary structure

4.3 實(shí)驗(yàn)小結(jié)

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

5 結(jié) 論

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

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

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

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.

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

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

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