Many computational problems concerning RNA pseudoknot structures, most prominently their prediction and alignment, are NP-hard. For structure prediction, several algorithms have been proposed that are restricted to certain classes of pseudoknots in order to run efficiently. We present a general scheme that yields an efficient alignment algorithm for arbitrary classes of pseudoknots that can be predicted efficiently by dynamic programming. Moreover, we show that such an alignment algorithm benefits from restrictions to certain structure classes in the same way as structure prediction algorithms do. We look at five of these classes in greater detail. Compared to the respective structure prediction algorithm, the time and space complexity of the obtained alignment algorithm is increased by only a linear factor. For four of the classes, there do not exist alignment algorithms so far. For the fifth, most general class, our algorithm improves the time complexity compared to the best algorithm known so far, from $O(n^5m^5)$ time to $O(nm^6)$, where $n$ and $m$ are the length of the two aligned sequences. Finally, we apply the fastest of the generated algorithms with complexity $O(nm^4)$ time and $O(nm^2)$ space to comparative de-novo prediction of pseudoknots.
Download PDF Show BibTeX
Login to edit