Exact Learning of RNA Energy Parameters From Structure
This work addresses the challenge of parameter estimation in RNA energy models for computational biology, presenting an incremental theoretical and algorithmic contribution.
The paper tackles the problem of exactly learning RNA energy parameters from secondary structure data by deriving a necessary and sufficient condition based on convex hull computations, and it demonstrates that selecting a maximal subset of training data satisfying this condition is NP-hard. Using a randomized greedy algorithm on the RNA STRAND v2.0 database, they learn parameters that align with experimentally measured Turner parameters for base pairs.
We consider the problem of exact learning of parameters of a linear RNA energy model from secondary structure data. A necessary and sufficient condition for learnability of parameters is derived, which is based on computing the convex hull of union of translated Newton polytopes of input sequences. The set of learned energy parameters is characterized as the convex cone generated by the normal vectors to those facets of the resulting polytope that are incident to the origin. In practice, the sufficient condition may not be satisfied by the entire training data set; hence, computing a maximal subset of training data for which the sufficient condition is satisfied is often desired. We show that problem is NP-hard in general for an arbitrary dimensional feature space. Using a randomized greedy algorithm, we select a subset of RNA STRAND v2.0 database that satisfies the sufficient condition for separate A-U, C-G, G-U base pair counting model. The set of learned energy parameters includes experimentally measured energies of A-U, C-G, and G-U pairs; hence, our parameter set is in agreement with the Turner parameters.