2026-08-27T21:20:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27515 2026-08-27T06:04:07Z ddc:004 open_access

FPT Learning of Sparse, Robust and Interpretable Generative Models of RNA Evolution Gardelle, Samuel Bulteau, Laurent Ponty, Yann RNA Structure prediction Evolution DCA Tree decomposition RNA structure modeling greatly benefits from the availability of structural homologs, associated with the presence of coevolving positions in multiple alignments. Direct Coupling Analysis (DCA) is a statistical framework for inferring significant covariations as Potts models, in a way that corrects for the transitive nature of mutual information. Various instances of DCA have been proposed over time with demonstrated ability to infer molecular contacts, yet were shown to be associated with inference algorithms that are invariably data hungry, prone to overfitting, and hindered by numerical instability. Recently, edge-activated DCA (eaDCA) has emerged as an alternative which iteratively infers couplings in a greedy manner and explicitly targets sparsity. In this work, we revisit the inference of eaDCA models in a rigorous algorithmic setting. We circumvent the #P-hardness of computing the most promising addition/update of coupling and provide exact fixed-parameter tractable algorithms for the treewidth parameter of the coupling-induced graph. We empirically show that eaDCA models are typically associated with moderate treewidth values, and validate the practical feasibility of the method by producing, in a matter of minutes, the models associated with 41 RFAM families associated with structured non-coding families. Our results reveal good recovery rates for couplings associated with conserved base pairs from the family consensus, and enable a more systematic and robust assessment of the potential of eaDCA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samuel Gardelle and Laurent Bulteau and Yann Ponty 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.11 urn:nbn:de:0030-drops-275155 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.11 eng https://creativecommons.org/licenses/by/4.0/legalcode