任何人都可以帮助我解决以下问题吗？
对于参数 k，计算两个字符串之间的全局对齐，受限于对齐包含最多 k 个间隙（连续 indel 块）的约束。
问问题
482 次
2 回答
1
您应该能够将其作为标准动态编程方法的扩展来处理序列比对。问题在于，现在有多种方式可以让您到达矩阵中的给定单元格，因为您可以使用不同数量的间隙到达那里。因此，您需要跟踪每个单元格中可能获得的最佳分数，因为您使用了一定数量的间隙来到达那里。
您可以通过使用在实施仿射惩罚时用于跟踪间隙长度的相同直觉来实现这一点：通过跟踪 k + 1 个矩阵。动态规划算法从第 0 个矩阵开始。该矩阵将代表您在网格中任何点都可以得到的最佳分数，而无需插入任何间隙。如果从矩阵 0 中选择“在 x 中添加间隙”或“在 y 中添加间隙”，您将在矩阵 1 中记录结果得分。如果从矩阵 1 中添加间隙，则转到矩阵 2，依此类推。如果您在矩阵 k 中，则不能选择添加间隙。回溯的起点将是得分最高的右下角。
于 2013-12-21T12:37:38.433 回答
1
我一直在寻找类似的问题，终于找到了正确术语称为的解决方案Affine Gap Penalties。该幻灯片可以在Advanced Sequence Alignment找到，这是UNC-Chapel Hill的旧课程幻灯片之一。
相关幻灯片从#12 开始。
简短的回答是：
连续插入缺失的惩罚会略有不同（间隙扩展惩罚）；
我们需要 3 个矩阵来保留所有值，截图来自幻灯片：
于 2021-10-27T03:23:43.557 回答