使用局部和全局对齐找到两个字符串的最佳局部对齐
Find optimal local alignment of two strings using local & global alignments
我有一个家庭作业问题，我试图解决很多小时都没有成功，也许有人可以指导我正确的思考方式。
问题：
我们想找到两个字符串S1和S2的最优局部对齐，我们知道存在这样的对齐
S1 和 S2 的两个对齐子串的长度最多为 q。
此外，我们知道具有最大值opt的table个单元格的数量最多为r。
描述一个算法解决时间 O(mn+r*q^2) 最多使用 space
O(n+r+q^2).
限制： 运行寻找最优局部对齐值的算法，与
添加到您的选择（如索引对列表），仅一次。此外，您可以运行任意多次解决全局最优对齐问题的算法变体
我知道解决这个问题的方法是 运行 局部对齐多次，全局对齐只一次，但相反。
全局对齐算法：
局部对齐算法：
如有任何帮助，我们将不胜感激。
以后有人对这个问题感兴趣的答案：
- 计算最佳局部对齐分数两个字符串的 OPT 在 $O(mn)$ 时间和 $O(n)$ space 通过只维护一个DP矩阵的行。 （因为我们只计算分数，不需要执行回溯来构建完整的解决方案，所以我们不需要保留完整的 DP 矩阵。）当您这样做时，跟踪到目前为止看到的最高单元格值，以及具有此值的单元格的坐标列表 $(i, j)$。每当看到新的最大值时，清除列表并更新最大值。每当看到当前最大值的单元格 $\ge$ 时（包括我们刚刚看到新最大值的情况），将当前单元格的坐标添加到列表中。最后，我们有一个所有最优局部比对的端点列表；根据假设，最多有 $r$ 个。
- 对于列表中的每个条目 $(i, j)$：
- 设置$R1$为子串$S1[i-q+1..i]$的逆向，$R2$为$S2[j-q+1..j]$的逆向.
- 在 $O(q^2)$ 时间内执行 $R1$ 和 $R2$ 的最优全局对齐，这次保持完整的 $O(q^2)$ DP 矩阵。
- 搜索矩阵中最高的条目（也是 $O(q^2)$ 时间；或者您可以在上一步执行此操作）。
- 如果这个条目是OPT，我们已经找到了一个解决方案：从这个单元格向左上角回溯找到完整的解决方案，反转它，输出它，然后停止。
根据假设，至少有一个在上一步中执行的比对达到了 OPT 的分数。 （请注意，反转两个字符串不会改变对齐的分数。）
第 2 步最多迭代 $r$ 次，每次执行 $O(q^2)$ 次，最多使用 $O(q^2)$ space，所以总时间space 边界得到满足。
（避免反转字符串的更简单方法是简单地执行长度-$q$ 子字符串的 local 对齐，但限制似乎禁止这样做。）
我有一个家庭作业问题，我试图解决很多小时都没有成功，也许有人可以指导我正确的思考方式。
问题：
我们想找到两个字符串S1和S2的最优局部对齐，我们知道存在这样的对齐 S1 和 S2 的两个对齐子串的长度最多为 q。 此外，我们知道具有最大值opt的table个单元格的数量最多为r。 描述一个算法解决时间 O(mn+r*q^2) 最多使用 space O(n+r+q^2).
限制： 运行寻找最优局部对齐值的算法，与 添加到您的选择（如索引对列表），仅一次。此外，您可以运行任意多次解决全局最优对齐问题的算法变体
我知道解决这个问题的方法是 运行 局部对齐多次，全局对齐只一次，但相反。
全局对齐算法：
局部对齐算法：
如有任何帮助，我们将不胜感激。
以后有人对这个问题感兴趣的答案：
- 计算最佳局部对齐分数两个字符串的 OPT 在 $O(mn)$ 时间和 $O(n)$ space 通过只维护一个DP矩阵的行。 （因为我们只计算分数，不需要执行回溯来构建完整的解决方案，所以我们不需要保留完整的 DP 矩阵。）当您这样做时，跟踪到目前为止看到的最高单元格值，以及具有此值的单元格的坐标列表 $(i, j)$。每当看到新的最大值时，清除列表并更新最大值。每当看到当前最大值的单元格 $\ge$ 时（包括我们刚刚看到新最大值的情况），将当前单元格的坐标添加到列表中。最后，我们有一个所有最优局部比对的端点列表；根据假设，最多有 $r$ 个。
- 对于列表中的每个条目 $(i, j)$：
- 设置$R1$为子串$S1[i-q+1..i]$的逆向，$R2$为$S2[j-q+1..j]$的逆向.
- 在 $O(q^2)$ 时间内执行 $R1$ 和 $R2$ 的最优全局对齐，这次保持完整的 $O(q^2)$ DP 矩阵。
- 搜索矩阵中最高的条目（也是 $O(q^2)$ 时间；或者您可以在上一步执行此操作）。
- 如果这个条目是OPT，我们已经找到了一个解决方案：从这个单元格向左上角回溯找到完整的解决方案，反转它，输出它，然后停止。
根据假设，至少有一个在上一步中执行的比对达到了 OPT 的分数。 （请注意，反转两个字符串不会改变对齐的分数。）
第 2 步最多迭代 $r$ 次，每次执行 $O(q^2)$ 次，最多使用 $O(q^2)$ space，所以总时间space 边界得到满足。
（避免反转字符串的更简单方法是简单地执行长度-$q$ 子字符串的 local 对齐，但限制似乎禁止这样做。）