A Fast longest crossing-plain preserving common subsequence algorithm

Abstract

In molecular biology, the comparison of ribonucleic acid (RNA) structures is important in predicting RNA folding and exploring RNA conserved and consensus structures. One of the frameworks used to study the RNA structure comparison is the longest arc-preserving common subsequence (LAPCS). In this framework, given two RNA structures represented as two arc-annotated sequences, (X, PX) and (Y, PY) , where (1) X and Y are the sequences of nucleotides over Σ = { A , C , G , U } and (2) PX and PY are the set of arcs that represent the chemical bonds between complementary bases. The goal of the LAPCS problem is to determine the maximal length of the common subsequence of X and Y preserving all the arcs that link a subsequence of nucleotides. In this paper, we developed a fast heuristic algorithm for LAPCS in which the two types of arc-annotated sequence are CROSSING and PLAIN. The algorithm is based on dynamic programming and a lookup table, and runs in O(nm) , where n and m are the lengths of the sequences. The experiments on artificial data, consisting of different sequence lengths and number of arcs showed that the proposed algorithm outperformed the fastest known heuristic algorithm for the LAPCS problem in terms of both time complexity and output length. Specifically, the proposed algorithm achieved, on average, a 96% improvement in running time and was able to generate a LAPCS that was better in terms of length.