Research map / Learning theory and algorithms / Combinatorial and search optimization
Enforcing Constraints in RNA Secondary Structure Predictions: A Post-Processing Framework Based on the Assignment Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a post-processing step that casts RNA secondary structure constraint enforcement as a linear sum assignment problem solved exactly by the Jonker-Volgenant/Hungarian algorithm, guaranteeing zero constraint violations on top of E2Efold and REDfold score networks.
Problem
ML-based RNA secondary structure predictors output matrices that violate hard RNA constraints (allowed base pairs, no sharp loops, no overlapping pairs), and existing post-processing (E2Efold, RED PP, Blossom) fails to guarantee validity and is slow.
Approach
Shows that the constrained post-processing optimization over RNA contact matrices is equivalent to a linear sum assignment problem with a carefully designed cost matrix (masked, negated, scaled score matrix), so an exact polynomial-time LSAP solver yields valid structures with optimal score.
Key results
- On RNAStrAlign, REDfold + Ours reaches F1 0.918 vs 0.917 for REDfold + Blossom and 0.904 for REDfold + RED PP, with zero constraint violations.
- E2Efold + Ours yields 0% violations on C2-C4 across both datasets, while E2Efold + E2E PP has 56.8% (RNAStrAlign) and 58.3% (ncRNA) C4 violations.
- Post-processing runtime is 0.014 s per sequence for REDfold + Ours on RNAStrAlign versus 0.496 s for REDfold + Blossom.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add assignment-based post-processing instead of RED PP | REDfold · RNAStrAlign test | F1: 0.904 -> 0.918 | Helped |
| Add assignment-based post-processing instead of RED PP | REDfold · ncRNA test | F1: 0.844 -> 0.847 | Helped |
| Add assignment-based post-processing instead of RED PP | REDfold · ncRNA pseudoknot sequences | F1: 0.810 -> 0.818 | Helped |
| Add assignment-based post-processing instead of E2E PP | E2Efold · RNAStrAlign test | F1: 0.809 -> 0.822 | Helped |
| Add assignment-based post-processing instead of E2E PP | E2Efold · ncRNA test | F1: 0.595 -> 0.608 | Helped |
| Add assignment-based post-processing instead of E2E PP | E2Efold · ncRNA pseudoknot sequences | F1: 0.603 -> 0.616 | Helped |
| Use assignment-based post-processing rather than E2E PP | E2Efold · RNAStrAlign | constraint violations (C2, C3, C4): 0%, 10.3%, 56.8% -> 0%, 0%, 0% | Helped |
| Use assignment-based post-processing rather than RED PP | REDfold · RNAStrAlign | constraint violations (C2, C3, C4): 0%, 0.6%, 0% -> 0%, 0%, 0% | Helped |
Surprising findings
- The E2Efold post-processing (E2E PP) and Blossom post-processing fail to enforce constraints despite being designed for them, with substantial violation rates.
Limitations
- Two-stage design disconnects the computational graph so the backbone is not trained with the post-processing step.
- Cubic O(L^3) complexity of the assignment solver may be too slow for very long RNAs.
- Only enforces constraints as post-processing; the score network is not aware of the constraints.
Experimental setup
Datasets: RNAStrAlign ncRNA (Rfam)
Benchmarks: RNAStrAlign ncRNA
Metrics: F1 precision recall constraint violation rate running time
Baselines: RNAfold RNAstructure CONTRAfold SPOT-RNA MXfold2 E2Efold + E2E PP E2Efold + Blossom REDfold + RED PP REDfold + Blossom
Builds on: E2Efold REDfold Blossom post-processing Hungarian algorithm
Closest papers by meaning
- Deciphering RNA Secondary Structure Prediction: A Probabilistic K-Rook Matching Perspective (ICML 2024 · similarity 0.90)
- PriFold: Biological Priors Improve RNA Secondary Structure Predictions (AAAI 2025 · similarity 0.87)
- RDesign: Hierarchical Data-efficient Representation Learning for Tertiary Structure-based RNA Design (ICLR 2024 · similarity 0.86)
- Beyond Sequence: Impact of Geometric Context for RNA Property Prediction (ICLR 2025 · similarity 0.86)
- RiboFlow: Conditional De Novo RNA Co-Design via Synergistic Flow Matching (NeurIPS 2025 · similarity 0.86)
- RNAFlow: RNA Structure & Sequence Design via Inverse Folding-Based Flow Matching (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.