RNA二級結(jié)構(gòu)點(diǎn)括號圖與CT文件表示法的相互轉(zhuǎn)換算法研究

吳建英，王淑琴

（天津師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，天津300387）

核糖核酸RNA（Ribonucleic Acid，RNA）是由核糖核苷酸經(jīng)磷酯鍵縮合而成的長鏈狀分子，A、U、G和C 4種堿基分別代表腺嘌呤（Adenine）、尿嘧啶（Uracil）、鳥嘌呤（Guanine）和胞嘧啶（Cytosine）.RNA分子中的一部分可以與自身堿基互補(bǔ)配對，并折疊形成復(fù)雜的二級結(jié)構(gòu).RNA是生物系統(tǒng)內(nèi)最為重要的分子之一，它在生物體內(nèi)行使著多種功能，尤其是在HIV等病毒體中，遺傳信息由RNA攜帶而不是DNA[1].隨著人們對RNA研究的不斷深入[2－3]，RNA分子的重要性越來越受到人們的重視，特別是發(fā)現(xiàn)了RNA分子的催化屬性，更加引起了研究者的廣泛關(guān)注.隨著科學(xué)技術(shù)的飛速發(fā)展，研究人員已經(jīng)獲得了大量的RNA一級結(jié)構(gòu)信息.分析RNA二級結(jié)構(gòu)的相似性可以為研究RNA的功能提供重要的信息，因此，RNA二級結(jié)構(gòu)的表示形式對RNA的相關(guān)研究具有至關(guān)重要的作用，是近年來的研究熱點(diǎn)[4－5].為了更好地研究RNA的功能，通常需要大量使用RNA二級結(jié)構(gòu)預(yù)測軟件，而不同的預(yù)測軟件獲得的二級結(jié)構(gòu)不同，而且很多有關(guān)RNA二級結(jié)構(gòu)相似性的研究也基于不同的RNA二級結(jié)構(gòu)表示方法，因此，研究RNA二級結(jié)構(gòu)表示方法之間的轉(zhuǎn)換算法具有非常重要的意義.目前，對RNA二級結(jié)構(gòu)表示法間轉(zhuǎn)換算法的研究相對較少，文獻(xiàn)[6]中給出了二級結(jié)構(gòu)平面圖到點(diǎn)括號圖的轉(zhuǎn)換以及樹圖和二級結(jié)構(gòu)平面圖的轉(zhuǎn)換算法.本研究對RNA二級結(jié)構(gòu)常用的表示方法進(jìn)行討論，給出點(diǎn)括號圖與二級結(jié)構(gòu)平面圖文本表示（即對應(yīng)的CT文件）之間的相互轉(zhuǎn)換算法，以期對RNA二級結(jié)構(gòu)功能及其相似性研究有所幫助.

1 RNA二級結(jié)構(gòu)及其表示方法

1.1 RNA二級結(jié)構(gòu)及其子結(jié)構(gòu)

RNA分子存在3種結(jié)構(gòu)形態(tài)：一級結(jié)構(gòu)（primary structure）、二級結(jié)構(gòu)（secondary structure）和三級結(jié)構(gòu)（tertiary structure）.其中，一級結(jié)構(gòu)可以視為由A（腺嘌呤）、U（尿嘧啶）、G（鳥嘌呤）和C（胞嘧啶）4個(gè)字符組成的線性有限字符串.二級結(jié)構(gòu)是RNA分子自身通過堿基互補(bǔ)配對（A與U配對，G與C配對，有時(shí)G與U也配對）回折形成局部的莖狀結(jié)構(gòu)與未配對的堿基（自由基）交替出現(xiàn)構(gòu)成的環(huán)狀結(jié)構(gòu).二級結(jié)構(gòu)是一級結(jié)構(gòu)向三級結(jié)構(gòu)（空間結(jié)構(gòu)）變換的一種中間狀態(tài)，具有橋梁性的作用，研究RNA二級結(jié)構(gòu)有助于了解RNA三級結(jié)構(gòu)的功能和特性.RNA二級結(jié)構(gòu)中通常包含堆積、凸包環(huán)、內(nèi)環(huán)、多分支環(huán)和發(fā)夾環(huán)等子結(jié)構(gòu)[7].RNA二級結(jié)構(gòu)及其子結(jié)構(gòu)如圖1所示.

圖1 RNA二級結(jié)構(gòu)及其子結(jié)構(gòu)示意圖Fig.1 Representation of RNA secondary structure

RNA二級結(jié)構(gòu)可以由RNA一級序列通過二級結(jié)構(gòu)預(yù)測軟件獲得，常用的RNA二級結(jié)構(gòu)預(yù)測軟件有 RNAstructure、Pfold（PPfold）、RNAfold、MPGAfold、caRNAc、UNAFold和 Mfold等.這些預(yù)測軟件基于不同原理，輸入和輸出的格式有所差別，如RNAstructure輸入或載入RNA一級序列，根據(jù)最小自由能理論預(yù)測二級結(jié)構(gòu)，輸出二級結(jié)構(gòu)平面圖和CT文件.Pfold的輸入是一組比對好的同源RNA序列，然后結(jié)合上下文無關(guān)法預(yù)測一致的RNA二級結(jié)構(gòu)[8].RNAfold和caRNAc同是輸入一級序列，輸出點(diǎn)括號圖同時(shí)生成相關(guān)聯(lián)的CT文件及其二級結(jié)構(gòu)平面圖.

1.2 RNA二級結(jié)構(gòu)的表示方法

1.2.1 平面圖形表示法

目前，RNA二級結(jié)構(gòu)的平面圖表示方法很多，如圓頂圖、圓圈圖、山峰圖和折線圖等，如圖2所示.

圖2 RNA二級結(jié)構(gòu)平面圖形表示法示意圖Fig.2 Representation of RNA secondary structure with ichnography

將RNA的一級序列依次水平放置，如果2個(gè)堿基配對就用弧線連接起來，圖2a是圓頂圖表示法，直線上點(diǎn)表示堿基，弧線連接的2個(gè)點(diǎn)表示配對堿基[7]，該圖可用于表示RNA二級結(jié)構(gòu)的配對信息，文獻(xiàn)[9－10]使用圓頂圖表示法計(jì)算RNA序列間的相似性.在圓頂圖的基礎(chǔ)上，將首尾堿基連接起來形成一個(gè)圓，將兩兩配對的堿基在圓的內(nèi)部用弧線連接，就形成了圓圈圖，如圖2b所示.

圓頂圖和圓圈圖表示法直觀、簡易，但丟失了大量的RNA二級結(jié)構(gòu)及其子結(jié)構(gòu)的信息。圖2c是一種比較典型的RNA二級結(jié)構(gòu)表示方法，這種方法直觀、大方，配對信息一目了然，各子結(jié)構(gòu)單元也很清楚，一般作為效果圖輸出。RNAfold和Mfold等RNA二級結(jié)構(gòu)預(yù)測軟件可以生成此結(jié)構(gòu)圖。

目前，大多數(shù)RNA二級結(jié)構(gòu)比較算法都采用RNA二級結(jié)構(gòu)的樹圖表示進(jìn)行聚類分析和相似性分析。圖2d所示的樹圖表示法采用鄰接矩陣的存儲方式，對矩陣的一些不變量進(jìn)行計(jì)算、分析，從而比較2個(gè)RNA分子的二級結(jié)構(gòu)，文獻(xiàn)[11－15]中采用該表示方法對RNA二級結(jié)構(gòu)進(jìn)行分析，但此樹圖表示不能表示自然界中普遍存在的假結(jié)結(jié)構(gòu)，且不能精確表示出堿基的數(shù)目及其各子結(jié)構(gòu)的信息，因此造成部分結(jié)構(gòu)和功能信息的丟失。

1.2.2 點(diǎn)括號圖表示

點(diǎn)括號表示法常用于定義RNA二級結(jié)構(gòu).RNA中的自由基用“.”表示，配對基用一對“（）”表示，“（”表示從5’開始的有配對的堿基，“）”表示與之配對的堿基，如圖3所示.

圖3 RNA二級結(jié)構(gòu)的點(diǎn)括號圖文本格式表示Fig.3 Representation of RNA secondary structure with dot－bracket notation

許多RNA二級結(jié)構(gòu)預(yù)測軟件都采用點(diǎn)括號圖文件格式作為輸入（輸出）文本，文獻(xiàn)[14]采用此種格式表示RNA二級結(jié)構(gòu)作為文件輸入，提出了一種新的壓縮算法.

1.2.3 CT文件表示

CT文件格式最早由ZuKer[15]提出，用于定義RNA二級結(jié)構(gòu)和核苷酸序列，包含單個(gè)序列的多個(gè)子結(jié)構(gòu)信息.在CT文件中，首行中整數(shù)N表示核苷酸序列的總長度，N后面是預(yù)測二級結(jié)構(gòu)得到的自由能和RNA分子的描述信息.圖2c中RNA二級結(jié)構(gòu)對應(yīng)的CT文件表示如圖4所示.CT文件中包含6列數(shù)據(jù)：第1列為索引信息；第2列表示RNA二級結(jié)構(gòu)中從5’端開始到3’端結(jié)束的堿基（A、U、G和C）；第3列是與之相鄰的前一個(gè)堿基的編號；第4列是與之相鄰的后1個(gè)堿基的編號；第5列表示是否存在與這個(gè)堿基配對的堿基，‘0’表示無配對堿基，非‘0’表示存在配對堿基，且用數(shù)字n表示與配對的堿基編號；第6列同第1列.

圖4 RNA二級結(jié)構(gòu)CT文件表示法Fig.4 Representation of RNA secondary structure with ichnography and its CT file（part）

CT文件可以由RNA二級結(jié)構(gòu)預(yù)測軟件得到，被用于計(jì)算RNA之間的相似性及預(yù)測其類別，文獻(xiàn)[13－16]用到的CT文件由 Mfold軟件生成，RAGdatabase提供在線將CT文件轉(zhuǎn)換成樹圖.

2 轉(zhuǎn)換算法

2.1 點(diǎn)括號圖到平面圖文本表示法的轉(zhuǎn)換

輸入：一級序列和對應(yīng)的點(diǎn)括號圖的文本文件.

輸出：RNA二級結(jié)構(gòu)平面圖對應(yīng)的CT文件.

轉(zhuǎn)換算法的具體描述：

該算法的基本思想是首先讀取點(diǎn)括號文件，將以‘＞’符號開頭的一行賦值給str1，作為CT文件每個(gè)RNA分子的首行輸出，將讀入的堿基行賦值給str2，點(diǎn)括號一行賦值給str3；然后調(diào)用write_CT _file函數(shù)，在此函數(shù)體內(nèi)對str3字符串所含字符進(jìn)行判斷處理；最后按照CT文件的格式一一輸出.算法的時(shí)間復(fù)雜度為O（n），空間復(fù)雜度為O（3n）.

2.2 平面圖文本表示法到點(diǎn)括號圖的轉(zhuǎn)換

輸入：RNA二級結(jié)構(gòu)平面圖對應(yīng)的CT文件.

輸出：一級序列及字符串S，Si∈｛‘.’，‘（’，‘）’｝即點(diǎn)括號圖表示.

轉(zhuǎn)換算法的具體描述：

該算法的基本思想是讀入CT文件，將每個(gè)RNA分子首行的描述信息作為點(diǎn)括號圖文件的首行輸出，讀取CT文件的第1列、第2列和第5列數(shù)據(jù)信息，主要根據(jù)第5列信息判斷輸出‘.’、‘（’和‘）’中的哪一個(gè)字符.時(shí)間復(fù)雜度為O（5n），空間復(fù)雜度為O（5n）.

2.3 實(shí)例分析

以點(diǎn)括號圖到CT文件轉(zhuǎn)換為例，運(yùn)行本研究所設(shè)計(jì)的轉(zhuǎn)換程序，界面如圖5所示.

圖5 程序運(yùn)行界面Fig.5 Program running interface

單擊“選擇文件”，選擇相應(yīng)的點(diǎn)括號圖文件，如圖6所示，再點(diǎn)擊“生成CT文件”，便生成如圖7所示的CT文件.

圖6 一級序列和對應(yīng)的點(diǎn)括號圖的文本文件Fig.6 Primary structure and its dot－bracket notation

圖7 RNA二級結(jié)構(gòu)平面圖對應(yīng)的CT文件Fig.7 RNA secondary structure with its CT file

此結(jié)果與用RNAstructure得出的結(jié)果一致，說明本研究設(shè)計(jì)的轉(zhuǎn)換算法準(zhǔn)確、有效.由于RNAstructure只能轉(zhuǎn)換單個(gè)的文件，本研究算法可以進(jìn)行批處理，因此，與RNAstructure相比，本算法提高了轉(zhuǎn)換效率.CT文件到點(diǎn)括號圖轉(zhuǎn)換同理，不再贅述.

3 結(jié)束語

本研究介紹了RNA二級結(jié)構(gòu)的各種表示方法，給出了其中點(diǎn)括號圖與平面圖文本表示法（即對應(yīng)的CT文件）之間的相互轉(zhuǎn)換算法.通過實(shí)例證明該轉(zhuǎn)換算法準(zhǔn)確、有效，可以應(yīng)用于比對RNA二級結(jié)構(gòu)相似性的研究領(lǐng)域，進(jìn)而為更好地研究RNA功能提供一種處理數(shù)據(jù)的方法.

[1]MA B，WANG L S，ZHANG K Z.Computing similarity between RNA structures[J].Theoretical Computer Science，2002，276：111－132.

[2]SHAPIRO B，ZHANG K.Comparing multiple RNA secondary structures using tree comparisons[J].Computer Applications in the Biosciences，1990，6：309－318.

[3]BAI F L，ZHU W，WANG T M.Analysis of similarity between RNA secondary structures[J].Chemical Physics Letters，2005，408（6）：258－263.

[4]YAO Y H，LIAO B，WANG T M.A 2Dgraphical representation of RNA secondary structures and the analysis of similarity／dissimilarity based on it[J].Journal of Molecular Structure：Theochem，2005，755：131－136.

[5]LIAO B，WANG T M.A 3Dgaphical representation of RNA secondary structures[J].J Biomol Struct Dynamics，2004，21：827－832.

[6]付微，黃競偉，徐麗.RNA二級結(jié)構(gòu)表示方法及其轉(zhuǎn)換算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，14（3）：43－45.

[7]鄒權(quán)，郭茂祖，張濤濤.RNA二級結(jié)構(gòu)預(yù)測方法綜述[J].電子學(xué)報(bào)，2008，36（2）：331－337.

[8]JIANG T，LIN G H，MA B，et al.The longest common subsequence problem for sequences with nested arc nanotations[J].Journal of Computer and System Sciences，2002，65：465－480.

[9]ALBER J，GRAMM J，GUO J，et al.Computing the similarity of two sequences with nested arc annotations[J].Theoretical Computer Science，2004，312（2／3）：337－358.

[10]JIN E Y，QIN J，REIDYS C M.Combinatorics of RNA structures with pseudoknots[J].Bull Math Biol，2008，70（1）：45－67.

[11]LIU Q，YANG Y，CHEN C，et al.RNA compress：Grammar－based compression and informational complexity measurement of RNA secondary structure[J].BMC Bioinformatics，2008，9（176）：1471－2105.

[12]MARKHAM N R，ZUKER M.Software for nucleic acid folding and hybridization[J].Methods in Molecular Biology，2008，453：3－31.

[13]GAN H H，F(xiàn)ERA D，ZORN J，et al.RAG：RNA A－graphs database concepts，analysis，and features[J].Bioinformatics，2004，20（8）：1285－1291.

[14]周文彥，曹槐.圖論在RNA二級結(jié)構(gòu)中的應(yīng)用[J].生物信息學(xué)，2008，6（3）：138－141.

[15]ZUKER M，JAEGER J，TURNER D.A comparison of optimal and suboptimal RNA secondary structures pridicted by free energy minimization with structures determined by phylogenetic comparison[J].Nucleic Acids Res，1991，19（10）：2707－2714.

[16]FERA D，KIM N，SHIFFELDRIM N，et al.RAG：RNA－asgraphs web resource[J].BMC Bioinformatics，2004，88（5）：471－2105.