第三节 主要比对方法与软件

由于动态规划法的时间与空间复杂性太高，人们发展了该算法的多种变体使得它们能够在合理的时间内找到优化比对。变体之一是S . Altschul等在1989年引入的一个算法，它能极大地缩小k维动态规划表的搜索空间，其中心思想如下：首先，对k个序列的个配对按动态规划法进行配对比对，由于一个k序列比对对应于k维空间动态规划表中的一个路径（图3-。一个关键点是，需要确定一个将多序列比对投影成配对比对的开支上限，该开支上限的选择应能保证动态规划法找到k个序列的最优比对。在使用启发式方法确定配对比对的开支上限时，若比对的 ......