有序树的计数及其应用

金应烈， 任俊丽

( 南开大学 数学科学学院， 天津 300071 )

0 引言

RNA二级结构的计数问题是计算分子生物学中的研究课题之一，也是组合数学的一个新兴研究课题.文献[1-6]研究了满足一定参数条件的RNA二级结构计数，但其结果大多只满足于不同参数条件下的RNA二级结构计数的递推关系式、生成函数或近似估计值，而对完全显示闭公式研究得很少.文献[7-8]利用不同的对合算法研究了含有k个内点的标号有序树的计数.本文利用标号有序树与森林的对合，讨论含有k+1个内点和p个外层内点且外层内点的度不小于正整数m的顶点数为n+1-k的非标号有序树的计数，并给出端环长度不小于正整数m的RNA二级结构计数的完全显示闭公式.在本文中作如下规定：对于有序树T中的一个内点u， 若u的所有子结点均为叶子点，则称u为外层内点；否则，称u为内层内点.高度为1的标号有序树称为基本有序树.

1 非标号有序树的计数

定理1设含有k+1个内点、顶点数为n+1-k的标号有序树T组成的集合为A， 由k+1个基本有序树组成的顶点数为n+1的森林Fk+1的集合为B， 其中k+1个基本有序树的根结点标号在{1,2,…,n+1-k}上，则A与B之间存在一个双射.

1)在有序树T的所有外层内点中，找出标号最小的外层内点vi；

3)重复以上过程，直至T中除根结点以外的所有内点均成为基本有序树Ti(i=1,2,…,k)的根结点为止.

由以上可得一个由k+1个基本有序树所构成的顶点数为n+1的森林Fk+1.

其次，以集合B中的一个森林Fk+1构造A中的一个有序树T.

3)重复以上过程，直至森林Fk+1变为一个标号有序树.

由以上可证，集合A与B之间存在一个双射.

从上述的双射构造过程可知，在有序树T中若有p个外层内点，则在森林Fk+1中恰有每个根结点的度不小于正整数m的p个基本有序树，且其叶子点均为非星号点，而其余内层内点所对应的基本有序树的叶子点中至少含有1个星号点.

定理2设顶点数为n+1-k的非标号有序树含有k+1个内点和p个外层内点，且外层内点的度不小于正整数m， 则满足条件的非标号有序树的个数为

证明当k=0时，根结点外的所有顶点均为叶子点，此时显然只有一个基本无序树.当k≥1时，由定理1知，所求标号有序树T的个数与顶点数为n+1的森林Fk+1的个数相等，其中Fk+1中恰含有p个度不小于正整数m且其叶子点均为非星号点的基本有序树.因此，若求满足定理条件的标号有序树T的个数，只需求顶点数为n+1的森林Fk+1的个数即可.

再次，将k个星号点进行排列后分给剩余的k+1-p个基本有序树的叶子点,然后将n-2k-q个非星号点再进行排列后分给2k+1-p个位置上，其标号的方法数为

由pm≤q≤n-2k可知，标号森林Fk+1的个数为

2 RNA二级结构的计数

引理1[3]设在集合{1,2,…,n}上,具有k个碱基对且所有端环长度不小于正整数m的RNA二级结构的个数为Hn(k)， 则有：

下面讨论端环长度不小于正整数m的RNA二级结构计数的完全显示闭公式.

定理3设在集合{1,2,…,n}上含k个碱基对和p个端环的RNA二级结构的集合为A， 含有k+1个内点、n-2k个叶子点和p个外层内点的顶点数为n+1-k的有序树的集合为B， 则在A与B之间存在一个双射.

证明首先，以集合A中的1个RNA二级结构S构造集合B中的1个有序树T.令顶点u为树T的根.

1)若(i,j)是S的一个碱基对，且其包含的结构为一个分支，则把点i作为u的儿子内点；若i为一个外点，则将点i作为u的叶子点，并按S中原来的左右顺序进行排列；

2)若i是u的儿子内点，则去掉碱基对(i,j)， 并按步骤1)把(i,j)内部的所有外点和分支作为顶点i的儿子结点；

3)重复步骤2)，直至考虑完所有的碱基对为止.

其次，以集合B中的一个有序树T构造集合A中的一个RNA二级结构S.令T(u)为根结点u的所有儿子结点的集合.

1)对∀v∈T(u)， 如果v为T中的叶子点，则v在RNA二级结构中对应的点就是外点；如果v为内点，则v对应的点就是RNA中的一个分支，并按照它们原来的左右顺序插入到RNA二级结构中；

2)对T(u)中的内点p， 将T(p)中的所有点按照步骤1)均插入到(p,q)分支的内部；

3)重复步骤2)，直至考虑完所有的顶点为止.

由以上可证，集合A与B之间存在一个双射.

由定理3可得RNA二级结构与非标号有序树的对应关系,见表1.由表1和定理2可得定理4.

表1 RNA二级结构与非标号有序树的对应关系

注推论1的结论就是引理1递推关系式的完全显示闭公式.