计算生物学中的组合结构研究

Computational biology is one of the most vigorous frontier in life science，it illustrates the nature of various life phenomena by studying the structure, function and biosynthesis of biological macromolecules (such as Protein and RNA et al). By their nature, structures of Protein and RNA can be abstracted to combinatorial objects: contact map. Contact map is closely related to matchings and set partitions. By studying the related enumeration problem of contact map, we can obtain different recursive structures, which imply different structure prediction algorithms. The genus is a positive integer number whose value quantifies the topological complexity of the folded Protein and RNA structure. Recent study results show that even for large RNA, the genus remains very small. Thus, it becomes meaningful to study the enumeration problem of contact map with genus constraints. In this project, we will use combinatorial and analysis methods to study the enumeration of extended RNA structures, contact maps and chord diagrams on many intervals with given genus, such as their generating functions, recursive relations and asymptotic formulas. We will consider the relationship between genus and crossing number and nesting number, study the joint distribution function of crossing number and nesting number on matchings, set partitions with given genus. It will bring lots of research objects to combinatorics and promote the development of combinatorics.

计算生物学是当今生命科学最具活力的新兴前沿领域之一，它通过研究生物大分子(蛋白质、RNA)的结构、功能和生物合成等方面来阐明各种生命现象的本质。蛋白质和RNA的分子结构天然地可以抽象为一种组合结构——关联图结构。关联图与组合数学中的集合划分、匹配等经典组合结构密切相关，通过研究关联图相关的组合计数问题可以得到结构预测算法的不同递归结构。亏格是一种度量蛋白质和RNA折叠的拓扑复杂程度的统计量，最新研究表明RNA分子结构通常具有较低的亏格，因此研究带亏格约束的关联图计数问题就变得非常有意义。本项目将利用组合数学和分析的工具和方法，研究给定亏格的扩展RNA结构、一般关联图和多区间弦图的组合计数问题，如生成函数、递推关系、渐进计数公式等，同时考察匹配和集合划分上亏格与交叉数、嵌套数的关系，研究给定亏格的匹配、集合划分上交叉数和嵌套数的联合分布生成函数。相关研究将进一步丰富组合数学的研究对象。

关联图是描述蛋白质和RNA分子结构不同折叠方式的基本模型，不同的关联图通常对应着蛋白质和RNA的不同折叠方式，从而最终决定它们不同的功能。对关联图中的团、匹配和线性森林结构的极值问题研究将对生物大分子的功能理解和合成具有一定的指导意义。在项目执行期间，项目负责人与他人合作主要针对蛋白质在三维六角棱柱晶格模型中的近似折叠算法、图中的生成线性森林图兰型问题和图与超图中的匹配图兰型问题等进行了研究，主要成果有：给出了蛋白质在三维六角棱柱晶格中的近似比为1/3的近似折叠算法；应用极值集合论中的移位方法确定了给定匹配数的图中最大s-团个数和给定匹配数的r-一致超图中的最大s-团个数；采用闭包方法确定了给定线性森林大小的图中最大边数，证明了Erdos-Gallai匹配定理的稳定性；应用直积上的EKR型定理确定了不含s-匹配和q-团的k一致超图中的最大边数等。在理论上，相关研究结果与极值集合论中的Erdos匹配猜想密切相关，具有重要的理论研究意义。在计算生物学角度，相关研究结果对理解给定匹配数的关联图结构具有一定的指导意义，进而对蛋白质和RNA分子的功能理解和合成具有一定的指导意义。