bioinformatics - 证明对于特定函数的局部和全局对齐 L >= G

Question

我这学期要上生物信息学课，但我在书中的一个特定问题上遇到了麻烦。

*给定两个具有相同长度 n 的 DNA 序列 S 和 T，并让评分函数定义如下：匹配 = 1，错配 = -1，插入缺失（间隙） = -2。假设 G 和 L 分别是 S 和 T 之间的最佳全局对齐和最佳局部对齐的分数。

证明 L >= G。

我了解如何找到两个随机序列的各自比对，但我无法证明这一点。据我所知，这是真的。G 永远无法大于 L，因为 indel 惩罚太高了，而比赛无法弥补它。我还必须生成一个例子来证明它们可以相等，所以我知道这是真的。

所以，是的，任何关于如何去做的提示都会很棒。

Answer 1

那么这个网站不应该是我们做你的功课，但这是一个简单的问题，所以让我们来破解它：

我们将假设您最初提出的分数是有效的（关于得分）。

假设相反，存在一些小于 G 的局部对齐。如果这是真的，那么这意味着您的最佳局部对齐（意味着您从 G 的起点或终点之外的某个地方开始）实际上比您的全局对齐效率低。但我们知道这不可能，因为局部对齐是全局对齐的一个子集（最坏的情况，您的局部对齐就是您的全局对齐）。

因此，我们证明没有反例，所以这个陈述必须成立。

希望这是有道理的！