Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots

摘要

In this paper, we consider the problem of structural alignment of a target RNA sequence of length n and a query RNA sequence of length m with known secondary structure that may contain simple pseudoknots or embedded simple pseudoknots. The best known algorithm for solving this problem runs in O(mn^3) time for simple pseudoknot or O(mn^4) time for embedded simple pseudoknot with space complexity of O(mn^3) for both structures, which require too much memory making it infeasible for comparing noncoding RNAs (ncRNAs) with length several hundreds or more. We propose memory efficient algorithms to solve the same problem. We reduce the space complexity to O(n^3) for simple pseudoknot and O(mn^2 + n^3) for embedded simple pseudoknot while maintaining the same time complexity. We also show how to modify our algorithm to handle a restricted class of recursive simple pseudoknot which is found abundant in real data with space complexity of O(mn^2 + n^3) and time complexity of O(mn^4). Experimental results show that our algorithms are feasible for comparing ncRNAs of length more than 500.