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 F1and F2where niand di, for i ∈{1, 2}, denote the number of nodes in Fi and the degree of Fi, 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(n1n2d1d2(d1+ d2)) time and O(n1n2d1d2) 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 F1and F2in O(n1n2d1d2(d1+ d2)) time and O(n1n2d1d2) space. We show that our technique can improve the computation of the optimal local closed subforest alignment in O(n1n2(d1+ d2)2) time and O(n1n2(d1+ d2)) 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(n12n22(n1+ n2)) time and O(n1n2) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n1n2(d1+ d2)2) time and O(n1n2(d1+ d2)) space.