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 ∈ {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_1n_2d_1d_2(d_1 + d_2)) time and O(n_1n_2d_1d_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 F_1 and F_2 in O(n_1n_2d_1d_2(d_1 + d_2)) time and O(n_1n_2d_1d_2) space. We show that our technique can improve the computation of the optimal local closed subforest alignment in O(n_1n_2(d_1 + d_2)~2) time and O(n_1n_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~2n_2~2(n_1 + n_2)) time and O(n_1n_2) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n_1n_2(d_1 + d_2)~2) time and O(n_1n_2(d_1 + d_2)) space.