rnapagenumber

rnapagenumber computes the optimal page number π(S) of RNA pseudoknotted and tertiary structures to quantify their topological complexity for structure analysis.

Key Features:

• Page Number Computation: Computes π(S), the minimum k such that a set of base pairs S = {(i, j)} can be decomposed into k disjoint secondary structures representing hydrogen-bonded nucleotide pairs.
• Constraint Programming: Uses constraint programming (CP) to obtain exact solutions for the NP-complete page number problem.
• Approximation Algorithm: Implements an approximation algorithm that establishes bounds ω(S) ≤ π(S) ≤ ω(S) · log n, where ω(S) is the clique number of S (maximum number of pairwise-crossing base pairs).
• Input Formats: Accepts structural input in PDB and .ct (mfold connect) file formats.

Scientific Applications:

• RNA Structure Analysis: Quantifies topological complexity of RNA tertiary and pseudoknotted structures to inform studies of folding patterns and topology.
• Genomic Research: Supports analysis of RNA structures with known topological genus relevant to studies of gene expression and regulation.
• Algorithmic Biology: Provides exact and approximate computations useful for developing and testing algorithms for RNA structure prediction and analysis.

Methodology:

Performs exact page number computation using constraint programming and an approximation algorithm that applies clique-number-based bounds ω(S) ≤ π(S) ≤ ω(S) · log n; accepts PDB and .ct (mfold connect) inputs.