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, nearoptimal 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:16:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770507},
ISSN = {18688969},
year = {2017},
volume = {88},
editor = {Russell Schwartz and Knut Reinert},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7643},
URN = {urn:nbn:de:0030drops76437},
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 