• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >Heuristic Reusable Dynamic Programming: Efficient Updates of Local Sequence Alignment
【24h】

Heuristic Reusable Dynamic Programming: Efficient Updates of Local Sequence Alignment

机译：启发式可重用动态编程：局部序列比对的有效更新

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Recomputation of the previously evaluated similarity results between biological sequences becomes inevitable when researchers realize errors in their sequenced data or when the researchers have to compare nearly similar sequences, e.g., in a family of proteins. We present an efficient scheme for updating local sequence alignments with an affine gap model. In principle, using the previous matching result between two amino acid sequences, we perform a forward-backward alignment to generate heuristic searching bands which are bounded by a set of suboptimal paths. Given a correctly updated sequence, we initially predict a new score of the alignment path for each contour to select the best candidates among them. Then, we run the Smith-Waterman algorithm in this confined space. Furthermore, our heuristic alignment for an updated sequence shows that it can be further accelerated by using reusable dynamic programming (rDP), our prior work. In this study, we successfully validate "relative node tolerance boundȁD; (RNTB) in the pruned searching space. Furthermore, we improve the computational performance by quantifying the successful RNTB tolerance probability and switch to rDP on perturbation-resilient columns only. In our searching space derived by a threshold value of 90 percent of the optimal alignment score, we find that 98.3 percent of contours contain correctly updated paths. We also find that our method consumes only 25.36 percent of the runtime cost of sparse dynamic programming (sDP) method, and to only 2.55 percent of that of a normal dynamic programming with the Smith-Waterman algorithm.
机译：当研究人员意识到其测序数据中的错误，或者当研究人员必须比较近乎相似的序列（例如蛋白质家族）时，重新评估生物学序列之间的先前相似性结果变得不可避免。我们提出一种有效的方案，以仿射差距模型更新本地序列比对。原则上，使用两个氨基酸序列之间的先前匹配结果，我们执行前后比对以生成启发式搜索带，这些搜索带由一组次优路径限制。给定正确更新的序列，我们首先预测每个轮廓的对齐路径的新分数，以在其中选择最佳候选者。然后，我们在此受限空间中运行Smith-Waterman算法。此外，我们对更新序列的启发式比对表明，通过使用我们先前的工作可重用动态编程（rDP），可以进一步加速该序列。在这项研究中，我们成功地在修剪后的搜索空间中验证了“相对节点公差界ȁD;（RNTB）。此外，我们通过量化成功的RNTB公差概率来提高计算性能，并且仅在摄动弹性列上切换到rDP。”由最佳对齐分数的90％的阈值得出的空间，我们发现98.3％的轮廓包含正确更新的路径，并且还发现我们的方法仅消耗稀疏动态编程（sDP）方法运行时间成本的25.36％，仅为使用Smith-Waterman算法的普通动态编程的2.55％。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号