DNA比对得分是加性还是非加性？

Question

所以我有一个递归代码，它给出了2条DNA链的最佳对齐，但问题是它执行得非常慢（我需要它是递归的）。后来我在麻省理工学院的一个网站上看到，结果是相加的，这对我很好，但后来我想了一下，发现有一个问题：

网址：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-096-algorithms-for-computational-biology-spring-2005/lecture-notes/lecture5_newest.pdf

麻省理工学院的网站说，对于给定的（i，j）： 第一股（0，i）和第二股（0，j）对齐
+ 第一根_钢绞线（i，len）和第二根_钢绞线（j，len）对齐

等于

第一条和第二条钢绞线对齐

但是：

GTC GTAA

与GTA对齐的G是G——和GTA 带有对齐的TC是TC和A- 结果=G——TC和GTAA-

实际最佳结果=GTC-GTAA

有人能在麻省理工学院的网站上解释他们的意思吗？我可能都搞错了！在

Answer 1

我想你说的是this link。在

如果是这样的话，请仔细阅读几百遍；-）这是“加法”，因为你只考虑在一对特定的(i, j)对上分裂固定的对齐方式。在

在你假设的反例中，你首先打破了GTC的首字母{}和{}的首字母{}。那么G 是将GTC变成{}的最短方法。好的。继续相同的拆分，您仍然需要将剩余的右侧部分：TC与{}对齐。也可以。在

这是声称这是最好的分割。只有一种说法认为这是最好的对齐方式，因为你只考虑了特定的分割。在

这是动态编程方法中的一个小步骤，这是您缺少的部分。仍然需要计算所有可能的分割的最佳对齐。在

动态规划一开始很棘手。你不应该指望从看电报幻灯片中学到这一点。读一本真正的教科书，或者在网上搜索教程。在

加速递归版本

注释表明这个“必须”的代码是递归的。哦，好吧；—）

注意：我把这些放在一起只是为了说明一个加速合适递归函数的一般过程。它几乎没有被测试过。在

首先是一个非常天真的递归版本：

def lev(a, b):
    if not a:
        return len(b)
    if not b:
        return len(a)
    return min(lev(a[:-1], b[:-1]) + (a[-1] != b[-1]),
               lev(a[:-1], b) + 1,
               lev(a, b[:-1]) + 1)

我将在这里讨论的所有运行中使用"absd31-km"和"ldk3-1fjm"作为参数。在

在我的框中，使用python3，这个简单的函数在大约1.6秒后返回7。太慢了。在

最明显的问题是无休止重复的字符串切片。索引中的每个:所花费的时间与被切片的字符串的当前长度成比例。因此，第一个优化是传递字符串索引。因为代码总是切掉字符串的前缀，所以我们只需要传递“字符串末尾”索引：

^{pr2}$

好多了！这个版本在大约1.44秒内“仅”返回7。仍然非常缓慢，但比原来的好。它的优势会在更长的弦上增加，但谁在乎呢；-）

我们快完成了！现在需要注意的是，函数在运行过程中多次传递相同的参数。我们在“备忘录”中记录这些信息，以避免所有冗余计算：

def lev3(a, b):
    memo = {}
    def inner(j1, j2):
        if j1 < 0:
            return j2 + 1
        if j2 < 0:
            return j1 + 1
        args = j1, j2
        if args in memo:
            return memo[args]
        result = min(inner(j1-1, j2-1) + (a[j1] != b[j2]),
                     inner(j1-1, j2) + 1,
                     inner(j1, j2-1) + 1)
        memo[args] = result
        return result
    return inner(len(a)-1, len(b)-1)

该版本在0.00026秒内返回7，比lev2快5000倍以上。在

现在，如果您研究了基于矩阵的算法，并且眯着眼睛看一下，您会发现lev3()有效地构建了一个二维矩阵映射索引对，以在其memo字典中得到结果。它们实际上是一样的，只是递归版本以更复杂的方式构建矩阵。另一方面，递归版本可能更容易理解和推理。请注意，您发现的幻灯片称为“自上而下”的记忆化方法和“自下而上”的嵌套循环矩阵方法。这些描述得很好。在

您还没有谈到递归函数是如何工作的，但是如果它遭受类似的递归过量，您应该能够使用类似的技术获得类似的加速效果：-）