Sparse RNA folding: Time and space efficient algorithms

The currently fastest algorithm for RNA Single Strand Folding   requires O(nZ)O(nZ) time and Θ(n2)Θ(n2) space, where n denotes the length of the input string and Z   is a sparsity parameter satisfying n⩽Z