|
|||||
|
|
| RNA折叠中的最大公共嵌套子图 | |
| 引用本文： | 刘国栋,王振佳,刘丙强. RNA折叠中的最大公共嵌套子图[J]. 山东大学学报(理学版), 2012, 47(12): 57-63 |
| 作者姓名： | 刘国栋 王振佳 刘丙强 |
| 作者单位： | 1.山东科技大学济南校区人力资源部, 山东 济南 250031; 2.山东大学数学学院, 山东 济南 250100 |
| 基金项目： | 山东省自然科学基金青年基金资助项目(ZR2011FQ010);山东科技大学科学研究“春蕾计划”项目(2010AZZ052);山东大学自主创新基金(2010GN028) |
| 摘 要： | 在嵌套线状图模型中,寻找ncRNA联配的最大公共二次结构,实际就是寻找其序列导出线状图的最大公共嵌套线状子图。通过对模型的简化,证明该问题在伪平嵌套线状图的情形下是NP-完全的,并给出求最大水平嵌套线状子图的近似算法。 |
| 关 键 词： | 线状图 嵌套 整子图 子序列 NP-完全, |
The largest common nested sub-graph in RNA folding |
|
| LIU Guo-dong,WANG Zhen-jia,LIU Bing-qiang. The largest common nested sub-graph in RNA folding[J]. Journal of Shandong University, 2012, 47(12): 57-63 | |
| Authors: | LIU Guo-dong WANG Zhen-jia LIU Bing-qiang |
| Affiliation: | 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 |
| 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. |
| Keywords: | linear graph nested integral sub-graph subsequence NP-Complete, |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 | |
| 点击此处可从《山东大学学报(理学版)》下载全文 | |