**A Faster and More Space-Efficient Algorithm for Inferring
Arc-Annotations of RNA Sequences through Alignment**

*Jesper** Jansson,
See-Kiong Ng, Wing-Kin Sung and Hugo Willy*

The nested arc-annotation of a sequence is an important model used to
represent structural information for RNA and protein sequences. Given two
sequences S_{1} and S_{2} and a nested arc-annotation P_{1}
for S_{1}, this paper considers the problem of inferring the nested
arc-annotation P_{2} for S_{2} such that (S_{1},P_{1}) and (S_{2},P_{2}) have the
largest common substructure. The problem has a direct application in predicting
the secondary structure of an RNA sequence given a closely related sequence
with known secondary structure. The currently most efficient algorithm for this
problem requires O(nm^{3}) time and O(nm^{2})
space where n is the length of the sequence with known arc-annotation and m is
the length of the sequence whose arc-annotation is to be inferred. By using sparsification on a new recursive dynamic programming algorithm
and applying a Hirschberg-like traceback technique
with compression, we obtain an improved algorithm that runs in min{O(nm^{2}+n^{2}m),O(nm^{2}
log n), O(nm^{3})} time and min{O(m^{2} + mn),
O(m^{2} log n+n)} space.

References

*Jesper** Jansson,
See-Kiong Ng, Wing-Kin Sung and Hugo Willy.** ***A Faster and More
Space-Efficient Algorithm for Inferring Arc-Annotations of RNA Sequences
through Alignment, ***Algorithmica*, Volume 46,
Number 2 / October, 2006, pg 223-245

The basic WLCS program implemented in JAVA is available here. (full implementation of the backtracking is still not available)