基于布谷鳥(niǎo)搜索的帶假結(jié)RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)

摘要：RNA在細(xì)胞中具有重要的結(jié)構(gòu)、功能和調(diào)節(jié)作用。RNA單鏈的結(jié)構(gòu)對(duì)于其在有機(jī)系統(tǒng)中的作用具有決定性影響，因此RNA結(jié)構(gòu)預(yù)測(cè)成為研究熱點(diǎn)。假結(jié)是一種重要但是難以預(yù)測(cè)的RNA結(jié)構(gòu)。以熱動(dòng)力學(xué)模型與最小自由能量理論為基礎(chǔ)，本文提出了一種稱(chēng)為CSRNA的基于布谷鳥(niǎo)搜索的啟發(fā)式算法，用以預(yù)測(cè)帶假結(jié)RNA二級(jí)結(jié)構(gòu)。通過(guò)基于已知RNA序列的預(yù)測(cè)實(shí)驗(yàn)，本文比較了CSRNA與幾種算法的預(yù)測(cè)結(jié)果，證明CSRNA算法的有用性及有效性。

關(guān)鍵詞：RNA二級(jí)結(jié)構(gòu)預(yù)測(cè); 假結(jié); 最小自由能; 布谷鳥(niǎo)搜索

中圖分類(lèi)號(hào)： R857.3 文獻(xiàn)標(biāo)識(shí)碼：A

1概述

假結(jié)結(jié)構(gòu)是一類(lèi)二級(jí)結(jié)構(gòu)子結(jié)構(gòu)，在兩個(gè)或多個(gè)莖區(qū)出現(xiàn)交叉嵌套時(shí)形成，存在于多種RNA分子二級(jí)結(jié)構(gòu)中。其中莖區(qū)是一種二級(jí)結(jié)構(gòu)子結(jié)構(gòu)，通過(guò)連續(xù)的三對(duì)或三對(duì)以上堿基配對(duì)形成。研究發(fā)現(xiàn)，假結(jié)結(jié)構(gòu)對(duì)于RNA結(jié)構(gòu)的作用具有重要的意義。

RNA分子結(jié)構(gòu)對(duì)于其作用有重要影響，其測(cè)定可通過(guò)X光測(cè)定、核磁共振成像等物理方法進(jìn)行。但物理方法存在耗時(shí)長(zhǎng)、財(cái)力物力開(kāi)銷(xiāo)大等缺點(diǎn)，限制了其使用。

目前的研究主要通過(guò)軟件計(jì)算方式預(yù)測(cè)RNA二級(jí)結(jié)構(gòu)。早期的RNA結(jié)構(gòu)預(yù)測(cè)算法主要是動(dòng)態(tài)規(guī)劃類(lèi)型算法。這些算法具有不適用于較長(zhǎng)的RNA序列、算法復(fù)雜預(yù)測(cè)計(jì)算耗時(shí)長(zhǎng)等缺點(diǎn)。近期研究熱點(diǎn)轉(zhuǎn)向基于啟發(fā)式算法的預(yù)測(cè)研究。

2 研究現(xiàn)狀

目前主要預(yù)測(cè)算法采用最小自由能量模型作為建模基礎(chǔ)。此模型認(rèn)為在所有可能結(jié)構(gòu)中自由能量最低的預(yù)測(cè)結(jié)構(gòu)最有可能是給定序列的實(shí)際結(jié)構(gòu)。通過(guò)實(shí)驗(yàn)及統(tǒng)計(jì)估算，可以指定出一系列自由能量計(jì)算規(guī)則，以計(jì)算出任何給定結(jié)構(gòu)的自由能量。

目前的主要算法分為動(dòng)態(tài)規(guī)劃和啟發(fā)式兩種。動(dòng)態(tài)規(guī)劃算法能夠在理論上保證搜索到具有全局最小自由能量的結(jié)構(gòu)，但時(shí)間復(fù)雜度高。啟發(fā)式算法收斂速度明顯比動(dòng)態(tài)規(guī)劃算法快，但不能保證得到具有全局最小自由能的結(jié)構(gòu)是其主要缺點(diǎn)。

目前主要的動(dòng)態(tài)規(guī)劃算法包括Reeder和Generics提出的pknotsRG-mfe算法 和Dirks和Pierce提出的NUPACK的算法。pknotsRG-mfe通過(guò)限制假結(jié)類(lèi)型將時(shí)間復(fù)雜度低至 。

Van Batenburg等人通過(guò)引入遺傳算法思想提出名為STAR的啟發(fā)式算法，將問(wèn)題轉(zhuǎn)化為莖區(qū)組合優(yōu)化進(jìn)行搜索。Ren和Rastegari提出名為HotKnots的啟發(fā)式算法，通過(guò)迭代添加可能的子結(jié)構(gòu)建立候選結(jié)構(gòu)。

3 CSRNA算法

布谷鳥(niǎo)搜索算法（Cuckoo Search， CS）是由Yang等于2009年提出的一種啟發(fā)式優(yōu)化算法，用以解決函數(shù)優(yōu)化、最值搜索等問(wèn)題。算法受布谷鳥(niǎo)在其他鳥(niǎo)類(lèi)的巢中下蛋并由他人代為孵化這一繁殖行為啟發(fā)。

3.1 目標(biāo)函數(shù)

CSRNA算法定義RNA結(jié)構(gòu)自由能量函數(shù)作為算法的目標(biāo)函數(shù)，使用最鄰近能量模型進(jìn)行計(jì)算。

一個(gè)結(jié)構(gòu)的自由能通過(guò)將非假結(jié)子結(jié)構(gòu)、H假結(jié)、復(fù)雜假結(jié)三者能量求和得到。

非假結(jié)子結(jié)構(gòu)包含莖區(qū)、發(fā)夾環(huán)、內(nèi)環(huán)、凸環(huán)、多分支環(huán)、懸掛堿基和終端錯(cuò)配等二級(jí)結(jié)構(gòu)子結(jié)構(gòu)。CSRNA采用Mathews小組提出的能量參數(shù)計(jì)算上述子結(jié)構(gòu)的能量。

針對(duì)H型假結(jié)能量，CSRNA引入由Gultyaev和Batenburg、Dirk和Pierce[3]以及Cao和Chen 提出的三組能量參數(shù)進(jìn)行計(jì)算。針對(duì)復(fù)雜假結(jié)能量，CSRNA采用了將其拆分為多個(gè)非假結(jié)結(jié)構(gòu)方式計(jì)算能量。

3.2 初始化處理

初始化處理包括構(gòu)造莖區(qū)池、構(gòu)造初始解并排序兩個(gè)步驟。

首先定義兩個(gè)莖區(qū)兼容指相互不包含重復(fù)的堿基位。

莖區(qū)池是一個(gè)存儲(chǔ)給定RNA序列所有可能存在的莖區(qū)的線性表，表中每個(gè)莖區(qū)被賦予全局唯一的序號(hào)。每個(gè)解都是莖區(qū)池中相互兼容莖區(qū)的組合。

4 實(shí)驗(yàn)結(jié)果

定義TP表示預(yù)測(cè)結(jié)構(gòu)堿基對(duì)中出現(xiàn)在實(shí)際結(jié)構(gòu)中的堿基對(duì)個(gè)數(shù)，F(xiàn)P表示預(yù)測(cè)結(jié)構(gòu)堿基對(duì)中未出現(xiàn)于實(shí)際結(jié)構(gòu)中的堿基對(duì)個(gè)數(shù)，F(xiàn)N表示真實(shí)結(jié)構(gòu)堿基對(duì)中未出現(xiàn)在預(yù)測(cè)結(jié)構(gòu)中的堿基對(duì)的個(gè)數(shù)。

則可定義用于評(píng)價(jià)結(jié)果的敏感性指標(biāo)為T(mén)P除以TP與FN的和，而確定性敏感性指標(biāo)為T(mén)P除以TP與FP的和。

表2 確定性指標(biāo)實(shí)驗(yàn)結(jié)果表

結(jié)語(yǔ)

在本文中，以解決帶假結(jié)RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)問(wèn)題，我們基于布谷鳥(niǎo)搜索提出了一種名為CSRNA的預(yù)測(cè)算法。通過(guò)與目前主要預(yù)測(cè)算法進(jìn)行對(duì)比實(shí)驗(yàn)，證明了CSRNA算法的有用性和有效性。

在后續(xù)研究中，計(jì)劃通過(guò)完善自由能量計(jì)算模型以提高預(yù)測(cè)準(zhǔn)確率。此外，還計(jì)劃針對(duì)構(gòu)造領(lǐng)域解進(jìn)行搜索和按比例淘汰部分解兩項(xiàng)機(jī)制進(jìn)行改造，以加強(qiáng)算法搜索能力，優(yōu)化預(yù)測(cè)結(jié)果。

參考消息

[1] D. H. Turner， D. H . Mathews. NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure[J]. Nucleic Acids Research， 2009， 38:280-282.

[2] J. Reeder， P. Steffen， R. Giegerich. PknotsRG: RNA pseudoknot folding including near-optimal structures and sliding windows. Nucleic Acids Research， 2007， 35(2):320-323.