问题标签 [needleman-wunsch]

我想知道如何量化 Needleman-Wunsch 算法的结果（通常用于比对核苷酸/蛋白质序列）。

考虑一些固定的评分方案和两个不同长度S1和的序列S2。假设我们通过蛮力计算所有可能的对齐方式，S1并且得分最高的对齐方式有一个 score 。当然，这比 Needleman-Wunsch 方法的复杂性要高得多。S2x

当使用 Needleman-Wunsch 算法查找序列比对时，假设它有一个 score y。

考虑r是通过 Needleman-Wunsch 为两个随机序列R1和生成的分数R2。

x相比如何y？是否y总是大于r已知同源性的两个序列？

总的来说，我确实知道我们使用 Needleman-Wunsch 算法来显着加快序列比对（相对于蛮力方法），但不了解随之而来的准确性成本（如果有的话）。我尝试阅读了原始论文（Needleman & Wunsch，1970），但仍然留下了这个问题。

有人可以提供一个示例，其中仿射间隙惩罚最终会给出与在两个具有固定间隙惩罚的序列上运行 NW 不同的结果吗？

我在 C# 中实现了最长公共子序列问题。我需要检测两个字符串之间的所有常见最大子序列。

为此，我使用Needleman-Wunsch 算法创建了一个表，用于存储每个计算步骤的 LCS 序列。

是否有机会确定找到了多少个最大子序列（使用表格）？

根据这一点，我想选择一种方法来收集每个子序列。关键是，对于一个子序列递归是不需要的，所以它会提供更好的性能。它对我的任务至关重要。

这是一个代码片段，其中实现了项目的基本功能：

以及具有两种输入和预期输出的示例：

任何帮助将不胜感激。

我将创建一个 needleman-wunsch 全局序列比对。但我的回答是错误的。请帮我检查我的代码。有时当两个序列匹配时，它仍然会运行不匹配函数。忽略我蹩脚的英语，谢谢。

这是我的输出（突出显示的是错误答案）：

有没有办法为以下示例编写算法而没有糟糕的运行时间？

该算法应该能够匹配两个字符串，但是字符串中的每个值都有一个权重。（0-1：0 表示非必要，1 表示必要）如果权重不是 1，则字符不必匹配，因此可能会发生不匹配。这更容易用一个例子来解释。

图案： public static void main (String []args){

样本： public static void main (List<String> command_line_vals) {

重量：

• 1 为public static void main (
• 0.5 为String []
• 0.1 为args
• 1 为) {

目标是让这两个匹配成功。如果参数更接近模式，则得分更高。在这个例子中，这意味着String []vals它将比上面的样本排名更高。

这与 needleman-wunsch 不同，因为如果 char 的等级为 !=1 那么它根本不应该匹配。

我会使用regex但是这不允许我对匹配的人进行排名。会先使用正则表达式（所有非 1 值字符的通配符），然后在匹配的那些上使用 needleman-wunsch 吗？

欢迎提出建议和头脑风暴。

感谢您的时间。

我知道 Levenshtein 和 Needleman Wunsch 都有 O(N*M) 的时间复杂度，但我很想知道哪一个比另一个表现更好，为什么？

我正在尝试使用 needleman 解决“最长公共子序列”问题。

示例：输入：text1 = "abcde", text2 = "ace" 输出：3
解释：最长的公共子序列是 "ace"，它的长度是 3。

对于 text1 =“ezu”和 text2 =“ubm”的情况，我对算法应该如何工作感到非常困惑。

Needleman 矩阵是（假设不匹配的成本是 -3，差距的成本是 -4 和匹配是 1）：

现在算法状态从矩阵的底角回溯，并且：

• 如果 text[i] == text[j] => 向上移动对角线
• 否则移动到上下之间的最大值。

因此，从 -9 开始，我必须在 -10 和 -10 之间进行选择（我应该向上还是向下？），无论做出何种决定，我都不会遇到这种情况 [i,j] = [3,1]

我的代码：

谢谢！

众所周知，全局序列比对问题可以使用 Needleman-Wunsch 算法解决。解决问题分为三个步骤

说清楚。

并让评分函数为

1. 对于初始化步骤

   1.1。创建一个 m+1 乘 n+1 的二维矩阵，即 M[m+1][n+1]

   1.2. 将第一行和第一列初始化为
   M[0][j]=M[0][j-1]+ gap 和

   M[i][0]=M[i-1][0]+间隙

2.对于矩阵填充步骤，只有当M[i-1][j-1]、M[i-1][j]和M[i][j]时，才能开始计算M[i][j] -1] 获得它们的值，并且可以使用以下方法计算这些值：

要使用串行方法实现，我们可以使用以下代码填充矩阵以进行第二步

并行实现（使用 OpenMP 或 Pthreads）。

对于并行实现，由于数据依赖性，垂直或水平数据分解是不可行的。在计算该矩阵元素之前，需要计算所有北、西和西北邻域。因此，可以按照反对角线的顺序依次进行分数矩阵的计算，如附图反对角矩阵所示。我的问题是，如何提取无方阵的反对角元素，不包括第一列和第一行的值，如图所示反对角元素任何可以帮助我的人？