RNA molecules whose secondary structures contain similar substructures often have similar
functions. Therefore, an important task in the study of RNA is to develop methods for
discovering substructures in RNA secondary structures that occur frequently (also referred
to as motifs). In this paper, we consider the problem of computing an optimal local alignment
of two given labeled ordered forests F
1 and F
2. This problem asks for a substructure of F
1
and a substructure of F
2 that exhibit a high similarity. Since an RNA molecule's secondary
structure can be represented as a labeled ordered forest, the problem we study has a direct
application to finding potential motifs. We generalize the previously studied concept of a
closed subforest to a gapped subforest and present the first algorithm for computing the
optimal local gapped subforest alignment of F
1 and F
2. We also show that our technique
can improve the time and space complexity of the previously most efficient algorithm for
optimal local closed subforest alignment. 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) and modify our main algorithm to
obtain a much faster algorithm for lssa than the one previously proposed. An implementation
of our algorithm is available at www.comp.nus.edu.sg/~bioinfo/LGSFAligner/. Its running
time is significantly faster than the original lssa program.
