Local gapped subforest alignment and its application in finding RNA structural motifs

We consider the problem of computing an optimal local alignment of two labeled ordered forests F-1 and F-2 where n(i) and d(i), for i is an element of {1, 2}, denote the number of nodes in F-i and the degree of F-i, respectively; and its applications in finding RNA structural motifs. A previous result is the local closed subforest alignment problem, which can be solved in O(n(1)n(2)d(1)d(2)(d(1) + d(2))) time and O(n(1)n(2)d(1)d(2)) space. This paper generalizes the concept of a closed subforest to a gapped subforest and then presents an algorithm for computing the optimal local gapped subforest alignment of F1 and F2 in O(n(1)n(2)d(1)d(2)(d(1) + d(2))) time and O(n(1)n(2)d(1)d(2)) space. We show that our technique can improve the computation of the optimal local closed subforest alignment in O(n(1)n(2)(d(1) + d(2))(2)) time and O(n(1)n(2)(d(1) + d(2))) space. Furthermore, we prove that a special case of our local gapped subforest alignment problem is equivalent to a problem known in the literature as the local sequence-structure alignment problem (lssa). The previously best algorithm for lssa uses O(n(1)(2)n(2)(2)(n(1) + n(2))) time and O(n(1)n(2)) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n(1)n(2)(d(1) + d(2))(2)) time and O(n(1)n(2)(d(1) + d(2))) space.