Summarizing RNA Structural Ensembles via Maximum Agreement Secondary Structures.

Authors

Xinyu Gu, Stefan Ivanovic, Daniel W Feng, Mohammed El-Kebir

Published in

Journal of computational biology : a journal of computational molecular cell biology. Pages 15578666261486480. Sep 15, 2026. Epub Sep 15, 2026.

Abstract

Summarizing a collection $P$ of related RNA secondary structures is a key challenge in applications like evolutionary analysis, alternative fold studies and mRNA vaccine design. This requires both clustering the input structures into similar groups and identifying the core structural motifs on which they agree or differ. Existing methods fail by focusing on only one of these goals: clustering methods do not output shared motifs, while consensus methods overlook the structural diversity present in the collection. Here, we introduce the Maximum Agreement Secondary Structures (MASS) problem, which seeks the largest set F of structural features present in $P$ that partition the input structures into a user-specified number $\tau$ of distinct clusters. We prove that MASS is NP-hard and also establish its equivalence to a constrained binary matrix projection problem. We present an exact integer linear program, an exact combinatorial algorithm, and a scalable beam-search heuristic. Using simulations we demonstrate the performance of these exact algorithms and heuristics relative to baseline methods that focus on either clustering or identifying a single consensus tree. On real data, we demonstrate that MASS identifies conserved scaffolds in conformational datasets, reveals conserved structural motifs in different species within RNA families, and recovers shared structural features among synonymous transcripts encoding the same protein. MASS provides a general and interpretable framework for summarizing RNA structural organization.

PMID:
42742330
Bibliographic data and abstract were imported from PubMed on 15 Sep 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.