Gibbs/MCMC Sampling for Multiple RNA Interaction with Sub-optimal Solutions
| Autor: | Saad Mneimneh, Syed Ali Ahmed |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Computer science Applied Mathematics 0206 medical engineering Sampling (statistics) Approximation algorithm Markov chain Monte Carlo 02 engineering and technology symbols.namesake Metropolis–Hastings algorithm Genetics Bipartite graph symbols Combinatorial optimization Cluster analysis 020602 bioinformatics Biotechnology Gibbs sampling |
| Zdroj: | IEEE/ACM transactions on computational biology and bioinformatics. |
| ISSN: | 1557-9964 |
| Popis: | Multiple RNA interaction can be modeled as a problem in combinatorial optimization, where the “optimal” structure is driven by an energy-minimization-like algorithm. However, the actual structure may not be optimal in this computational sense. Moreover, it is not necessarily unique. Therefore, alternative sub-optimal solutions are needed to cover the biological ground. We present a combinatorial formulation for the Multiple RNA Interaction problem with approximation algorithms to handle various interaction patterns, which when combined with Gibbs sampling and Markov Chain Monte Carlo (MCMC), can efficiently generate a reasonable number of optimal and sub-optimal solutions. When viable structures are far from an optimal solution, exploring dependence among different parts of the interaction can increase their score and boost their candidacy for the sampling algorithm. By clustering the solutions, we identify a few representatives that are distinct enough to suggest possible alternative structures. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|