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

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (4): 20-23.

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

高世乐,丁克诠

大连理工大学电子与信息工程学院，辽宁大连 116024

收稿日期:2007-09-24 修回日期:2007-10-30 出版日期:2008-02-01 发布日期:2008-02-01
通讯作者: 高世乐

Realization of book embedding for Rivas-Eddy RNA secondary structures

GAO Shi-le,DING Ke-quan

School of Electronic and Information Engineering，Dalian University of Technology，Dalian，Liaoning 116024，China

Received:2007-09-24 Revised:2007-10-30 Online:2008-02-01 Published:2008-02-01
Contact: GAO Shi-le

摘要/Abstract

摘要： 书嵌入数是对图进行分类的一个拓扑标准，通常来说，计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题。针对Rivas-Eddy（R&E）类中RNA分子的二级结构图，从二级结构图的语法出发，通过其交叉关系图的点着色，构造性地得到了RNA分子二级结构图书嵌入的具体实现方法，完成了对RNA分子二级结构的书嵌入分类。该方法具有多项式时间复杂性，为求解NP完全问题提供了有益的参考。

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

Abstract: ook-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.

Key words: pseudoknots, RNA secondary structures, book embedding, vertex coloring, clique number, chromatic number, perfect graphs

高世乐,丁克诠. Rivas-Eddy RNA二级结构图书嵌入分类的实现方法[J]. 计算机工程与应用, 2008, 44(4): 20-23.

GAO Shi-le,DING Ke-quan. Realization of book embedding for Rivas-Eddy RNA secondary structures[J]. Computer Engineering and Applications, 2008, 44(4): 20-23.