Sparse RNA folding: Time and space efficient algorithms

The currently fastest algorithm for RNA Single Strand Folding requires O(nZ) time and Theta(n(2)) space, where n denotes the length of the input string and Z is a sparsity parameter satisfying n <= Z < n(2). We show how to reduce the time and space complexities of this algorithm in the sparse case. The space reduction is based on the observation that some solutions for sub-instances are not examined after a certain stage of the algorithm, and may be discarded from memory. The running time speed up is achieved by combining two independent sparsification criteria, which restrict the number of expressions that need to be examined in bottleneck computations of the algorithm. This yields an O(n(2) + P Z) time and Theta(Z) space algorithm, where P is a sparsity parameter satisfying P < n <= Z <= n(P + 1). For the base-pairing maximization variant, the time complexity is further reduced to O(LZ), where L denotes the maximum number of base-pairs in a folding of the input string and satisfies L <= n\2. The presented techniques also extend to the related RNA Simultaneous Alignment and Folding problem. For an input composed of two strings of lengths n and m, the time and space complexities are reduced from O(nm (Z) over tilde) and Theta(n(2)m(2)) down to O(n(2)m(2) + (P) over tilde(Z) over tilde) and Theta(nm(2) + (Z) over tilde) respectively, where (Z) over tilde and (P) over tilde are sparsity parameters satisfying (P) over tilde < nm <= (Z) over tilde <nm(<(P)over tilde> + 3). A preliminary extended abstract of this work previously appeared in Backofen et al. (2009) [5]. Code implementations (in Java) may be downloaded from: http://www.cs.bgu.ac.il/similar to zakovs/RNAfold/SparseFold. zip. (C) 2010 Elsevier B. V. All rights reserved.