Combinatorics of RNA Structures with Pseudoknots

被引：0
作者：
Emma Y. Jin
Jing Qin
Christian M. Reidys
机构：
[1] Nankai University,Center for Combinatorics, LMPC
来源：
Bulletin of Mathematical Biology | 2008年 / 70卷
关键词：
RNA secondary structure; Pseudoknot; Enumeration; Generating function; Reflection principle; Walks; Weyl-chamber;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, we derive the generating function of RNA structures with pseudoknots. We enumerate all k-noncrossing RNA pseudoknot structures categorized by their maximal sets of mutually intersecting arcs. In addition, we enumerate pseudoknot structures over circular RNA. For 3-noncrossing RNA structures and RNA secondary structures we present a novel 4-term recursion formula and a 2-term recursion, respectively. Furthermore, we enumerate for arbitrary k all k-noncrossing, restricted RNA structures i.e. k-noncrossing RNA structures without 2-arcs i.e. arcs of the form (i,i+2), for 1≤i≤n−2.
引用
收藏
页码：45 / 67
页数：22
相关论文
共 62 条
[1]  
Akutsu T.(2000)Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots Discret. Appl. Math. 104 45-62
[2]  
Chen W.Y.C.(2007)Crossings and nestings of matchings and partitions Trans. Am. Math. Soc. 359 1555-1575
[3]  
Deng E.Y.P.(1992)Random walk in a Weyl chamber Proc. Am. Math. Soc. 115 27-31
[4]  
Du R.R.X.(1993)Random walks in Weyl chambers and the decomposition of tensor powers J. Algebr. Comb. 2 239-260
[5]  
Stanley R.P.(1999)Tree adjoining grammars for RNA structure prediction Theor. Comput. Sci. 210 277-303
[6]  
Yan C.H.(1999)RNA structures with pseudo-knots Bull. Math. Biol. 61 437-467
[7]  
Gessel I.M.(1998)Combinatorics of RNA secondary structures Discret. Appl. Math. 88 207-237
[8]  
Zeilberger D.(1980)Computation of generating functions for biological molecules SIAM J. Appl. Math. 39 119-133
[9]  
Grabiner D.J.(1995)A comparison of thermodynamic foldings with comparatively derived structures of 16s and 16s-like rRNAs RNA 1 559-574
[10]  
Magyar P.(1973)On the vector representation of induced matroids Bull. Lond. Math. Soc. 5 85-90
1234567