A fast pruning algorithm for optimal sequence alignment
A fast pruning algorithm for optimal sequence alignment
复制标题
一种用于最佳序列比对的快速剪枝算法
DOI：
10.1109/bibe.2001.974411
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Aaron Davidson
中科院分区：
文献类型：
--
作者：
Aaron Davidson
序列比对是计算生物学中的一个重要操作。本文讨论和评价了动态规划和A* 启发式搜索两种最优序列比对算法。本文提出了两种新的最优序列比对算法，它们在处理大规模问题（如几十万个字符）时优于传统方法。该技术结合了动态规划和A* 启发式搜索的优点，具有最小的额外开销。动态编程矩阵沿着反对角线遍历，限制计算以排除矩阵中不包含最佳路径的部分。一个可容许的启发式有助于修剪掉矩阵中不必要的区域，同时保留任何给定评分函数的最佳解。由于内存需求是一个主要关注的大序列比对问题，它示出了如何的标准算法（需要二次空间）可以重新制定为一个分而治之的算法（只需要线性空间，在一些recomputation的成本）。
Sequence alignment is an important operation in computational biology. Both dynamic programming and A* heuristic search algorithms for optimal sequence alignment are discussed and evaluated Presented here are two new algorithms for optimal pairwise sequence alignment which outperform traditional methods on very large problem instances (hundreds of thousands of characters, for example). The technique combines the benefits of dynamic programming and A* heuristic search, with a minimal amount of additional overhead. The dynamic programming matrix is traversed along antidiagonals, bounding the computation to exclude portions of the matrix that cannot contain optimal paths. An admissible heuristic assists in pruning away unnecessary areas of the matrix, while preserving optimal solutions for any given scoring function. Since memory requirements are a major concern for large sequence alignment problems, it is shown how the standard algorithm (requiring quadratic space) can be reformulated as a divide and conquer algorithm (requiring only linear space, at the cost of some recomputuation).
搜索序列数据库的策略。
影响因子：
2.7
作者：
NicholasJr,HB;Deerfield2nd,DW;Ropelewski,AJ
通讯作者：
Ropelewski,AJ