Document Open Access Logo

An IP Algorithm for RNA Folding Trajectories

Authors Amir H. Bayegan, Peter Clote

PDF
Thumbnail PDF

File

LIPIcs.WABI.2017.6.pdf
  • Filesize: 0.86 MB
  • 16 pages

Document Identifiers

Author Details

Amir H. Bayegan
Peter Clote

Cite As Get BibTex

Amir H. Bayegan and Peter Clote. An IP Algorithm for RNA Folding Trajectories. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.WABI.2017.6

Abstract

Vienna RNA Package software Kinfold implements the Gillespie algorithm for RNA secondary structure folding kinetics, for the move sets MS1 [resp. MS2], consisting of base pair additions and removals [resp. base pair addition, removals and shifts]. In this paper, for arbitrary secondary structures s, t of a given RNA sequence, we present the first optimal algorithm to compute the shortest MS2 folding trajectory s = s0, s1, . . . , sm = t, where each intermediate structure si+1 is obtained from its predecessor by the addition, removal or shift of a single base pair. The shortest MS1 trajectory between s and t is trivially equal to the number of base pairs belonging to s but not t, plus the number of base pairs belonging to t but not s. Our optimal algorithm applies integer programming (IP) to solve (essentially) the minimum feedback vertex set (FVS) problem for the "conflict digraph" associated with input secondary structures s, t, and then applies topological sort, in order to generate an optimal MS2 folding pathway from s to t that maximizes the use of shift moves. Since the optimal algorithm may require excessive run time, we also sketch a fast, near-optimal algorithm (details to appear elsewhere). Software for our algorithm will be publicly available at http://bioinformatics.bc.edu/clotelab/MS2distance/.

Subject Classification

Keywords
  • Integer programming
  • RNA secondary structure
  • folding trajectory
  • feedback vertex problem
  • conflict digraph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. Clote. Expected degree for RNA secondary structure networks. J. Comput. Chem., 0(O):O, November 2014. Google Scholar
  2. P. Clote and A. Bayegan. Network Properties of the Ensemble of RNA Structures. PLoS One, 10(10):e0139476, 2015. Google Scholar
  3. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Algorithms. McGraw-Hill, 1990. 1028 pages. Google Scholar
  4. I. Dotu, W. A. Lorenz, P. VAN Hentenryck, and P. Clote. Computing folding pathways between RNA secondary structures. Nucleic. Acids. Res., 38(5):1711-1722, 2010. Google Scholar
  5. C. Flamm, I. L. Hofacker, P. F. Stadler, and M. Wolfinger. Barrier trees of degenerate landscapes. Z. Phys. Chem., 216:155-173, 2002. Google Scholar
  6. D. T. Gillespie. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J. Comp. Phys., 22(403):403-434, 1976. Google Scholar
  7. F. W. Glover and M. Laguna. Tabu Search. Springer-Verlag, 1998. 408 p. Google Scholar
  8. C. Hobartner and R. Micura. Bistable secondary structures of small RNAs and their structural probing by comparative imino proton NMR spectroscopy. J. Mol. Biol., 325(3):421-431, January 2003. Google Scholar
  9. D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4:77-84, 1975. Google Scholar
  10. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, pages 85-103, 1972. URL: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
  11. A. Kolmogoroff. Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung. Mathematische Annalen, 104:415-458, 1931. Google Scholar
  12. R. Lorenz, S. H. Bernhart, C. Höner zu Siederdissen, H. Tafer, C. Flamm, P. F. Stadler, and I. L. Hofacker. Viennarna Package 2.0. Algorithms. Mol. Biol., 6:26, 2011. Google Scholar
  13. S. R. Morgan and P. G. Higgs. Barrier heights between ground states in a model of RNA secondary structure. J. Phys. A: Math. Gen., 31:3153-3170, 1998. Google Scholar
  14. D. Pörschke. Model calculations on the kinetics of oligonucleotide double-helix coil transitions: Evidence for a fast chain sliding reaction. Biophys Chem, 2(2):83-96, August 1974. Google Scholar
  15. P. Schuster and P. F. Stadler. Modeling conformational flexibility and evolution of structure: RNA as an example. In U. Bastille, M. Roman, and M. Vendruscolo, editors, Structural Approaches to Sequence-Evolution, page 3–36. Springer, Heidelberg, 2007. Google Scholar
  16. X. Tang, B. Kirkpatrick, S. Thomas, G. Song, and N. M. Amato. Using motion planning to study RNA folding kinetics. J. Comput. Biol., 12(6):862-881, July/August 2005. Google Scholar
  17. C. Thachuk, J. Maňuch, L. Stacho, and A. Condon. NP-completeness of the direct energy barrier height problem. Natural Computing, 10(1):391-405, 2011. Google Scholar
  18. A. Wagner. Robustness and evolvability: a paradox resolved. Proc. Biol Sci., 275(1630):91-100, January 2008. Google Scholar
  19. Michael T. Wolfinger, W. Andreas Svrcek-Seiler, Christoph Flamm, Ivo L. Hofacker, and Peter F. Stadler. Efficient folding dynamics of RNA secondary structures. J. Phys. A: Math. Gen., 37:4731-4741, 2004. Google Scholar
  20. A. Xayaphoummine, T. Bucher, and H. Isambert. Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots. Nucleic. Acids. Res., 33(Web):W605-W610, July 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact