Zhang Z, Berman P, Miller W
Department of Computer Science and Engineering, The Pennsylvania State University, University Park 16802, USA.
J Comput Biol. 1998 Summer;5(2):197-210. doi: 10.1089/cmb.1998.5.197.
Given a strong match between regions of two sequences, how far can the match be meaningfully extended if gaps are allowed in the resulting alignment? The aim is to avoid searching beyond the point that a useful extension of the alignment is likely to be found. Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem. Given two sequences and a fixed X > 0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X. Our results indicate that computing an optimal alignment under this constraint is very expensive. However, less rigorous conditions on the alignment can be guaranteed by quite efficient algorithms. One of these variants has been implemented in a new release of the Blast suite of database search programs.
如果在最终比对中允许出现空位，那么当两个序列的区域之间存在强匹配时，该匹配能够有意义地延伸多远呢？目标是避免在可能找到比对有用延伸的点之后进行搜索。不失一般性，我们可以将注意力限制在强匹配之后的序列后缀上，这就引出了以下形式化问题。给定两个序列以及一个固定的X>0，在比对的任何部分得分都不低于 -X的约束下，比对序列的初始部分。我们的结果表明，在这种约束下计算最优比对成本非常高。然而，通过相当高效的算法可以保证比对满足不太严格的条件。这些变体之一已在新版的数据库搜索程序Blast套件中实现。
