Local Exact Pattern Matching for Non-Fixed RNA Structures
Local Exact Pattern Matching for Non-Fixed RNA Structures
复制标题
DOI：
10.1109/tcbb.2013.2297113
复制
发表时间：
2014-01-01
影响因子：
4.5
通讯作者：
Will, Sebastian
中科院分区：
文献类型：
--
作者：
Amit, Mika;Backofen, Rolf;Will, Sebastian
检测RNA的局部共同序列结构区域是一个重要的生物学问题。通过检测这些区域，生物学家可以确定被检查分子之间在功能上的相似之处。我们开发了动态规划算法来寻找两个RNA之间的共同结构-序列模式。RNA由它们的序列和一组具有相关概率的潜在碱基对给出。与以往在RNA局部模式匹配方面的工作不同，我们支持打断弧线。这使我们能够增加灵活性，而不是只匹配固定结构；潜在地只匹配指定碱基对的类似子集。给出了两个嵌套RNA之间的局部精确模式匹配的O(n(3))算法，以及一个嵌套RNA和一个有界无限RNA的O(n(3)logn)算法。此外，还提出了一种近似模式匹配算法，对于给定的两个嵌套RNA和k个数，在O(n(3)k(2))时间内找到两个最多k个不匹配的RNA之间的最大局部模式匹配分数。最后，我们给出了一个O(n(3))算法来寻找两个嵌套RNA之间最相似的子森林。
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.