摘要
在嵌套线状图模型中,寻找ncRNA联配的最大公共二次结构,实际就是寻找其序列导出线状图的最大公共嵌套线状子图。通过对模型的简化,证明该问题在伪平嵌套线状图的情形下是NP-完全的,并给出求最大水平嵌套线状子图的近似算法。
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.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2012年第12期57-63,共7页
Journal of Shandong University(Natural Science)
基金
山东省自然科学基金青年基金资助项目(ZR2011FQ010)
山东科技大学科学研究"春蕾计划"项目(2010AZZ052)
山东大学自主创新基金(2010GN028)
关键词
线状图
嵌套
整子图
子序列
NP-完全
linear graph
nested
integral sub-graph
subsequence
NP-Complete
