A Fast longest crossing-plain preserving common subsequence algorithm
Kenawy, Tarek G.; Abdel-Rahman, Mohammad; Bahig, Hazem M.;
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.
Other data
Title | A Fast longest crossing-plain preserving common subsequence algorithm | Authors | Kenawy, Tarek G.; Abdel-Rahman, Mohammad ; Bahig, Hazem M. | Keywords | Arc-preserving common subsequence;Dynamic programming;Longest common subsequence;Pattern matching;RNA structure | Issue Date | 1-Oct-2022 | Journal | International Journal of Information Technology (Singapore) | Volume | 14 | Start page | 3019 | End page | 3029 | ISSN | 25112104 | DOI | 10.1007/s41870-022-01038-0 | Scopus ID | 2-s2.0-85136975771 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.