Time and Space Efficient Algorithms for RNA Folding with the Four-Russians Technique

2015/03/19 by Song, Yinglei
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1503.05670

Abstract

In this paper, we develop new algorithms for the basic RNA folding problem. Given an RNA sequence that contains n nucleotides, the goal of the problem is to compute a pseudoknot-free secondary structure that maximizes the number of base pairs in the sequence. We show that there exists a dynamic programming algorithm that can solve the problem in time O(\fracn³log₂n) while using only O(\fracn²log₂n) memory space. In addition, we show that the time complexity of this algorithm can be further improved to O(\fracn³log₂²n) at the expense of a slightly increased space complexity. To the best of our knowledge, this is the first algorithm that can solve the problem with traditional dynamic programming techniques in time O(\fracn³log₂²n). In addition, our results improve the best known upper bound of the space complexity for efficiently solving both this problem and the context-free language recognition problem.

Related

• Faster Algorithms for RNA-folding using the Four-Russians method
• Hardness of RNA Folding Problem with Four Symbols
• A dynamic programming algorithm for RNA structure prediction including pseudoknots
• Minimum length RNA folding trajectories
• On the combinatorics of sparsification