| On the page number of RNA secondary structures with pseudoknots. | |
| | |
MedLine Citation:
|
PMID: 22159642 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
Let [Formula: see text] denote the set of (possibly noncanonical) base pairs {i, j} of an RNA tertiary structure; i.e. [Formula: see text] if there is a hydrogen bond between the ith and jth nucleotide. The page number of [Formula: see text], denoted [Formula: see text], is the minimum number k such that [Formula: see text] 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 [Formula: see text], where the clique number of [Formula: see text], denotes the maximum number of base pairs that pairwise cross each other. |
| | |
Authors:
|
Peter Clote; Stefan Dobrev; Ivan Dotu; Evangelos Kranakis; Danny Krizanc; Jorge Urrutia |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-12-10 |
Journal Detail:
|
Title: Journal of mathematical biology Volume: - ISSN: 1432-1416 ISO Abbreviation: - Publication Date: 2011 Dec |
Date Detail:
|
Created Date: 2011-12-13 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 7502105 Medline TA: J Math Biol Country: - |
Other Details:
|
Languages: ENG Pagination: - Citation Subset: - |
Affiliation:
|
Department of Biology, Boston College, Chestnut Hill, MA, 02467, USA, clote@bc.edu. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Tripeptide self-assembled hydrogels: unexpected twists of chirality.
Next Document: Open-ended TiO(2) nanotubes formed by two-step anodization and their application in dye-sensitized s...