License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2017.6
URN: urn:nbn:de:0030-drops-76437
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7643/
Go to the corresponding LIPIcs Volume Portal

Bayegan, Amir H. ; Clote, Peter

An IP Algorithm for RNA Folding Trajectories

pdf-format:
LIPIcs-WABI-2017-6.pdf (0.9 MB)

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/.

BibTeX - Entry

@InProceedings{bayegan_et_al:LIPIcs:2017:7643,
  author =	{Amir H. Bayegan and Peter Clote},
  title =	{{ An IP Algorithm for RNA Folding Trajectories}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Russell Schwartz and Knut Reinert},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7643},
  URN =		{urn:nbn:de:0030-drops-76437},
  doi =		{10.4230/LIPIcs.WABI.2017.6},
  annote =	{Keywords: Integer programming, RNA secondary structure, folding trajectory, feedback vertex problem, conflict digraph}
}

Keywords: Integer programming, RNA secondary structure, folding trajectory, feedback vertex problem, conflict digraph
Collection: 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI