含假结RNA二级结构图的语法及拓扑分类
|
摘要
RNA的生物学功能很大程度上决定于其三维空间结构。空间结构一般通过X射线晶体衍射和核磁共振等实验方法获得,但是实验方法技术难度高、耗资大且并非总是可行。因此理论预测RNA空间结构就非常必要,它可以提高认识RNA空间结构的效率,还可以指引实验研究的方向。
RNA二级结构预测是其空间结构预测的关键。目前,最小自由能法是预测RNA二级结构最主要的方法,但二级结构内部假结的存在使得该方法是NP完全的,这类方法只能考虑具有一定结构特征的假结,从而将时间复杂度控制在多项式范围内。视结构特征的不同,复杂度从O(n~3)到O(n~6)不等,复杂度越高能预测的目标集也越广,目前不存在速度快、目标集广的“好”方法。本文以时间复杂度为O(n~6)的Rivas与Eddy算法的目标集(R&E类)为全集,从文法和语言的角度提出了R&E类及其子类的弧图语法,并从拓扑学的角度将其分类,具体内容包括:
1.提出了弧图语法概念。RNA二级结构弧图是一种特殊的二级结构图,从最简单的弧图开始,按照一定的替换规则对弧图的小部件用较大的部件替换,从而得到一个弧图类。那些体现结构特征的最简单的弧图称为初始弧图,那些替换规则称为重写规则,初始弧图和重写规则两类要素构成弧图语法。给定弧图语法就决定着一个弧图类,该类称为弧图语言。弧图语法提供了一种把数量无限的弧图映射成为数量有限的语法要素的研究方法,且具有易扩展性。
2.给出了5个二级结构算法类的弧图语法。本文首先设计出R&E类的弧图语法,以R&E类弧图语法的要素为全集,给出其自小至大的子集PKF类、L&P类、D&P类、A&U类的弧图语法,这几个类间具有真包含关系,这种关系直观地从他们的弧图语法要素中体现出来。通过研究这5个二级结构类间的关系以及代表元素使全面掌握各类的内容成为可能。
3.得到了平面R&E弧图的语法判据。直观地以平面图的形式展示二级结构有着很广泛的需求,本文在他人研究的基础上在更大范围——R&E类内给出基于弧图语法的判别依据,同时给出了平面嵌入算法。通过可平面R&E类的弧图语法,在R&E类内部完全解决了可平面弧图的平面嵌入问题。在R&E类外部也进行了初步的探索,得到一些有益的例证。
4.实现了R&E弧图的书嵌入分类。RNA二级结构图的书嵌入自1999年提出以来由于其高时间复杂性(NP完全)而一直停留在概念上。本文以R&E类的弧图语法为基础,以弧图的交叉关系图为桥梁,最终通过交叉关系图的极大团覆盖求出任意R&E煌嫉氖榍度胧⒏銮度敕桨?将传统意义上的NP完全问题在R&E类上用多项式时间加以解决。
5.改进了计算R&E弧图亏格的方法。本文基于R&E类的弧图语法,提出弧图亏格计算的动态快速算法,该方法把二级结构图的有向闭曲面分类法中计算亏格的时间复杂度由线性提高到常数,在枚举小亏格弧图和计算多个相似二级结构弧图的亏格上具有较大优势。
The functions of RNA moleculars in biology are mostly determined by its three-dimensional structure, which can be observed by experimental methods such as X-ray crystallography and nuclear magnetic resonance spectroscopy. However, experimental investigations often suffer from the challenge in technique, cost, and other difficulties. Therefore, theoretically predicting the space structure of RNA molecular becomes very necessary, which can improve the efficiency to realize the RNA space structures, guide the experiemtmal investigation.
The secondary structure of RNA molecular is the key to predict its space structure. Up to now, minimization free energy (MFE) method is the most conventional for RNA secondary structure prediction. However, finding the MFE structure for a given RNA molecular is NP-complete for the pseudoknots which exist in RNA secondary structures, MFE methods can only control the time complexity in the polynomial level for some special kinds of pseudoknots. The time complexity, which is related to different special kinds of pseudonots, is from O(n~3) to O(n~6). The algorithms with higher time complexity can predict general target, and there do not exist a "good" algorithms with lower time complexity and general target so far. In this paper, we introduce grammars and topological classifications of Rivas and Eddy algorithm class (R&E class) based on linguistics and topology. This thesis includes:
1. The concept of the grammar of arc graphs is proposed. At first, arc graph is a graph which illustrates RNA secondary structure, where the information about the nested and crossed base pairs is preserved but that of the unpaired bases is deleted. A small part of an arc graph is replaced by a larger one according to the replacement rule and a larger arc graph is obtained. These processes are continued and a class of arc graphs can be achieved. These simplest arc graphs which embody the structure characteristics are called initial arc graphs. These replacement rules are called rewriting rules. The grammar of arc graphs includes both initial arc graphs and rewriting rules. The arc graphs determined by a given grammar are called languages of arc graphs. The grammar of arc graphs provides a new method to map infinite arc graphs to finite grammar elements. The grammar of arc graphs can be easily extended to define new classes of RNA secondary structures.
2. Arc graph grammars of 5 typical RNA secondary prediction algorithms classes are given. In this paper, R&E grammar is defined firstly. Taking the grammar elements of R&E as the whole class, the grammars of PKF, L&P, D&P, A&U classes are defined. Proper inclusive relations are existed between these classes. It is exhibited distinctly through the inclusive relations of the grammar elements. It is possible to grasp the content of these 5 secondary structure prediction algorithm classes through the relations among these classes and the typical elements of these classes.
3. Planarity criterion of R&E arc graph is obtained. It is widely required to show RNA secondary structures as a planar. The planar graphical criterion and embedding algorithms are given based on the R&E grammar. The result of this thesis is more general than the previous works. The book embedding and the book embedding number calculation are solved completely in R&E class through the R&E grammar. Some examples are exhibited outside R&E class along with the basic exploring in this area.
4. Book embedding classification of R&E arc graph is realized. Book embedding of arc graph is just a concept since it was proposed in 1999 because of its high time complexity (NP-complete). In this thesis, based on the grammar of R&E arc graph, Taking the cross relation graph of an arc graph as a bridge, the book embedding number of any arc graph is calculated through the maximum clique covering. At the same time, the book embedding number is obtained. A traditional NP-complete problem is solved with a polynomial time in R&E class.
5. The method for calculating the genus of R&E arc graph is improved. Based on the grammar of R&E arc graphs, a rapid dynamic algorithm for calculating the genus of R&E arc graph is introduced. The time complexity of calculating the genus, the classification standard of directed closed sphere for RNA secondary structures, is improved from linear to constant. This algorithm can be applied to enumerate all arc graphs with small genus and calculating genus of a series of similar arc graphs. It is super to old algorithm in these two aspects.
RNA二级结构预测是其空间结构预测的关键。目前,最小自由能法是预测RNA二级结构最主要的方法,但二级结构内部假结的存在使得该方法是NP完全的,这类方法只能考虑具有一定结构特征的假结,从而将时间复杂度控制在多项式范围内。视结构特征的不同,复杂度从O(n~3)到O(n~6)不等,复杂度越高能预测的目标集也越广,目前不存在速度快、目标集广的“好”方法。本文以时间复杂度为O(n~6)的Rivas与Eddy算法的目标集(R&E类)为全集,从文法和语言的角度提出了R&E类及其子类的弧图语法,并从拓扑学的角度将其分类,具体内容包括:
1.提出了弧图语法概念。RNA二级结构弧图是一种特殊的二级结构图,从最简单的弧图开始,按照一定的替换规则对弧图的小部件用较大的部件替换,从而得到一个弧图类。那些体现结构特征的最简单的弧图称为初始弧图,那些替换规则称为重写规则,初始弧图和重写规则两类要素构成弧图语法。给定弧图语法就决定着一个弧图类,该类称为弧图语言。弧图语法提供了一种把数量无限的弧图映射成为数量有限的语法要素的研究方法,且具有易扩展性。
2.给出了5个二级结构算法类的弧图语法。本文首先设计出R&E类的弧图语法,以R&E类弧图语法的要素为全集,给出其自小至大的子集PKF类、L&P类、D&P类、A&U类的弧图语法,这几个类间具有真包含关系,这种关系直观地从他们的弧图语法要素中体现出来。通过研究这5个二级结构类间的关系以及代表元素使全面掌握各类的内容成为可能。
3.得到了平面R&E弧图的语法判据。直观地以平面图的形式展示二级结构有着很广泛的需求,本文在他人研究的基础上在更大范围——R&E类内给出基于弧图语法的判别依据,同时给出了平面嵌入算法。通过可平面R&E类的弧图语法,在R&E类内部完全解决了可平面弧图的平面嵌入问题。在R&E类外部也进行了初步的探索,得到一些有益的例证。
4.实现了R&E弧图的书嵌入分类。RNA二级结构图的书嵌入自1999年提出以来由于其高时间复杂性(NP完全)而一直停留在概念上。本文以R&E类的弧图语法为基础,以弧图的交叉关系图为桥梁,最终通过交叉关系图的极大团覆盖求出任意R&E煌嫉氖榍度胧⒏銮度敕桨?将传统意义上的NP完全问题在R&E类上用多项式时间加以解决。
5.改进了计算R&E弧图亏格的方法。本文基于R&E类的弧图语法,提出弧图亏格计算的动态快速算法,该方法把二级结构图的有向闭曲面分类法中计算亏格的时间复杂度由线性提高到常数,在枚举小亏格弧图和计算多个相似二级结构弧图的亏格上具有较大优势。
The functions of RNA moleculars in biology are mostly determined by its three-dimensional structure, which can be observed by experimental methods such as X-ray crystallography and nuclear magnetic resonance spectroscopy. However, experimental investigations often suffer from the challenge in technique, cost, and other difficulties. Therefore, theoretically predicting the space structure of RNA molecular becomes very necessary, which can improve the efficiency to realize the RNA space structures, guide the experiemtmal investigation.
The secondary structure of RNA molecular is the key to predict its space structure. Up to now, minimization free energy (MFE) method is the most conventional for RNA secondary structure prediction. However, finding the MFE structure for a given RNA molecular is NP-complete for the pseudoknots which exist in RNA secondary structures, MFE methods can only control the time complexity in the polynomial level for some special kinds of pseudoknots. The time complexity, which is related to different special kinds of pseudonots, is from O(n~3) to O(n~6). The algorithms with higher time complexity can predict general target, and there do not exist a "good" algorithms with lower time complexity and general target so far. In this paper, we introduce grammars and topological classifications of Rivas and Eddy algorithm class (R&E class) based on linguistics and topology. This thesis includes:
1. The concept of the grammar of arc graphs is proposed. At first, arc graph is a graph which illustrates RNA secondary structure, where the information about the nested and crossed base pairs is preserved but that of the unpaired bases is deleted. A small part of an arc graph is replaced by a larger one according to the replacement rule and a larger arc graph is obtained. These processes are continued and a class of arc graphs can be achieved. These simplest arc graphs which embody the structure characteristics are called initial arc graphs. These replacement rules are called rewriting rules. The grammar of arc graphs includes both initial arc graphs and rewriting rules. The arc graphs determined by a given grammar are called languages of arc graphs. The grammar of arc graphs provides a new method to map infinite arc graphs to finite grammar elements. The grammar of arc graphs can be easily extended to define new classes of RNA secondary structures.
2. Arc graph grammars of 5 typical RNA secondary prediction algorithms classes are given. In this paper, R&E grammar is defined firstly. Taking the grammar elements of R&E as the whole class, the grammars of PKF, L&P, D&P, A&U classes are defined. Proper inclusive relations are existed between these classes. It is exhibited distinctly through the inclusive relations of the grammar elements. It is possible to grasp the content of these 5 secondary structure prediction algorithm classes through the relations among these classes and the typical elements of these classes.
3. Planarity criterion of R&E arc graph is obtained. It is widely required to show RNA secondary structures as a planar. The planar graphical criterion and embedding algorithms are given based on the R&E grammar. The result of this thesis is more general than the previous works. The book embedding and the book embedding number calculation are solved completely in R&E class through the R&E grammar. Some examples are exhibited outside R&E class along with the basic exploring in this area.
4. Book embedding classification of R&E arc graph is realized. Book embedding of arc graph is just a concept since it was proposed in 1999 because of its high time complexity (NP-complete). In this thesis, based on the grammar of R&E arc graph, Taking the cross relation graph of an arc graph as a bridge, the book embedding number of any arc graph is calculated through the maximum clique covering. At the same time, the book embedding number is obtained. A traditional NP-complete problem is solved with a polynomial time in R&E class.
5. The method for calculating the genus of R&E arc graph is improved. Based on the grammar of R&E arc graphs, a rapid dynamic algorithm for calculating the genus of R&E arc graph is introduced. The time complexity of calculating the genus, the classification standard of directed closed sphere for RNA secondary structures, is improved from linear to constant. This algorithm can be applied to enumerate all arc graphs with small genus and calculating genus of a series of similar arc graphs. It is super to old algorithm in these two aspects.
引文
[1]吴庆余编著.基础生命科学(第二版).北京:高等教育出版社,2006.
[2]琼斯 N C,帕夫纳 P A著.王翼飞等译.生物信息学算法导论.北京:化学工业出版社,2007.
[3]塞图宝 J,梅丹尼斯 J著.朱浩译.计算分子生物学导论.北京:科学出版社,2003.
[4]金由辛编著.核糖核酸与核糖核酸组学.北京:科学出版社,2005.
[5]Dennis C.The brave new world of RNA.Nature.2002,418(6894):122-124.
[6]刘永明主编.分子生物学简明教程.北京:化学工业出版社,2006.
[7]刘次全,曹恩华,白春礼等著.核酸结构多态性.北京:高等教育出版社,2000.
[8]金由辛.面向21世纪的RNA研究.自然科学进展,2000,10(7):600-606.
[9]梁毅主编.结构生物学.北京:科学出版社,2005.
[10]刘次全.白春礼,张静著.结构分子生物学.北京:高等教育出版社,1997.
[11]Karp G.Cell and Molecular Biology.John Wiley & Sons Inc,2002.
[12]卡普著.王喜忠,丁明孝,张传茂等译.分子细胞生物学,北京:高等教育出版社,2005.
[13]王传铭,潘珉,曹槐.RNA折叠.自然杂志,2004,26(5):249-254.
[14]Mathews D H,Turner D H.Prediction of RNA secondary structure by free energy minimization,Current Opinion in Structural Biology.2006,16(3):270-278.
[15]Zuker M,Stiegler P.Optimal computer folding of larger RNA sequences using thermodynamics and auxiliary information.Nucleic Acids Research.1981,9(1):133-148.
[16]Nussinov R,Pieczenik G,Griggs J,et al.Algorithms for loop matchings.SIAM Journal on Applied Mathematics.1978,35:68-82.
[17]Ieong S,Kao M-Y,Lam T-W,et al.Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs.Journal of Computational Biology.2003,10(6):981-995.
[18]Dirks R M,Pierce N A.partition function algorithm for nucleic acid secondary structure including pseudoknots.Journal of computational Chemistry.2003,24(13):1664-1677.
[19]王翼飞,史定华主编.生物信息学:智能化算法及其应用.北京:化学工业出版社,2006.
[20]Voss B.Structural analysis of aligned RNAs.Nucleic Acids Research.2006,34(19):5471-5481.
[21]Bindewald E,Shapiro B A.RNA secondary structure prediction from sequence alignments using a network of k-nearest neighbor classifiers.RNA-a Publication of the RNA Society.2006,12(3):342-352.
[22]刘琦,张引,叶修梓等.基于奇异值分解的RNA级结构相似度计算方法.浙江大学学报(工学版),2007,41(8):1249-1255.
[23]Le S Y,Nussinov R,Maizel J V.Tree graphs of RNA secondary structures and their comparisons.Computers and Biomedical Research.1989,22(5):461-473.
[24]Zuker M.Mfold web server for nucleic acid folding and hybridization prediction.Nucleic Acids Research.2003,31(13):3406-3415.
[25]Hofacker I L.Vienna RNA secondary structure server.Nucleic Acids Research.2003,31(13):3429-3431.
[26]Waterman M S,Smith T F.Rapid dynamic programming algorithms for RNA secondary structure.Advances in applied mathematics.1986,7(4):455-464.
[27]Rivas E.Eddy S R.A dynamic programming algorithm for RNA structure prediction including pseudoknots.Journal of Molecular Biology.1999,285(5):2053-2068.
[28]Rivas E,Eddy S R.The language of RNA:a formal grammar that includes pseudoknots.Bioinformatics.2000,16(4):334-340.
[29]Condon A,Davy B,Rastegari B,et al.Classifying RNA pseudoknotted structures.Theoretical Computer Science.2004,320(1):35-50.
[30]van Batenburg F H D,Gultyaev A P,Pleij C W A,et al.Pseudobase:a database with RNA pseudoknots.Nucleic Acids Research.2000,28(1):201-204.
[31]van Batenburg F H D,Gultyaev A P,Pleij C W A.PseudoBase:structural information on RNA pseudoknots.Nucleic Acids Research.2001,29(1):194-195.
[32]Cannone J J,Subramanian S,Schnare M N,et al.The comparative RNA web(CRW)site:an online database of comparative sequence and structure information for ribosomal,intron,and other RNAs.BMC Bioinformatics.2002,3:15.
[33]Akutsu,T.Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots.Discrete Applied Mathematics.2000,104(1-3):45-62.
[34]Akutsu T.Recent advances in RNA secondary structure prediction with pseudoknots.Current Bioinformatics.2006,1(2):115-129.
[35]Dirks R M,Pierce N A.An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots.Journal of Computational Chemistry.2004,25(10):1295-1304.
[36]Dirks RM,Bois J S,Schaeffer J M,et al.Thermodynamic analysis of interacting nucleic acid strands.SIAM Review.2007,49(1):65-88.
[37]Gultyaev A,van Batenburg F,Pleij C.An approximation of loop free energy values of RNA h-pseudoknots.RNA-a Publication of the RNA Society.1999,5(5):609-617.
[38]Liu H J,Xu D,Shao J L,et al.An RNA folding algorithm including pseudoknots based on dynamic weighted matching.Computational Biology and Chemistry.2006,30(1):72-76.
[39]Li H W,Zhu D M.A new pseudoknots folding algorithm for RNA structure prediction.In:Computing and combinatorics,proceedings.Berlin Heidelberg:Springer-Verlag,2005,lecture notes in computer science 3595(ISSN 0302-9743):94-103.
[40]Lyngso R B,Pedersen C.RNA pseudoknot prediction in energy-based models.Journal of Computational Biology.2000,7(3-4):409-427.
[41]Mathews D H.Predicting RNA secondary structure by free energy minimization.Theoretical Chemistry Accounts.2006,116(1-3):160-168.
[42]Namsrai O E,Ryu K H.Characterizing pseudobase and predicting RNA secondary structure with simple H-type pseudoknots based on dynamic programming.3rd International Conference on Advanced Data Mining and Applications,Harbin P R CHINA,AUG 06-08,2007,4632:578-585.
[43]Reeder J,Giegerich R.Design,implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.Bmc Bioinformatics 2004,5:104.
[44]Ren J H,Rastegari B,Condon A,et al.HotKnots:Heuristic prediction of RNA secondary structures including pseudoknots.RNA-a Publication of the RNA Society.2005,11(10):1494-1504.
[45]Ruan J H,Stormo G D,Zhang W X.An Iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots.Bioinformatics.2004,20(1):58-66.
[46]Shapiro B A,Kasprzak W,Grunewald C,et al.Graphical exploratory data analysis of RNA secondary structure dynamics predicted by the massively parallel genetic algorithm.Journal of Molecular Graphics & Modelling.206,25(4):514-531.
[47]Shapiro B A,Yingling Y G,Kasprzak W,et al.Bridging the gap in RNA structure prediction.Current Opinion in Structural Biology.2007,17(2):157-165.
[48]Westhof E,Fritsch V.RNA folding:beyond Watson-Crick pairs.Structure with Folding & Design.2000,8(3):R55-R65.
[49]Xayaphoummine A,Bucher T,Thalmann F,et al.Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations.PNAS 2003,100(26):15310-15315.
[50]Zhao J Z.Malmberg R L,Cai L M.Rapid ab initio RNA folding including pseudoknots via graph tree decomposition.Algorithms in Bioinformatics,Proceedings.2006,4175:262-273.
[51]Zhao J Z,Malmberg R L,Cai L M.Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition.Journal of Mathematical Biology.2008,56:145-159.
[52]Ji Y M,Xu X,Stormo G D.A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences.Bioinformatics.2004,20(10):1591-1602.
[53]Mathews D H.Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization.RNA-a Publication of the RNA Society.2004,10(8):1178-1190.
[54]Andronescu M,Fejes A P,Hutter F,et al.A new algorithm for RNA secondary structure design.Journal of Molecular Biology.2004,336(3):607-624.
[55]McCaskill J S.The equilibrium partition function and base pair binding probabilities for RNA secondary structure.Biopolymers.1990,29(6-7):1105-1119.
[56]Heitsch C E,Condon A E,Hoos H H.From RNA secondary structure to coding theory:A combinatorial approach.DNA Computing.2003,2568:215-228.
[57]Ruan J H,Stormo G D,Zhang W X.ILM:a web server for predicting RNA secondary structures with pseudoknots.Nucleic Acids Research.2004,32(S2):W146-W149.
[58]Xayaphoummine A,Bucher T,Isambert H.Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots.Nucleic Acids Research.2005,33(S):W605-W610.
[59]胡桂武,彭宏.利用混沌差分进化算法预测RNA二级结构.计算机科学,2007,34(9):163-166.
[60]谭光明,冯圣中,孙凝晖.RNA二级结构预测中动态规划和有效并行.软件学报,2006,17(7):1501-1509.
[61]李恒武,朱大铭,纪秀花.RNA二级结构预测算法的设计与实现.计算机工程与科学,2006,28(7):82-84.
[62]Li H W,Zhu D M,Liu Z D,et al.Prediction for RNA planar pseudoknots.Progress in natural Science.2007,17(6):717-724.
[63]王金华,骆志刚,管乃洋.基于最小自由能和协变信息预测带伪结RNA二级结构的迭代化方法.遗传,2007,29(7):889-897.
[64]Zuker M.Calculating nucleic acid secondary structure.Current Opinion in Structural Biology.2000,10(3):303-310.
[65]Mathews D H.Revolutions in RNA secondary structure prediction.Journal of Molecular Biology.2006,359(3):526-532.
[66]Gardner P P,Giegerich R.A comprehensive comparison of comparative RNA structure prediction approaches.BMC Bioinformatics.2004,5:140.
[67]刘海军,史定华,王翼飞.日新月异的RNA二级结构预测.自然杂志,2003,25(6):314-322.
[68]帕夫纳 P A著.王翼飞等译.计算分子生物学:算法逼近.北京:化学工业出版社,2004.
[69]Baldi P,Brunak S.Bioinformatics:The Machine Learning Approach.Cambridge,MA:MIT Press,2001.
[70]Durbin R,Krogh A,Mitchison G et al.Biological Sequence Analysis:Probabilistic Models of Proteins and Nucleic Acids.Cambridge UK:Cambridge University Press,1998.
[71]Mount D W.Bioinformatics:Sequence and Genome Analysis.New York:Cold Spring Harbor Laboratory Press,2001.
[72]Waterman M S.Applications of Combinatorics to Molecular Biology.In:Graham R,Grotschel M,Lovbz L,ed.Handbook of combinatorics.Amsterdam:Elsevier Science B V,1995.
[73]Waterman M S.Introduction to Computational Biology:Maps Sequences and Genomes.Boca Raton,FL:CRC Press,2000.
[74]Penner R C,Waterman M S.Spaces of RNA secondary structures.Advances in Mathematics.1993,101(1):31-49.
[75]Lyngso R B,Pedersen C.Pseudoknots in RNA secondary structures.In:Proceedings of the Fourth Annual International Conference on Computational Molecular Biology(RECOMB' 2000).8-11April,Tokyo,Japan,pp.201-209.
[76]Giegerich R,Voss B,Rehmsmeier M.Abstract shapes of RNA.Nucleic Acids Research.2004,32(16):4843-4851.
[77]西普塞 M著.张立昂,王捍贫,黄雄译.计算理论导引.北京:机械工业出版社,2001.
[78]堵丁柱,葛可一,王洁著.计算复杂性导论.北京:高等教育出版社,2002.
[79]张效祥主编.计算机科学技术百科全书.北京:清华大学出版社,1998.
[80]Jin E Y,Qin J,Reidys C M.Combinatorics of RNA structures with pseudoknots.Bulletin of Mathematical Biology.2008,70:45-67.
[81]Rodland E A.Pseudoknots in RNA Secondary Structures:Representation,Enumeration,and Prevalence.Journal of Computational Biology.2006,13(6):1197-1213.
[82]Pasquali S,Gan H,Schlick T.Modular RNA architecture revealed by computational analysis of existing pseudoknots and ribosomal RNAs.Nucleic Acids Research.2005,33(4):1384-1398.
[83]Haslinger C,Stadler P.RNA structures with pseudo-knots:Graph-theoretical,combinatorial and statistical properties.Bulletin of Mathematical Biology.1999,61(3):437-467.
[84]Nebel M.Combinatorial properties of RNA secondary structures.Journal of Computational Biology.2002,9(3):541-573.
[85]Higgs P G.RNA secondary structure:physical and computational aspects.Quarterly Reviews of Biophysics.2000,33(3):199-253.
[86]Schuster P,Stadler P F.Discrete Models of Biopolymers.In:Crabbe M J C,Drew M,Konopka A,ed.Handbook of Computational Chemistry.Marcel Dekker,New York,2002.
[87]Stein P R,Waterman M S.On some new sequences generalizing the Catalan and Motzkin numbers.Discrete Mathematics.1979,26(3):261-272.
[88]Waterman M S.Smith T F.RNA secondary structure:a complete mathematical analysis.Mathematical Biosciences.1978,42(2):257-266.
[89]Reidys C,Stadler P F.Bio-molecular shapes and algebraic structures.Computers &Chemistry.1996,20(1):85-94.
[90]Reidys C,Stadler P F,Schuster P.Generic Properties of Combinatory Maps:Neural Networks of RNA Secondary Structures.Bulletin of Mathematical Biology.1997,59(2):339-397.
[91]Reidys C,Stadler P F.Combinatorial landscapes.SlAM Review.2002,44(1):3-54.
[92]Casasnovas J,Miro-Julia J,Rossello F.On the algebraic representation of RNA secondary structures with G·U pairs.Journal of Mathematical Biology.2003,47(1):1-22.
[93]Hofacker I L,Schuster P,Stadler P F.Combinatorics of RNA secondary structures.Discrete Applied Mathematics.1998,88(1-3):207-237.
[94]Ding Y.Statistical and Bayesian approaches to RNA secondary structure prediction.RNA-a Publication of the RNA Society.2006,12(3):323-331.
[95]Fontana W,Konings D,Stadler P,et al.Statistics of RNA secondary structures.Biopolymers.1993,33(9):1389-1404.
[96]Searls D B.The computational linguistics of biological sequences.In:Hunter L ed.Artificial Intelligence and Molecular Biology Ch.2.Menlo Park,CA:AAAI Press,1993,47-120.
[97]Searls D B.Linguistic approaches to biological sequences.Comput.Appl.Biosci.1997,13(4):333-344.
[98]Searls D B.The language of gene.Nature.2002,420(6912):211-217.
[99]Matsui H,Sato K,Sakakibara Y.Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures.In:Proceedings-2004 IEEE Computational Systems Bioinformatics Conference,CSB,2004:290-299.
[100]Kato Y,Seki H,Kasami T.A comparative Study on Formal Grammars for Pseudoknots.Genome informatics.2003,14:470-471.
[101]Kato Y,Seki H,Kasami T.On the Generative Power of Grammars for RNA Secondary Structure.IEICE Transactions on Information and Systems.2005,E88D(1):53-64.
[102]Dowell R D,Eddy S R.Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction.BMC Bioinformatics,2004,5:71.
[103]Mathews D H,Sabina J,Zuker M,et al.Expanded Sequence Dependence of Thermodynamic Parameters Improves Prediction of RNA Secondary Structure.Journal of Molecular Biology.1999,288(5):911-940.
[104]Serra M,Turner D.Predicting thermodynamic properties of RNA.Energetics of Biological Macromolecules.1995,259:242-261.
[105]Pleij C W,Rietveld K,Bosch L.A new principle of RNA folding based on pseudoknotting.Nucleic Acids Research.1985,13(5):1717-1731.
[106]Han K,Byun Y.PseudoViewer2:visualization of RNA pseudoknots of any type.Nucleic Acids Research.2003,31(13):3432-3440.
[107]Lescoute A,Westhof E.Topology of three-way junctions in folded RNAs.RNA-a Publication of the RNA Society.2006,12(1):83-93.
[108]Aalberts D P,Hodas N O.Asymmetry in RNA pseudoknots:observation and theory.Nucleic Acids Research.2005,33(7):2210-2214.
[109]Uemura Y,Hasegawa A,Kobayashi S,et al.Tree adjoining grammars for RNA structure prediction.Theoretical Computer Science.1999,210(2):277-303.
[110]Liebers A.Planarizing graphs—a survey and annotated bibliography,Journal of Graph Algorithms and Applications.2001,5(1-4):1-74.
[111]Witwer C,Hofacker I L,Stadler P F.Prediction of consensus RNA secondary structures including pseudoknots.IEEE-ACM Transactions on Computational Biology and Bioinformatics.2004,1(2):66-77.
[112]Han K,Kim D,Kim H J.A vector-based method for drawing RNA secondary structure.Bioinformatics.1999,15(4):286-297.
[113]Han K,Lee Y,Kim W.PseudoViewer:automatic visualization of RNA pseudoknots.Bioinformatics 2002,18(S1):S321-S328.
[114]Lee D,Han K.Genetic Algorithm for Inferring Pseudoknotted RNA Structures from Sequence Data.In:Grieser G,et al.ed.Discovery Science,proceedings.Berlin Heidelberg:Springer-Verlag,2003,lecture notes in computer science 2843(ISSN 0302-9743):336-343.
[115]Byun Y,Han K.PseudoViewer:web application and web service for visualizing RNA pseudoknots and secondary structures.Nucleic Acids Research.2006,34(SI):W416-W422.
[116]Haslinger M C.Prediction Algorithms for Restricted RNA Pseudoknots(Ph.D.dissertation).Vienny:University of Vienny,2001.
[117]Dujmovic V,Wood D R.On linear layouts of graphs.Discrete Mathematics and Theoretical Computer Science.2004,6:339-358.
[118]王敬庚编著.直观拓扑.北京:北京师范大学出版社,2001.
[119]Bon M,Vernizzi G,Orland H,et al.Topological classification of RNA structures.arXiv:q-bio.BM/0607032 vl 21 Ju12006.http://www-spht.cea.fr/articles_k2/tO6/O90/paper.pdf
[120]Vemizzi G,Orland H,Zee A.Prediction of RNA pseudoknots by Monte Carlo simulations,arXiv:q-bio.BM/0405014 vl 19 May 2004.
[121]Orland H,Zee A.RNA folding and large N matrix theory.Nuclear Physics B.2002,620(3):456-476.
[122]Pillsbury M,Taylor J A,Orland H,et al.An Algorithm for RNA Pseudoknots.arXiv:cond-mat/0310505 vl 21 Oct 2003.
[123]Pillsbury M,Orland H,Zee A.Steepest descent calculation of RNA pseudoknots.Physical Review E.2005,72(1):011911.
[124]Vernizzi G,Orland H,Zee A.Enumeration of RNA structures by matrix models.Physical Review Letters.2005,94:168103/1-4.
[125]Vernizzi G,Orland H.Large-N random matrices for RNA folding.Acta Physica Polonica B.2005,36(9):2821-2827.
[126]Zee A.Random Matrix Theory and RNA Folding.Acta Physica Polonica B.2005,36(9):2829-2836.
[127]Brinkmeier M.Pseudoknotted secondary RNA structure.Scientific Literature Digital Library,available from:< http://citeseer.ist.psu.edu>.
[128]Moulton V,Zuker M,Steel M,et al.Metrics on RNA Secondary Structures.Journal of Computational Biology.2000,7(1-2):277-292.
[129]付微,黄竞伟,徐丽.RNA二级结构表示方法及其转换算法.计算机工程与应用,2004,40(14):43-45.
[130]Gan H H,Pasquali S,Schlick T.Exploring the repertoire of RNA secondary motifs using graph theory;implications for RNA design.Nucleic Acids Research.2003,31(11):2926-2943.
[131]Gan H H,Fera D,Zorn J,et al.RAG:RNA-As-Graphs database—concepts,analysis,and features.Bioinformatics.2004,20(8):1285-1291.
[132]Kim N,Shiffeldrim N,Gan H H,et al.Candidates for novel RNA topologies.Journal of Molecular Biology.2004,341(5):1129-1144.
[133]Berman H M,Olson W K,Beveridge D L,et al.The nucleic acid database:a comprehensive relational database of 3-dimensional structures of nucleic acids.Biophysical Journal.1992,63(3):751-759.
[134]Berman H M,Westbrook J,Feng Z,et al.The protein data bank.Nucleic Acids Research.2000,28(1):235-242.
[135]Berman H M,Henrick K,Nakamura H.Announcing the worldwide Protein DataBank.Nature Structural Biology.2003,10(12):980-980.
[136]West D B.Introduction to graph theory,Second edition.Beijing:Prentice Hall,2004.
[137]Brinkmeier M.Structural alignments of pseudokotted RAN-molecules in polynomial time.Scientific Literature Digital Library,available from:< http://citeseer.ist.psu.edu>.
[138]Rastegari B.Linear time algorithm for parsing RNA secondary structure(Master thesis).Vancouver:University of British Columbia,2004.
[139]Rastegari B,Condon A.Parsing nucleic acid pseudoknotted secondary structure:Algorithm and applications.Journal of Computational Biology.2007,14(1):16-32.
[140]谢惠民.生物信息学中的若干数学问题.中学数学月刊,2003,11:1-3;12:1-3.
[141]Clote P.Combinatorics of Saturated Secondary Structures of RNA.Journal of Computational Biology.2006,13(9):1640-1657.
[142]Hopcroft J E,Ullman J D.Introduction to Automata Theory,Languages,and Computation.Addison-Wesley,1979.
[143]Searls D B.The linguistics of DNA.American Scientist.1992,80(6):579-591.
[144]Searls D B.String Variable Grammar:a logical grammar formalism for DNA sequence.Journal of Logic Programming.1995,24(1-2):73-102.
[145]Cai L,Malmberg R L,Wu Y.Stochastic modeling of RNA pseudoknotted structures:a grammatical approach.Bioinformatics.2003,19(S1):ⅰ66-ⅰ73.
[146]Dong S,Searls D B.Gene Structure Prediction by Linguistic Methods.Genomics,1994,23(3):540-551.
[147]Chiang D,Joshi A K,Searls D B.Grammatical representations of maeromolecular structure.Journal of Computational Biology.2006,13(5):1077-1100.
[148]Murzin A G,Brenner S E,Hubbard T,et al.SCOP-a structural classification of proteins database for the investigation of sequences and structures.Journal of Molecular Biology.1995,247(4):536-540.
[149]Orengo C A,Michie A D,Jones S,et al.CATH-a hierarchic classification of protein domain structures.Structure.1997,5(8):1093-1108.
[150]王朝瑞编著.图论(第三版).北京:北京理工大学出版社,2001.
[151]Bondy J A,Murty U S R.Graph theory with applications.London:Macmillan,1976.
[152]高纳德著.苏运霖译.计算机程序设计艺术第一卷:基本算法(第三版).北京:国防工业出版社,2002.
[153]高纳德著.苏运霖译.计算机程序设计艺术第三卷:排序与查找(第二版).北京:国防工业出版社,2002.
[154]Aho A V,Hopcroft J E,Ullman J E.The Design and Analysis of Computer Algorithms.Addison-Wesley,1974.
[155]Graham R L,Knuth D E,Patashnik O.Concrete Mathematics:A foundation for Computer Science.Pearson Education,1994.
[156]Hopcroft J,Tarjan R.Efficient Planarity Testing.Journal of the ACM.1974,21(4):549-568.
[157]Booth K S,Lueaker G S.Tsting for consecutive one property,interval graphs,and graph planarity using PQ-tree algorithms.Journal of Computer and System Sciences.1976,13(3):335-379.
[158]Demoucron G,Malgrange Y,Pertuiset R.Graphes planaires:reconnaissance et construction de representations planaires topologiques.Review Francaise Recherche Operationnelle.1964,8:33-47.
[159]Klotz W.A constructive proof of Kuratowski's theorem.Ars Combinatoria.1989,28:51-54.
[160]Klotz W.Clique covers and coloring problems of graphs.Journal of combinatorial theory,series B.1989,46(3):338-345.
[161]Orlitsky A,Venkatesh S S.On edge-colored interior planar graphs on a circle and the expected number of RNA secondary structures.Discrete Applied Mathematics.1996,64(2):151-178.
[162]Tuza Z.Graph colorings with local constraints—A survey.Discussiones Mathematicae-Graph Theory.1997,17(2):161-228.
[163]Beineke L W,Wilson R J.Selected Topics in Graph Theory,Vol 1.London:Academic Press,1978.
[164]Beineke L W,Wilson R J.Selected Topics in Graph Theory,Vol 2.London:Academic Press,1983.
[165]Beineke L W,Wilson R J.Selected Topics in Graph Theory,Vol 3.London:Academic Press,1988.
[166]Golumbic M C.Algorithmic Graph Theory and Perfect Graphs.New York:Academic Press,1980.
[167]Berge C.Graphs.Elsevier science publishing company,1985.
[168]Fukerson D R.Blocking and anti-blocking pairs of polyhedra.Mathematical Programming.1971,1:168-194.
[169]Fukerson D R.Anti-blocking polyhedra.Journal of Combinatorial Theory,Series B.1972,12(1):50-71.
[170]Lovasz L.Normal hypergraphs and the perfect graphs.Discrete Mathematics.1972,2:253-267(Reprinted 2006,306(10-11):867-875).
[171]Lovasz L.A characterization of perfect graphs.Journal of Combinatorial Theory,Series B.1972,13(2):95-98.
[172]Murthy V L,Rose G D.RNABase:an annotated database of RNA structures.Nucleic Acids Research.2003,31(1):502-504.
[173]郝柏林,张淑誉.生物信息学手册.上海:上海科技文献出版社,2000.
[174]刘彦佩著.地图的代数原理.北京:高等教育出版社,2006.
[175]巴尔S著.许明译.拓扑实验.上海:上海教育出版社,2002.
[176]Hooft G.A planar diagram theory for strong interactions.Nuclear Physics B.1974,B72(3):461-473.
[177]Vemizzi G,Ribeca P,Orland H,et al.Topology of pseudoknotted homopolymers.Physical Review E.2006,73(3):031902.
[178]Miklos I,Meyer I M,Nagy B.Moments of the Boltzmann distribution for RNA secondary structures.Bulletin of Mathematical Biology.2005,67(5):1031-1047.
[2]琼斯 N C,帕夫纳 P A著.王翼飞等译.生物信息学算法导论.北京:化学工业出版社,2007.
[3]塞图宝 J,梅丹尼斯 J著.朱浩译.计算分子生物学导论.北京:科学出版社,2003.
[4]金由辛编著.核糖核酸与核糖核酸组学.北京:科学出版社,2005.
[5]Dennis C.The brave new world of RNA.Nature.2002,418(6894):122-124.
[6]刘永明主编.分子生物学简明教程.北京:化学工业出版社,2006.
[7]刘次全,曹恩华,白春礼等著.核酸结构多态性.北京:高等教育出版社,2000.
[8]金由辛.面向21世纪的RNA研究.自然科学进展,2000,10(7):600-606.
[9]梁毅主编.结构生物学.北京:科学出版社,2005.
[10]刘次全.白春礼,张静著.结构分子生物学.北京:高等教育出版社,1997.
[11]Karp G.Cell and Molecular Biology.John Wiley & Sons Inc,2002.
[12]卡普著.王喜忠,丁明孝,张传茂等译.分子细胞生物学,北京:高等教育出版社,2005.
[13]王传铭,潘珉,曹槐.RNA折叠.自然杂志,2004,26(5):249-254.
[14]Mathews D H,Turner D H.Prediction of RNA secondary structure by free energy minimization,Current Opinion in Structural Biology.2006,16(3):270-278.
[15]Zuker M,Stiegler P.Optimal computer folding of larger RNA sequences using thermodynamics and auxiliary information.Nucleic Acids Research.1981,9(1):133-148.
[16]Nussinov R,Pieczenik G,Griggs J,et al.Algorithms for loop matchings.SIAM Journal on Applied Mathematics.1978,35:68-82.
[17]Ieong S,Kao M-Y,Lam T-W,et al.Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs.Journal of Computational Biology.2003,10(6):981-995.
[18]Dirks R M,Pierce N A.partition function algorithm for nucleic acid secondary structure including pseudoknots.Journal of computational Chemistry.2003,24(13):1664-1677.
[19]王翼飞,史定华主编.生物信息学:智能化算法及其应用.北京:化学工业出版社,2006.
[20]Voss B.Structural analysis of aligned RNAs.Nucleic Acids Research.2006,34(19):5471-5481.
[21]Bindewald E,Shapiro B A.RNA secondary structure prediction from sequence alignments using a network of k-nearest neighbor classifiers.RNA-a Publication of the RNA Society.2006,12(3):342-352.
[22]刘琦,张引,叶修梓等.基于奇异值分解的RNA级结构相似度计算方法.浙江大学学报(工学版),2007,41(8):1249-1255.
[23]Le S Y,Nussinov R,Maizel J V.Tree graphs of RNA secondary structures and their comparisons.Computers and Biomedical Research.1989,22(5):461-473.
[24]Zuker M.Mfold web server for nucleic acid folding and hybridization prediction.Nucleic Acids Research.2003,31(13):3406-3415.
[25]Hofacker I L.Vienna RNA secondary structure server.Nucleic Acids Research.2003,31(13):3429-3431.
[26]Waterman M S,Smith T F.Rapid dynamic programming algorithms for RNA secondary structure.Advances in applied mathematics.1986,7(4):455-464.
[27]Rivas E.Eddy S R.A dynamic programming algorithm for RNA structure prediction including pseudoknots.Journal of Molecular Biology.1999,285(5):2053-2068.
[28]Rivas E,Eddy S R.The language of RNA:a formal grammar that includes pseudoknots.Bioinformatics.2000,16(4):334-340.
[29]Condon A,Davy B,Rastegari B,et al.Classifying RNA pseudoknotted structures.Theoretical Computer Science.2004,320(1):35-50.
[30]van Batenburg F H D,Gultyaev A P,Pleij C W A,et al.Pseudobase:a database with RNA pseudoknots.Nucleic Acids Research.2000,28(1):201-204.
[31]van Batenburg F H D,Gultyaev A P,Pleij C W A.PseudoBase:structural information on RNA pseudoknots.Nucleic Acids Research.2001,29(1):194-195.
[32]Cannone J J,Subramanian S,Schnare M N,et al.The comparative RNA web(CRW)site:an online database of comparative sequence and structure information for ribosomal,intron,and other RNAs.BMC Bioinformatics.2002,3:15.
[33]Akutsu,T.Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots.Discrete Applied Mathematics.2000,104(1-3):45-62.
[34]Akutsu T.Recent advances in RNA secondary structure prediction with pseudoknots.Current Bioinformatics.2006,1(2):115-129.
[35]Dirks R M,Pierce N A.An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots.Journal of Computational Chemistry.2004,25(10):1295-1304.
[36]Dirks RM,Bois J S,Schaeffer J M,et al.Thermodynamic analysis of interacting nucleic acid strands.SIAM Review.2007,49(1):65-88.
[37]Gultyaev A,van Batenburg F,Pleij C.An approximation of loop free energy values of RNA h-pseudoknots.RNA-a Publication of the RNA Society.1999,5(5):609-617.
[38]Liu H J,Xu D,Shao J L,et al.An RNA folding algorithm including pseudoknots based on dynamic weighted matching.Computational Biology and Chemistry.2006,30(1):72-76.
[39]Li H W,Zhu D M.A new pseudoknots folding algorithm for RNA structure prediction.In:Computing and combinatorics,proceedings.Berlin Heidelberg:Springer-Verlag,2005,lecture notes in computer science 3595(ISSN 0302-9743):94-103.
[40]Lyngso R B,Pedersen C.RNA pseudoknot prediction in energy-based models.Journal of Computational Biology.2000,7(3-4):409-427.
[41]Mathews D H.Predicting RNA secondary structure by free energy minimization.Theoretical Chemistry Accounts.2006,116(1-3):160-168.
[42]Namsrai O E,Ryu K H.Characterizing pseudobase and predicting RNA secondary structure with simple H-type pseudoknots based on dynamic programming.3rd International Conference on Advanced Data Mining and Applications,Harbin P R CHINA,AUG 06-08,2007,4632:578-585.
[43]Reeder J,Giegerich R.Design,implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.Bmc Bioinformatics 2004,5:104.
[44]Ren J H,Rastegari B,Condon A,et al.HotKnots:Heuristic prediction of RNA secondary structures including pseudoknots.RNA-a Publication of the RNA Society.2005,11(10):1494-1504.
[45]Ruan J H,Stormo G D,Zhang W X.An Iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots.Bioinformatics.2004,20(1):58-66.
[46]Shapiro B A,Kasprzak W,Grunewald C,et al.Graphical exploratory data analysis of RNA secondary structure dynamics predicted by the massively parallel genetic algorithm.Journal of Molecular Graphics & Modelling.206,25(4):514-531.
[47]Shapiro B A,Yingling Y G,Kasprzak W,et al.Bridging the gap in RNA structure prediction.Current Opinion in Structural Biology.2007,17(2):157-165.
[48]Westhof E,Fritsch V.RNA folding:beyond Watson-Crick pairs.Structure with Folding & Design.2000,8(3):R55-R65.
[49]Xayaphoummine A,Bucher T,Thalmann F,et al.Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations.PNAS 2003,100(26):15310-15315.
[50]Zhao J Z.Malmberg R L,Cai L M.Rapid ab initio RNA folding including pseudoknots via graph tree decomposition.Algorithms in Bioinformatics,Proceedings.2006,4175:262-273.
[51]Zhao J Z,Malmberg R L,Cai L M.Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition.Journal of Mathematical Biology.2008,56:145-159.
[52]Ji Y M,Xu X,Stormo G D.A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences.Bioinformatics.2004,20(10):1591-1602.
[53]Mathews D H.Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization.RNA-a Publication of the RNA Society.2004,10(8):1178-1190.
[54]Andronescu M,Fejes A P,Hutter F,et al.A new algorithm for RNA secondary structure design.Journal of Molecular Biology.2004,336(3):607-624.
[55]McCaskill J S.The equilibrium partition function and base pair binding probabilities for RNA secondary structure.Biopolymers.1990,29(6-7):1105-1119.
[56]Heitsch C E,Condon A E,Hoos H H.From RNA secondary structure to coding theory:A combinatorial approach.DNA Computing.2003,2568:215-228.
[57]Ruan J H,Stormo G D,Zhang W X.ILM:a web server for predicting RNA secondary structures with pseudoknots.Nucleic Acids Research.2004,32(S2):W146-W149.
[58]Xayaphoummine A,Bucher T,Isambert H.Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots.Nucleic Acids Research.2005,33(S):W605-W610.
[59]胡桂武,彭宏.利用混沌差分进化算法预测RNA二级结构.计算机科学,2007,34(9):163-166.
[60]谭光明,冯圣中,孙凝晖.RNA二级结构预测中动态规划和有效并行.软件学报,2006,17(7):1501-1509.
[61]李恒武,朱大铭,纪秀花.RNA二级结构预测算法的设计与实现.计算机工程与科学,2006,28(7):82-84.
[62]Li H W,Zhu D M,Liu Z D,et al.Prediction for RNA planar pseudoknots.Progress in natural Science.2007,17(6):717-724.
[63]王金华,骆志刚,管乃洋.基于最小自由能和协变信息预测带伪结RNA二级结构的迭代化方法.遗传,2007,29(7):889-897.
[64]Zuker M.Calculating nucleic acid secondary structure.Current Opinion in Structural Biology.2000,10(3):303-310.
[65]Mathews D H.Revolutions in RNA secondary structure prediction.Journal of Molecular Biology.2006,359(3):526-532.
[66]Gardner P P,Giegerich R.A comprehensive comparison of comparative RNA structure prediction approaches.BMC Bioinformatics.2004,5:140.
[67]刘海军,史定华,王翼飞.日新月异的RNA二级结构预测.自然杂志,2003,25(6):314-322.
[68]帕夫纳 P A著.王翼飞等译.计算分子生物学:算法逼近.北京:化学工业出版社,2004.
[69]Baldi P,Brunak S.Bioinformatics:The Machine Learning Approach.Cambridge,MA:MIT Press,2001.
[70]Durbin R,Krogh A,Mitchison G et al.Biological Sequence Analysis:Probabilistic Models of Proteins and Nucleic Acids.Cambridge UK:Cambridge University Press,1998.
[71]Mount D W.Bioinformatics:Sequence and Genome Analysis.New York:Cold Spring Harbor Laboratory Press,2001.
[72]Waterman M S.Applications of Combinatorics to Molecular Biology.In:Graham R,Grotschel M,Lovbz L,ed.Handbook of combinatorics.Amsterdam:Elsevier Science B V,1995.
[73]Waterman M S.Introduction to Computational Biology:Maps Sequences and Genomes.Boca Raton,FL:CRC Press,2000.
[74]Penner R C,Waterman M S.Spaces of RNA secondary structures.Advances in Mathematics.1993,101(1):31-49.
[75]Lyngso R B,Pedersen C.Pseudoknots in RNA secondary structures.In:Proceedings of the Fourth Annual International Conference on Computational Molecular Biology(RECOMB' 2000).8-11April,Tokyo,Japan,pp.201-209.
[76]Giegerich R,Voss B,Rehmsmeier M.Abstract shapes of RNA.Nucleic Acids Research.2004,32(16):4843-4851.
[77]西普塞 M著.张立昂,王捍贫,黄雄译.计算理论导引.北京:机械工业出版社,2001.
[78]堵丁柱,葛可一,王洁著.计算复杂性导论.北京:高等教育出版社,2002.
[79]张效祥主编.计算机科学技术百科全书.北京:清华大学出版社,1998.
[80]Jin E Y,Qin J,Reidys C M.Combinatorics of RNA structures with pseudoknots.Bulletin of Mathematical Biology.2008,70:45-67.
[81]Rodland E A.Pseudoknots in RNA Secondary Structures:Representation,Enumeration,and Prevalence.Journal of Computational Biology.2006,13(6):1197-1213.
[82]Pasquali S,Gan H,Schlick T.Modular RNA architecture revealed by computational analysis of existing pseudoknots and ribosomal RNAs.Nucleic Acids Research.2005,33(4):1384-1398.
[83]Haslinger C,Stadler P.RNA structures with pseudo-knots:Graph-theoretical,combinatorial and statistical properties.Bulletin of Mathematical Biology.1999,61(3):437-467.
[84]Nebel M.Combinatorial properties of RNA secondary structures.Journal of Computational Biology.2002,9(3):541-573.
[85]Higgs P G.RNA secondary structure:physical and computational aspects.Quarterly Reviews of Biophysics.2000,33(3):199-253.
[86]Schuster P,Stadler P F.Discrete Models of Biopolymers.In:Crabbe M J C,Drew M,Konopka A,ed.Handbook of Computational Chemistry.Marcel Dekker,New York,2002.
[87]Stein P R,Waterman M S.On some new sequences generalizing the Catalan and Motzkin numbers.Discrete Mathematics.1979,26(3):261-272.
[88]Waterman M S.Smith T F.RNA secondary structure:a complete mathematical analysis.Mathematical Biosciences.1978,42(2):257-266.
[89]Reidys C,Stadler P F.Bio-molecular shapes and algebraic structures.Computers &Chemistry.1996,20(1):85-94.
[90]Reidys C,Stadler P F,Schuster P.Generic Properties of Combinatory Maps:Neural Networks of RNA Secondary Structures.Bulletin of Mathematical Biology.1997,59(2):339-397.
[91]Reidys C,Stadler P F.Combinatorial landscapes.SlAM Review.2002,44(1):3-54.
[92]Casasnovas J,Miro-Julia J,Rossello F.On the algebraic representation of RNA secondary structures with G·U pairs.Journal of Mathematical Biology.2003,47(1):1-22.
[93]Hofacker I L,Schuster P,Stadler P F.Combinatorics of RNA secondary structures.Discrete Applied Mathematics.1998,88(1-3):207-237.
[94]Ding Y.Statistical and Bayesian approaches to RNA secondary structure prediction.RNA-a Publication of the RNA Society.2006,12(3):323-331.
[95]Fontana W,Konings D,Stadler P,et al.Statistics of RNA secondary structures.Biopolymers.1993,33(9):1389-1404.
[96]Searls D B.The computational linguistics of biological sequences.In:Hunter L ed.Artificial Intelligence and Molecular Biology Ch.2.Menlo Park,CA:AAAI Press,1993,47-120.
[97]Searls D B.Linguistic approaches to biological sequences.Comput.Appl.Biosci.1997,13(4):333-344.
[98]Searls D B.The language of gene.Nature.2002,420(6912):211-217.
[99]Matsui H,Sato K,Sakakibara Y.Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures.In:Proceedings-2004 IEEE Computational Systems Bioinformatics Conference,CSB,2004:290-299.
[100]Kato Y,Seki H,Kasami T.A comparative Study on Formal Grammars for Pseudoknots.Genome informatics.2003,14:470-471.
[101]Kato Y,Seki H,Kasami T.On the Generative Power of Grammars for RNA Secondary Structure.IEICE Transactions on Information and Systems.2005,E88D(1):53-64.
[102]Dowell R D,Eddy S R.Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction.BMC Bioinformatics,2004,5:71.
[103]Mathews D H,Sabina J,Zuker M,et al.Expanded Sequence Dependence of Thermodynamic Parameters Improves Prediction of RNA Secondary Structure.Journal of Molecular Biology.1999,288(5):911-940.
[104]Serra M,Turner D.Predicting thermodynamic properties of RNA.Energetics of Biological Macromolecules.1995,259:242-261.
[105]Pleij C W,Rietveld K,Bosch L.A new principle of RNA folding based on pseudoknotting.Nucleic Acids Research.1985,13(5):1717-1731.
[106]Han K,Byun Y.PseudoViewer2:visualization of RNA pseudoknots of any type.Nucleic Acids Research.2003,31(13):3432-3440.
[107]Lescoute A,Westhof E.Topology of three-way junctions in folded RNAs.RNA-a Publication of the RNA Society.2006,12(1):83-93.
[108]Aalberts D P,Hodas N O.Asymmetry in RNA pseudoknots:observation and theory.Nucleic Acids Research.2005,33(7):2210-2214.
[109]Uemura Y,Hasegawa A,Kobayashi S,et al.Tree adjoining grammars for RNA structure prediction.Theoretical Computer Science.1999,210(2):277-303.
[110]Liebers A.Planarizing graphs—a survey and annotated bibliography,Journal of Graph Algorithms and Applications.2001,5(1-4):1-74.
[111]Witwer C,Hofacker I L,Stadler P F.Prediction of consensus RNA secondary structures including pseudoknots.IEEE-ACM Transactions on Computational Biology and Bioinformatics.2004,1(2):66-77.
[112]Han K,Kim D,Kim H J.A vector-based method for drawing RNA secondary structure.Bioinformatics.1999,15(4):286-297.
[113]Han K,Lee Y,Kim W.PseudoViewer:automatic visualization of RNA pseudoknots.Bioinformatics 2002,18(S1):S321-S328.
[114]Lee D,Han K.Genetic Algorithm for Inferring Pseudoknotted RNA Structures from Sequence Data.In:Grieser G,et al.ed.Discovery Science,proceedings.Berlin Heidelberg:Springer-Verlag,2003,lecture notes in computer science 2843(ISSN 0302-9743):336-343.
[115]Byun Y,Han K.PseudoViewer:web application and web service for visualizing RNA pseudoknots and secondary structures.Nucleic Acids Research.2006,34(SI):W416-W422.
[116]Haslinger M C.Prediction Algorithms for Restricted RNA Pseudoknots(Ph.D.dissertation).Vienny:University of Vienny,2001.
[117]Dujmovic V,Wood D R.On linear layouts of graphs.Discrete Mathematics and Theoretical Computer Science.2004,6:339-358.
[118]王敬庚编著.直观拓扑.北京:北京师范大学出版社,2001.
[119]Bon M,Vernizzi G,Orland H,et al.Topological classification of RNA structures.arXiv:q-bio.BM/0607032 vl 21 Ju12006.http://www-spht.cea.fr/articles_k2/tO6/O90/paper.pdf
[120]Vemizzi G,Orland H,Zee A.Prediction of RNA pseudoknots by Monte Carlo simulations,arXiv:q-bio.BM/0405014 vl 19 May 2004.
[121]Orland H,Zee A.RNA folding and large N matrix theory.Nuclear Physics B.2002,620(3):456-476.
[122]Pillsbury M,Taylor J A,Orland H,et al.An Algorithm for RNA Pseudoknots.arXiv:cond-mat/0310505 vl 21 Oct 2003.
[123]Pillsbury M,Orland H,Zee A.Steepest descent calculation of RNA pseudoknots.Physical Review E.2005,72(1):011911.
[124]Vernizzi G,Orland H,Zee A.Enumeration of RNA structures by matrix models.Physical Review Letters.2005,94:168103/1-4.
[125]Vernizzi G,Orland H.Large-N random matrices for RNA folding.Acta Physica Polonica B.2005,36(9):2821-2827.
[126]Zee A.Random Matrix Theory and RNA Folding.Acta Physica Polonica B.2005,36(9):2829-2836.
[127]Brinkmeier M.Pseudoknotted secondary RNA structure.Scientific Literature Digital Library,available from:< http://citeseer.ist.psu.edu>.
[128]Moulton V,Zuker M,Steel M,et al.Metrics on RNA Secondary Structures.Journal of Computational Biology.2000,7(1-2):277-292.
[129]付微,黄竞伟,徐丽.RNA二级结构表示方法及其转换算法.计算机工程与应用,2004,40(14):43-45.
[130]Gan H H,Pasquali S,Schlick T.Exploring the repertoire of RNA secondary motifs using graph theory;implications for RNA design.Nucleic Acids Research.2003,31(11):2926-2943.
[131]Gan H H,Fera D,Zorn J,et al.RAG:RNA-As-Graphs database—concepts,analysis,and features.Bioinformatics.2004,20(8):1285-1291.
[132]Kim N,Shiffeldrim N,Gan H H,et al.Candidates for novel RNA topologies.Journal of Molecular Biology.2004,341(5):1129-1144.
[133]Berman H M,Olson W K,Beveridge D L,et al.The nucleic acid database:a comprehensive relational database of 3-dimensional structures of nucleic acids.Biophysical Journal.1992,63(3):751-759.
[134]Berman H M,Westbrook J,Feng Z,et al.The protein data bank.Nucleic Acids Research.2000,28(1):235-242.
[135]Berman H M,Henrick K,Nakamura H.Announcing the worldwide Protein DataBank.Nature Structural Biology.2003,10(12):980-980.
[136]West D B.Introduction to graph theory,Second edition.Beijing:Prentice Hall,2004.
[137]Brinkmeier M.Structural alignments of pseudokotted RAN-molecules in polynomial time.Scientific Literature Digital Library,available from:< http://citeseer.ist.psu.edu>.
[138]Rastegari B.Linear time algorithm for parsing RNA secondary structure(Master thesis).Vancouver:University of British Columbia,2004.
[139]Rastegari B,Condon A.Parsing nucleic acid pseudoknotted secondary structure:Algorithm and applications.Journal of Computational Biology.2007,14(1):16-32.
[140]谢惠民.生物信息学中的若干数学问题.中学数学月刊,2003,11:1-3;12:1-3.
[141]Clote P.Combinatorics of Saturated Secondary Structures of RNA.Journal of Computational Biology.2006,13(9):1640-1657.
[142]Hopcroft J E,Ullman J D.Introduction to Automata Theory,Languages,and Computation.Addison-Wesley,1979.
[143]Searls D B.The linguistics of DNA.American Scientist.1992,80(6):579-591.
[144]Searls D B.String Variable Grammar:a logical grammar formalism for DNA sequence.Journal of Logic Programming.1995,24(1-2):73-102.
[145]Cai L,Malmberg R L,Wu Y.Stochastic modeling of RNA pseudoknotted structures:a grammatical approach.Bioinformatics.2003,19(S1):ⅰ66-ⅰ73.
[146]Dong S,Searls D B.Gene Structure Prediction by Linguistic Methods.Genomics,1994,23(3):540-551.
[147]Chiang D,Joshi A K,Searls D B.Grammatical representations of maeromolecular structure.Journal of Computational Biology.2006,13(5):1077-1100.
[148]Murzin A G,Brenner S E,Hubbard T,et al.SCOP-a structural classification of proteins database for the investigation of sequences and structures.Journal of Molecular Biology.1995,247(4):536-540.
[149]Orengo C A,Michie A D,Jones S,et al.CATH-a hierarchic classification of protein domain structures.Structure.1997,5(8):1093-1108.
[150]王朝瑞编著.图论(第三版).北京:北京理工大学出版社,2001.
[151]Bondy J A,Murty U S R.Graph theory with applications.London:Macmillan,1976.
[152]高纳德著.苏运霖译.计算机程序设计艺术第一卷:基本算法(第三版).北京:国防工业出版社,2002.
[153]高纳德著.苏运霖译.计算机程序设计艺术第三卷:排序与查找(第二版).北京:国防工业出版社,2002.
[154]Aho A V,Hopcroft J E,Ullman J E.The Design and Analysis of Computer Algorithms.Addison-Wesley,1974.
[155]Graham R L,Knuth D E,Patashnik O.Concrete Mathematics:A foundation for Computer Science.Pearson Education,1994.
[156]Hopcroft J,Tarjan R.Efficient Planarity Testing.Journal of the ACM.1974,21(4):549-568.
[157]Booth K S,Lueaker G S.Tsting for consecutive one property,interval graphs,and graph planarity using PQ-tree algorithms.Journal of Computer and System Sciences.1976,13(3):335-379.
[158]Demoucron G,Malgrange Y,Pertuiset R.Graphes planaires:reconnaissance et construction de representations planaires topologiques.Review Francaise Recherche Operationnelle.1964,8:33-47.
[159]Klotz W.A constructive proof of Kuratowski's theorem.Ars Combinatoria.1989,28:51-54.
[160]Klotz W.Clique covers and coloring problems of graphs.Journal of combinatorial theory,series B.1989,46(3):338-345.
[161]Orlitsky A,Venkatesh S S.On edge-colored interior planar graphs on a circle and the expected number of RNA secondary structures.Discrete Applied Mathematics.1996,64(2):151-178.
[162]Tuza Z.Graph colorings with local constraints—A survey.Discussiones Mathematicae-Graph Theory.1997,17(2):161-228.
[163]Beineke L W,Wilson R J.Selected Topics in Graph Theory,Vol 1.London:Academic Press,1978.
[164]Beineke L W,Wilson R J.Selected Topics in Graph Theory,Vol 2.London:Academic Press,1983.
[165]Beineke L W,Wilson R J.Selected Topics in Graph Theory,Vol 3.London:Academic Press,1988.
[166]Golumbic M C.Algorithmic Graph Theory and Perfect Graphs.New York:Academic Press,1980.
[167]Berge C.Graphs.Elsevier science publishing company,1985.
[168]Fukerson D R.Blocking and anti-blocking pairs of polyhedra.Mathematical Programming.1971,1:168-194.
[169]Fukerson D R.Anti-blocking polyhedra.Journal of Combinatorial Theory,Series B.1972,12(1):50-71.
[170]Lovasz L.Normal hypergraphs and the perfect graphs.Discrete Mathematics.1972,2:253-267(Reprinted 2006,306(10-11):867-875).
[171]Lovasz L.A characterization of perfect graphs.Journal of Combinatorial Theory,Series B.1972,13(2):95-98.
[172]Murthy V L,Rose G D.RNABase:an annotated database of RNA structures.Nucleic Acids Research.2003,31(1):502-504.
[173]郝柏林,张淑誉.生物信息学手册.上海:上海科技文献出版社,2000.
[174]刘彦佩著.地图的代数原理.北京:高等教育出版社,2006.
[175]巴尔S著.许明译.拓扑实验.上海:上海教育出版社,2002.
[176]Hooft G.A planar diagram theory for strong interactions.Nuclear Physics B.1974,B72(3):461-473.
[177]Vemizzi G,Ribeca P,Orland H,et al.Topology of pseudoknotted homopolymers.Physical Review E.2006,73(3):031902.
[178]Miklos I,Meyer I M,Nagy B.Moments of the Boltzmann distribution for RNA secondary structures.Bulletin of Mathematical Biology.2005,67(5):1031-1047.