RNA二级结构点括号图与CT文件表示法的相互转换算法研究

吴建英，王淑琴

（天津师范大学 计算机与信息工程学院，天津300387）

核糖核酸RNA（Ribonucleic Acid，RNA）是由核糖核苷酸经磷酯键缩合而成的长链状分子，A、U、G和C 4种碱基分别代表腺嘌呤（Adenine）、尿嘧啶（Uracil）、鸟嘌呤（Guanine）和胞嘧啶（Cytosine）.RNA分子中的一部分可以与自身碱基互补配对，并折叠形成复杂的二级结构.RNA是生物系统内最为重要的分子之一，它在生物体内行使着多种功能，尤其是在HIV等病毒体中，遗传信息由RNA携带而不是DNA[1].随着人们对RNA研究的不断深入[2－3]，RNA分子的重要性越来越受到人们的重视，特别是发现了RNA分子的催化属性，更加引起了研究者的广泛关注.随着科学技术的飞速发展，研究人员已经获得了大量的RNA一级结构信息.分析RNA二级结构的相似性可以为研究RNA的功能提供重要的信息，因此，RNA二级结构的表示形式对RNA的相关研究具有至关重要的作用，是近年来的研究热点[4－5].为了更好地研究RNA的功能，通常需要大量使用RNA二级结构预测软件，而不同的预测软件获得的二级结构不同，而且很多有关RNA二级结构相似性的研究也基于不同的RNA二级结构表示方法，因此，研究RNA二级结构表示方法之间的转换算法具有非常重要的意义.目前，对RNA二级结构表示法间转换算法的研究相对较少，文献[6]中给出了二级结构平面图到点括号图的转换以及树图和二级结构平面图的转换算法.本研究对RNA二级结构常用的表示方法进行讨论，给出点括号图与二级结构平面图文本表示（即对应的CT文件）之间的相互转换算法，以期对RNA二级结构功能及其相似性研究有所帮助.

1 RNA二级结构及其表示方法

1.1 RNA二级结构及其子结构

RNA分子存在3种结构形态：一级结构（primary structure）、二级结构（secondary structure）和三级结构（tertiary structure）.其中，一级结构可以视为由A（腺嘌呤）、U（尿嘧啶）、G（鸟嘌呤）和C（胞嘧啶）4个字符组成的线性有限字符串.二级结构是RNA分子自身通过碱基互补配对（A与U配对，G与C配对，有时G与U也配对）回折形成局部的茎状结构与未配对的碱基（自由基）交替出现构成的环状结构.二级结构是一级结构向三级结构（空间结构）变换的一种中间状态，具有桥梁性的作用，研究RNA二级结构有助于了解RNA三级结构的功能和特性.RNA二级结构中通常包含堆积、凸包环、内环、多分支环和发夹环等子结构[7].RNA二级结构及其子结构如图1所示.

图1 RNA二级结构及其子结构示意图Fig.1 Representation of RNA secondary structure

RNA二级结构可以由RNA一级序列通过二级结构预测软件获得，常用的RNA二级结构预测软件有 RNAstructure、Pfold（PPfold）、RNAfold、MPGAfold、caRNAc、UNAFold和 Mfold等.这些预测软件基于不同原理，输入和输出的格式有所差别，如RNAstructure输入或载入RNA一级序列，根据最小自由能理论预测二级结构，输出二级结构平面图和CT文件.Pfold的输入是一组比对好的同源RNA序列，然后结合上下文无关法预测一致的RNA二级结构[8].RNAfold和caRNAc同是输入一级序列，输出点括号图同时生成相关联的CT文件及其二级结构平面图.

1.2 RNA二级结构的表示方法

1.2.1 平面图形表示法

目前，RNA二级结构的平面图表示方法很多，如圆顶图、圆圈图、山峰图和折线图等，如图2所示.

图2 RNA二级结构平面图形表示法示意图Fig.2 Representation of RNA secondary structure with ichnography

将RNA的一级序列依次水平放置，如果2个碱基配对就用弧线连接起来，图2a是圆顶图表示法，直线上点表示碱基，弧线连接的2个点表示配对碱基[7]，该图可用于表示RNA二级结构的配对信息，文献[9－10]使用圆顶图表示法计算RNA序列间的相似性.在圆顶图的基础上，将首尾碱基连接起来形成一个圆，将两两配对的碱基在圆的内部用弧线连接，就形成了圆圈图，如图2b所示.

圆顶图和圆圈图表示法直观、简易，但丢失了大量的RNA二级结构及其子结构的信息。图2c是一种比较典型的RNA二级结构表示方法，这种方法直观、大方，配对信息一目了然，各子结构单元也很清楚，一般作为效果图输出。RNAfold和Mfold等RNA二级结构预测软件可以生成此结构图。

目前，大多数RNA二级结构比较算法都采用RNA二级结构的树图表示进行聚类分析和相似性分析。图2d所示的树图表示法采用邻接矩阵的存储方式，对矩阵的一些不变量进行计算、分析，从而比较2个RNA分子的二级结构，文献[11－15]中采用该表示方法对RNA二级结构进行分析，但此树图表示不能表示自然界中普遍存在的假结结构，且不能精确表示出碱基的数目及其各子结构的信息，因此造成部分结构和功能信息的丢失。

1.2.2 点括号图表示

点括号表示法常用于定义RNA二级结构.RNA中的自由基用“.”表示，配对基用一对“（）”表示，“（”表示从5’开始的有配对的碱基，“）”表示与之配对的碱基，如图3所示.

图3 RNA二级结构的点括号图文本格式表示Fig.3 Representation of RNA secondary structure with dot－bracket notation

许多RNA二级结构预测软件都采用点括号图文件格式作为输入（输出）文本，文献[14]采用此种格式表示RNA二级结构作为文件输入，提出了一种新的压缩算法.

1.2.3 CT文件表示

CT文件格式最早由ZuKer[15]提出，用于定义RNA二级结构和核苷酸序列，包含单个序列的多个子结构信息.在CT文件中，首行中整数N表示核苷酸序列的总长度，N后面是预测二级结构得到的自由能和RNA分子的描述信息.图2c中RNA二级结构对应的CT文件表示如图4所示.CT文件中包含6列数据：第1列为索引信息；第2列表示RNA二级结构中从5’端开始到3’端结束的碱基（A、U、G和C）；第3列是与之相邻的前一个碱基的编号；第4列是与之相邻的后1个碱基的编号；第5列表示是否存在与这个碱基配对的碱基，‘0’表示无配对碱基，非‘0’表示存在配对碱基，且用数字n表示与配对的碱基编号；第6列同第1列.

图4 RNA二级结构CT文件表示法Fig.4 Representation of RNA secondary structure with ichnography and its CT file（part）

CT文件可以由RNA二级结构预测软件得到，被用于计算RNA之间的相似性及预测其类别，文献[13－16]用到的CT文件由 Mfold软件生成，RAGdatabase提供在线将CT文件转换成树图.

2 转换算法

2.1 点括号图到平面图文本表示法的转换

输入：一级序列和对应的点括号图的文本文件.

输出：RNA二级结构平面图对应的CT文件.

转换算法的具体描述：

该算法的基本思想是首先读取点括号文件，将以‘＞’符号开头的一行赋值给str1，作为CT文件每个RNA分子的首行输出，将读入的碱基行赋值给str2，点括号一行赋值给str3；然后调用write_CT _file函数，在此函数体内对str3字符串所含字符进行判断处理；最后按照CT文件的格式一一输出.算法的时间复杂度为O（n），空间复杂度为O（3n）.

2.2 平面图文本表示法到点括号图的转换

输入：RNA二级结构平面图对应的CT文件.

输出：一级序列及字符串S，Si∈｛‘.’，‘（’，‘）’｝即点括号图表示.

转换算法的具体描述：

该算法的基本思想是读入CT文件，将每个RNA分子首行的描述信息作为点括号图文件的首行输出，读取CT文件的第1列、第2列和第5列数据信息，主要根据第5列信息判断输出‘.’、‘（’和‘）’中的哪一个字符.时间复杂度为O（5n），空间复杂度为O（5n）.

2.3 实例分析

以点括号图到CT文件转换为例，运行本研究所设计的转换程序，界面如图5所示.

图5 程序运行界面Fig.5 Program running interface

单击“选择文件”，选择相应的点括号图文件，如图6所示，再点击“生成CT文件”，便生成如图7所示的CT文件.

图6 一级序列和对应的点括号图的文本文件Fig.6 Primary structure and its dot－bracket notation

图7 RNA二级结构平面图对应的CT文件Fig.7 RNA secondary structure with its CT file

此结果与用RNAstructure得出的结果一致，说明本研究设计的转换算法准确、有效.由于RNAstructure只能转换单个的文件，本研究算法可以进行批处理，因此，与RNAstructure相比，本算法提高了转换效率.CT文件到点括号图转换同理，不再赘述.

3 结束语

本研究介绍了RNA二级结构的各种表示方法，给出了其中点括号图与平面图文本表示法（即对应的CT文件）之间的相互转换算法.通过实例证明该转换算法准确、有效，可以应用于比对RNA二级结构相似性的研究领域，进而为更好地研究RNA功能提供一种处理数据的方法.

[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二级结构表示方法及其转换算法[J].计算机工程与应用，2004，14（3）：43－45.

[7]邹权，郭茂祖，张涛涛.RNA二级结构预测方法综述[J].电子学报，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，FERA D，ZORN J，et al.RAG：RNA A－graphs database concepts，analysis，and features[J].Bioinformatics，2004，20（8）：1285－1291.

[14]周文彦，曹槐.图论在RNA二级结构中的应用[J].生物信息学，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.