Rivas-Eddy RNA二级结构图书嵌入分类的实现方法  

Realization of book embedding for Rivas-Eddy RNA secondary structures

作　　者：高世乐[1] 丁克诠[1] 

机构地区：[1]大连理工大学电子与信息工程学院,辽宁大连116024

出　　处：《计算机工程与应用》2008年第4期20-23,72,共5页Computer Engineering and Applications

基　　金：生物信息学研究(the Nature Science Foundation of China under Grant No.A0324670)

摘　　要：书嵌入数是对图进行分类的一个拓扑标准,通常来说,计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题。针对Rivas-Eddy(R&E)类中RNA分子的二级结构图,从二级结构图的语法出发,通过其交叉关系图的点着色,构造性地得到了RNA分子二级结构图书嵌入的具体实现方法,完成了对RNA分子二级结构的书嵌入分类。该方法具有多项式时间复杂性,为求解NP完全问题提供了有益的参考。Book-thickness is regarded as a topological standard to classify graphs.In general,it is a NP-complete problem to calculate the book-thickness of a graph or embed it into a book.In this paper,a book-embedding scheme is constructively obtained for the RNA secondary structures in Rivas-Eddy class by using the secondary-structure graphic grammar and the vertex coloring of the cross-relation graph,and the book-embedding classification can be performed furthermore.This method has a polynomial time complexity,which can provide useful reference to solving the NP-complete problems.

关 键 词：假结 RNA二级结构 书嵌入 点着色 团数 色数 完美图 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构] Q71[自动化与计算机技术—计算机科学与技术]