algorithm - 具有最小子序列长度约束的序列比对

Question

如何实现具有最小子序列长度约束的序列比对。例如，让这些输入的最小子序列长度为 3。使用 Smith-Waterman 给出如下输出。

ATACGGACC
||    |||
ATCATAACC

但相反，我需要像下面这样。

---ATACGGACC
   |||   |||
ATCATA---ACC

是否有一个已知的算法，或者你知道一种方法？

提前致谢。

Answer 1

看看 Smith-Waterman 是如何工作的。您有两个序列（长度为 N 的 S1，长度为 M 的 S2）并创建一个 NxM 矩阵（我们称之为 A），其中 A(i,j) 是“S1[1..i] 和 S2 的最佳分数对齐[1..j]。” 为此，您编写了一个关于如何根据最后一个元素获得 A(i,j) 的递归 - A(i,j) 是最好的

A(i-1, j-1) + match/mismatch score
A(i,j-1) + indel score
A(i-1,j) + indel score

这是基本思想；你可能需要稍微调整一下。

要执行您的要求，您需要两个矩阵。设 A(i,j) 为“S1[1..i] 和 S2[1..j] 的最佳得分对齐以匹配结尾”，B(i,j) 为“S1[ 的最佳得分对齐” 1..i] 和 S2[1..j] 以插入缺失结尾。"

让我们从 B 开始，因为它更容易。B(i,j) 是最好的

A(i,j-1) + indel score
A(i-1,j) + indel score
B(i,j-1) + indel score
B(i-1,j) + indel score

A(i,j) 是最好的

A(i-1, j-1) + match/mismatch score
B(i-3, j-3) + match/mismatch score for the three

Answer 2

该算法有效地返回所有可能子序列的二维表。您必须做额外的工作来提取实际的子序列，这显然是您正在做的。在对齐（反向）跟踪期间，您可以进行准入检查：

if(subsequence.length() > 2)
     results.add(subsequence);

如果你不想像我提到的那样去，那么你介意展示你用来获取实际子序列的代码，那么也许我们可以告诉你在哪里编辑？