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

Abstract

We consider the problem of computing an optimal local alignment of two labeled ordered forests F1 and F2 where ni and 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(n1n2d1d 2(d1 + d2)) time and O(n1n 2d1d2) 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 F2 in O(n1n2d 1d2(d1 + d2)) time and O(n 1n2d1d2) 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 + 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(n1 2n 2 2(n1 + n2)) time and O(n 1n2) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n1n2(d 1 + d2)2) time and O(n1n 2(d1 + d2)) space. © Springer-Verlag 2004.