• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >Local Exact Pattern Matching for Non-FixedRNA Structures
【24h】

Local Exact Pattern Matching for Non-FixedRNA Structures

机译：非固定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^3k^2)$ time. Finally, we present an $O(n^3)$ algorithm for finding the most similar subforest between two nested RNAs.
机译：检测RNA的局部共有序列结构区域是生物学上的重要问题。检测这样的区域可以使生物学家识别被检查分子之间的功能相关的相似性。我们开发了动态编程算法来查找两个RNA之间的常见结构序列模式。 RNA由其序列和一组具有相关概率的潜在碱基对给出。与先前有关RNA局部模式匹配的工作相反，我们支持打破弧线。这使我们在仅匹配固定结构时增加了灵活性。可能仅匹配指定碱基对的相似子集。我们提出了一种$ O（n ^ 3）$算法，用于两个嵌套RNA之间的局部精确模式匹配，以及一种$ O（n ^ 3 log n）$算法，用于一个嵌套RNA和一个有界无限的RNA。另外，引入了一种近似模式匹配的算法，对于两个给定的嵌套RNA和一个数字$ k $，找到两个RNA之间最大的局部模式匹配得分，其中最大错配为$ O（n ^ 3k ^ 2）$时间。最后，我们提出了一种$ O（n ^ 3）$算法，用于在两个嵌套RNA之间找到最相似的子森林。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号