×

An IP algorithm for RNA folding trajectories. (English) Zbl 1443.92135

Schwartz, Russell (ed.) et al., 17th international workshop on algorithms in bioinformatics, WABI 2017, Boston, MA, USA, August 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 88, Article 6, 16 p. (2017).
Summary: Vienna RNA package software Kinfold implements the Gillespie algorithm for RNA secondary structure folding kinetics, for the move sets \(MS_1\) [resp. \(MS_2]\), 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 \(MS_2\) folding trajectory \(s=s_0, s_1,\ldots,s_m=t\), where each intermediate structure \(s_{i+1}\) is obtained from its predecessor by the addition, removal or shift of a single base pair. The shortest \(MS_1\) 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 \(MS_2\) 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/.
For the entire collection see [Zbl 1372.68022].

MSC:

92D20 Protein sequences, DNA sequences
90C10 Integer programming
92-04 Software, source code, etc. for problems pertaining to biology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Clote. Expected degree for RNA secondary structure networks. {\it J. Comput. Chem.}, 0(O):O, November 2014.
[2] P. Clote and A. Bayegan. Network Properties of the Ensemble of RNA Structures. {\it PLoS} {\it One}, 10(10):e0139476, 2015.
[3] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. {\it Algorithms}. McGraw-Hill, 1990. 1028 pages.
[4] I. Dotu, W. A. Lorenz, P. VAN Hentenryck, and P. Clote. Computing folding pathways between RNA secondary structures. {\it Nucleic. Acids. Res.}, 38(5):1711-1722, 2010.
[5] C. Flamm, I. L. Hofacker, P. F. Stadler, and M. Wolfinger. Barrier trees of degenerate landscapes. {\it Z. Phys. Chem.}, 216:155-173, 2002.
[6] :16
[7] D. T. Gillespie. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. {\it J. Comp. Phys.}, 22(403):403-434, 1976.
[8] F. W. Glover and M. Laguna. {\it Tabu Search}. Springer-Verlag, 1998. 408 p. · Zbl 0930.90083
[9] C. Hobartner and R. Micura. Bistable secondary structures of small RNAs and their struc tural probing by comparative imino proton NMR spectroscopy. {\it J. Mol. Biol.}, 325(3):421- 431, January 2003.
[10] D. B. Johnson. Finding all the elementary circuits of a directed graph. {\it SIAM J. Comput.}, 4:77-84, 1975. · Zbl 0275.05112
[11] Richard M. Karp. Reducibility among combinatorial problems. In {\it Proceedings of a sym-} {\it posium on the Complexity of Computer Computations, held March 20-22, 1972, at the} {\it IBM Thomas J. Watson Research Center, Yorktown Heights, New York}, pages 85-103, 1972. URL: http://www.cs.berkeley.edu/ luca/cs172/karp.pdf. · Zbl 1467.68065
[12] A. Kolmogoroff.Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung. {\it Mathematische Annalen}, 104:415-458, 1931. · JFM 57.0613.03
[13] 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. {\it Algorithms. Mol. Biol.}, 6:26, 2011.
[14] S. R. Morgan and P. G. Higgs. Barrier heights between ground states in a model of RNA secondary structure. {\it J. Phys. A: Math. Gen.}, 31:3153-3170, 1998. · Zbl 0923.92008
[15] D. Pörschke. Model calculations on the kinetics of oligonucleotide double-helix coil trans itions: Evidence for a fast chain sliding reaction. {\it Biophys Chem}, 2(2):83-96, August 1974.
[16] 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, {\it Structural} {\it Approaches to Sequence-Evolution}, page 3-36. Springer, Heidelberg, 2007.
[17] X. Tang, B. Kirkpatrick, S. Thomas, G. Song, and N. M. Amato. Using motion planning to study RNA folding kinetics. {\it J. Comput. Biol.}, 12(6):862-881, July/August 2005.
[18] C. Thachuk, J. Maňuch, L. Stacho, and A. Condon. NP-completeness of the direct energy barrier height problem. {\it Natural Computing}, 10(1):391-405, 2011. · Zbl 1257.68073
[19] A. Wagner. Robustness and evolvability: a paradox resolved. {\it Proc. Biol Sci.}, 275(1630):91- 100, January 2008.
[20] Michael T. Wolfinger, W. Andreas Svrcek-Seiler, Christoph Flamm, Ivo L. Hofacker, and Peter F. Stadler. Efficient folding dynamics of RNA secondary structures. {\it J. Phys. A:} {\it Math. Gen.}, 37:4731-4741, 2004. · Zbl 1050.81729
[21] A. Xayaphoummine, T. Bucher, and H. Isambert. Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots. {\it Nucleic. Acids.} {\it Res.}, 33(Web):W605-W610, July 2005.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.