期刊
JOURNAL OF MATHEMATICAL BIOLOGY
卷 65, 期 6-7, 页码 1337-1357出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s00285-011-0493-6
关键词
-
资金
- National Science Foundation NSF [DMS-1016618, DMS-0817971]
- Digiteo Foundation
- VEGA
- APVV
- NSERC
- MITACS
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Mathematics of Information Technology and Complex Systems (MITACS)
- CONACYT
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1016618] Funding Source: National Science Foundation
Let S denote the set of (possibly noncanonical) base pairs {i, j} of an RNA tertiary structure; i.e. {i, j} is an element of S if there is a hydrogen bond between the ith and jth nucleotide. The page number of S, denoted pi(S), is the minimum number k such that S can be decomposed into a disjoint union of k secondary structures. Here, we show that computing the page number is NP-complete; we describe an exact computation of page number, using constraint programming, and determine the page number of a collection of RNA tertiary structures, for which the topological genus is known. We describe an approximation algorithm from which it follows that omega(S) <= pi(S) <= omega(S) . log n, where the clique number of S, omega(S), denotes the maximum number of base pairs that pairwise cross each other.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据