Local Exact Pattern Matching for Non-Fixed RNA Structures

被引:6
作者
Amit, Mika [1 ]
Backofen, Rolf [2 ,3 ]
Heyne, Steffen [4 ]
Landau, Gad M. [1 ,5 ]
Moehl, Mathias [4 ]
Otto, Christina [4 ]
Will, Sebastian [2 ,6 ,7 ]
机构
[1] Univ Haifa, Dept Comp Sci, IL-3498838 Haifa, Israel
[2] Univ Freiburg, Inst Comp Sci, D-79106 Freiburg, Germany
[3] Univ Freiburg, Ctr Biol Signaling Studies, D-79110 Freiburg, Germany
[4] Univ Freiburg, Inst Comp Sci, D-79110 Freiburg, Germany
[5] NYU, Polytech Sch Engn, Dept Comp Sci & Engn, Brooklyn, NY 11201 USA
[6] MIT, CSAIL, Cambridge, MA 02139 USA
[7] MIT, Dept Math, Cambridge, MA 02139 USA
基金
以色列科学基金会; 美国国家科学基金会;
关键词
Pattern matching; RNA local similarity; tree local similarity; sequence-structure matching; EDIT DISTANCE; TREE EDIT; ALIGNMENT; ALGORITHMS; GAPS;
D O I
10.1109/TCBB.2013.2297113
中图分类号
Q5 [生物化学];
学科分类号
070307 [化学生物学];
摘要
Detecting local common sequence-structure regions of RNAs is a biologically important problem. Detecting such regions allows biologists to identify functionally relevant similarities between the inspected molecules. We developed dynamic programming algorithms for finding common structure-sequence patterns between two RNAs. The RNAs are given by their sequence and a set of potential base pairs with associated probabilities. In contrast to prior work on local pattern matching of RNAs, we support the breaking of arcs. This allows us to add flexibility over matching only fixed structures; potentially matching only a similar subset of specified base pairs. We present an O(n(3)) algorithm for local exact pattern matching between two nested RNAs, and an O(n(3) log n) algorithm for one nested RNA and one bounded-unlimited RNA. In addition, an algorithm for approximate pattern matching is introduced that for two given nested RNAs and a number k, finds the maximal local pattern matching score between the two RNAs with at most k mismatches in O(n(3)k(2)) time. Finally, we present an O(n(3)) algorithm for finding the most similar subforest between two nested RNAs.
引用
收藏
页码:219 / 230
页数:12
相关论文
共 25 条
[1]
Amit M., 2012, P 23 ANN S COMB PAT, P306
[2]
[Anonymous], THESIS U ALBERTA
[3]
[Anonymous], 2004, J DISCRETE ALGORITHM, DOI DOI 10.1016/S1570-8667(03)00080-7
[4]
Locality and gaps in RNA comparison [J].
Backofen, Rolf ;
Chen, Shihyen ;
Hermelin, Danny ;
Landau, Gad M. ;
Roytberg, Mikhail A. ;
Weimann, Oren ;
Zhang, Kaizhong .
JOURNAL OF COMPUTATIONAL BIOLOGY, 2007, 14 (08) :1074-1087
[5]
Backofen R, 2009, LECT NOTES COMPUT SC, V5577, P236, DOI 10.1007/978-3-642-02441-2_21
[6]
A survey on tree edit distance and related problems [J].
Bille, P .
THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) :217-239
[7]
Blin G., 2011, ALGORITHMIC ASPECTS, P113
[8]
Small RNAs make big splash [J].
Couzin, J .
SCIENCE, 2002, 298 (5602) :2296-2297
[9]
An Optimal Decomposition Algorithm for Tree Edit Distance [J].
Demaine, Erik D. ;
Mozes, Shay ;
Rossman, Benjamin ;
Weimann, Oren .
ACM TRANSACTIONS ON ALGORITHMS, 2009, 6 (01)
[10]
Decomposition algorithms for the tree edit distance problem [J].
Dulucq, Serge ;
Touzet, Helene .
JOURNAL OF DISCRETE ALGORITHMS, 2005, 3 (2-4) :448-471