Component-Based Matching for Multiple Interacting RNA Sequences

摘要

RNA interactions are fundamental to a multitude of cellular processes including post-transcriptional gene regulation. Although much progress has been made recently at developing fast algorithms for predicting RNA interactions, much less attention has been devoted to the development of efficient algorithms and data structures for locating RNA interaction patterns. We present two algorithms for locating all the occurrences of a given interaction pattern in a set of RNA sequences. The baseline algorithm implements an exhaustive backtracking search. The second algorithm also finds all the matches, but uses additional data structures in order to considerably decrease the execution time, sometimes by one order of magnitude. The worst case memory requirement for the later algorithm increases exponentially with the input pattern length and does not depend on the database size, making it practical for large databases. The performance of the algorithms is illustrated with an application for locating RNA elements in a Diplonemid genome.