RNA折叠中的最大公共嵌套子图

J4 ›› 2012, Vol. 47 ›› Issue (12): 57-63.

RNA折叠中的最大公共嵌套子图

刘国栋¹,王振佳²,刘丙强^2*

1.山东科技大学济南校区人力资源部, 山东济南 250031;
2.山东大学数学学院, 山东济南 250100

出版日期:2012-12-20 发布日期:2012-12-14
通讯作者: 刘丙强(1983- ),男,讲师,理学博士,研究方向为生物信息学. Email: bingqiang@sdu.edu.cn
作者简介:刘国栋(1981- ),男,讲师,理学硕士,研究方向为组合最优化. Email: lgd5261@163.com
基金资助:
山东省自然科学基金青年基金资助项目(ZR2011FQ010);山东科技大学科学研究“春蕾计划”项目(2010AZZ052);山东大学自主创新基金(2010GN028)

The largest common nested sub-graph in RNA folding

LIU Guo-dong¹, WANG Zhen-jia², LIU Bing-qiang^2*

1. Department of Human Resources, Shandong University of Science and Technology,
Jinan Campus, Jinan 250031, Shandong, China;
2. School of Mathematics, Shandong University, Jinan 250100, Shandong, China

Online:2012-12-20 Published:2012-12-14

摘要/Abstract

摘要：

在嵌套线状图模型中,寻找ncRNA联配的最大公共二次结构,实际就是寻找其序列导出线状图的最大公共嵌套线状子图。通过对模型的简化,证明该问题在伪平嵌套线状图的情形下是NP-完全的,并给出求最大水平嵌套线状子图的近似算法。

关键词: 线状图;嵌套;整子图;子序列;NP-完全

Abstract:

In the Nested Linear Graph model, the problem of finding the largest common secondary sequence of multiple ncRNA alignment is precisely the problem of finding the largest common nested linear sub-graph. By simplifying the model, it is proven that this problem is NP-Complete in the condition of pseudo-flat nested linear graph, and an approximate algorithm for the largest level nested linear sub-graph is given.

Key words: linear graph; nested; integral sub-graph; subsequence; NP-Complete

刘国栋1,王振佳2,刘丙强2*. RNA折叠中的最大公共嵌套子图[J]. J4, 2012, 47(12): 57-63.

LIU Guo-dong1, WANG Zhen-jia2, LIU Bing-qiang2*. The largest common nested sub-graph in RNA folding[J]. J4, 2012, 47(12): 57-63.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed