字符串与模式匹配算法(六):Needleman–Wunsch算法

摘要:
该算法是由SaulB.Needlman和ChristianD.Wunsch两位科学家于1970年发明的。从现在开始,我们将使用Needleman和Wunsch创造的简单体系来进行打分,即匹配得1分,不匹配得-1分,错位得-1分.四、填充评分矩阵  开始于第二行中的第二列,初始值为0。
一、Needleman-Wunsch 算法

尼德曼-翁施算法(英语:Needleman-Wunsch Algorithm)是基于生物信息学的知识来匹配蛋白序列或者DNA序列的算法。这是将动态算法应用于生物序列的比较的最早期的几个实例之一。该算法是由 Saul B. Needlman和 Christian D. Wunsch 两位科学家于1970年发明的。本算法高效地解决了如何将一个庞大的数学问题分解为一系列小问题,并且从一系列小问题的解决方法重建大问题的解决方法的过程。该算法也被称为优化匹配算法和整体序列比较法。时至今日尼德曼-翁施算法仍然被广泛应用于优化整体序列比较中。

二、初始化得分矩阵

首先建立如下的得分矩阵。从第一列第一行的位置起始。计算过程从d 0,0开始,可以是按行计算,每行从左到右,也可以是按列计算,每列从上到下。当然,任何计算过程,只要满足在计算 d(i , j)时 d (i-1, j)(上边)、d(i-1 , j-1) (左上)和 d(i, j-1) (左边)都已经被计算这个条件即可。在计算 d(i , j)后,需要保存d(i , j)是从 d(i-1 , j)、d(i-1 , j-1)或 d(i, j-1)中的一个推进的,或保存计算的路径,以便于后续处理。上述计算过程到 d(m , n) 结束,其中m,n各位两个序列的长度。

GCATGCU
0
G
A
T
T
A
C
A
三、选择得分体系

我们可以看出每个位置配对都有三种可能情况:匹配, 不匹配与错位(或插入):

  • 匹配: 两个字母相同

  • 不匹配:两个字母不相同

  • 错位:一个字母与另一个序列中的间隔(空白)相匹配

  这三种得分情况有很多打分标准,这些情况都总结在得分体系的部分。从现在开始,我们将使用Needleman 和Wunsch创造的简单体系来进行打分,即匹配得1分,不匹配得-1分,错位得-1分.

四、填充评分矩阵

  开始于第二行中的第二列,初始值为0。通过矩阵一行一行移动,计算每个位置的分数。得分被计算为从现有的分数可能的最佳得分(即最高)的左侧,顶部或左上方(对角线)。当一个得分从顶部计算,或从左边这代表在我们的对准的插入缺失。当我们从对角线计算分数这表示两个字母所得位置匹配的对准。定不存在“向上”或“左上”的位置对第二行,我们只能从现有单元向左添加。因此,我们添加-1的权利,因为这代表了从以前的比分插入缺失。这导致在第一行是0,-1,-2,-3,-4,-5,-6,-7。这同样适用于第二列,因为我们只具有以上现有分数。因此,我们有:

GCATGCU
0-1-2-3-4-5-6-7
G-1
A-2
T-3
T-4
A-5
C-6
A-7

第一种情况是存在向三个方向构筑矩阵,周围位置得分如下:

G
0-1
G-1?

  该单元格具有三个可能的候选总和:

  • 对角线的左上邻居的分数为0。G和G的配对是匹配项,因此添加匹配项的分数:0 + 1 = 1
  • 正上邻居的得分为-1,从那里移动代表一个indel,因此将indel的得分相加:(-1)+(-1)=(-2)
  • 左邻居的得分也为-1,代表插入缺失,也产生(-2)。

  得分最高的单元格也必须记录下来。在的文章最开始说的那矩阵图中,它表示为从行和列3中的单元格到行和列2中的单元格的箭头,?号处根据评分规则最后为1。

  对接下来的位置,我们有不同的选择。

GC
0-1-2
G-11X
A-2Y

X:

  • 上: (-2)+(-1) = (-3)

  • 左: (+1)+(-1) = (0)

  • 左上: (-1)+(-1) = (-2)

  Y:

  • 上: (1)+(-1) = (0)

  • 左: (-2)+(-1) = (-3)

  • 左上: (-1)+(-1) = (-2)

对于X和Y,最高得分均为0。
  两个或所有相邻小格可能会达到最高的候选分数:

TG
T11
A0X
  • Top: (1)+(-1) = (0)

  • Top-Left: (1)+(-1) = (0)

  • Left: (0)+(-1) = (-1)

  在这种情况下,必须将达到最高候选得分的所有方向记录为中并完成图中可能的起点,例如,在第7行和第7列的单元格中。

  以这种方式填写表格会给出分数或所有可能的比对候选,右下角单元格中的分数代表最佳比对的比对分数。

字符串与模式匹配算法(六):Needleman–Wunsch算法第1张

五、追溯本源

  按照箭头的方向标记从右下角的单元格到左上角的单元格的路径。从此路径开始,将按照以下规则构建序列:

  • 对角箭头表示匹配或不匹配,因此原始单元格的列字母和行字母将对齐。

  • 水平或垂直箭头表示插入/缺失。 水平箭头将使间隙(“-”)与行的字母(“侧边”序列)对齐,垂直箭头将使间隙与列的字母(“顶部”序列)对齐。

  • 如果有多个箭头可供选择,则它们表示路线的分支。 如果两个或多个分支都属于从右下角到左上角单元格的路径,则它们是同等可行的路线。 在这种情况下,请注意将路径作为单独的对齐候选。

  遵循这些规则,上图中的一个可能的对齐候选者的步骤为:

U → CU → GCU → -GCU → T-GCU → AT-GCU → CAT-GCU → GCAT-GCU
A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA
             ↓
    (branch) → TGCU → ...
             → TACA → ...
六、评分系统

  最简单的计分方案只是为每个匹配,不匹配和插入缺失给出一个值。 上面的分步指南使用match = 1,mismatch = -1,indel = -1。 因此,对准分数越低,编辑距离越大,因为该计分系统需要较高的分数。 另一个计分系统可能是:

  • Match = 0

  • Indel = 1

  • Mismatch = 1

  对于此系统,对齐分数将代表两个字符串之间的编辑距离。 可以针对不同的情况设计不同的评分系统,例如,如果认为差距对您的对齐方式非常不利,则可以使用对差距进行严重惩罚的评分系统,例如:

  • Match = 0

  • Mismatch = 1

  • Indel = 10

七、Needleman–Wunsch算法代码

  计算评分矩阵,按行推进,根据左、上、左上计算的结果取最大的:

1     /**
2 * 一种用于计算全局最大相似度矩阵的实用方法。
3 *
4 * @paramsequence1 代表第一个氨基酸序列的字符串。
5 * @paramsequence1 代表第二个氨基酸序列的字符串。
6 * @parammatchScore 代表分配给比赛的分数的浮点数。
7 * @parammismatchScore 一个浮点数,代表分配给不匹配项的分数。
8 * @paramindelScore 浮点数表示分配给插入和删除的分数。
9      */
10     public static float[][] computeMatrix(String sequence1, String sequence2, float matchScore, float mismatchScore, floatindelScore) {
11         sequence1 = "-" +sequence1;
12         sequence2 = "-" +sequence2;
13 
14         float[][] resultMatrix = new float[sequence1.length()][sequence2.length()];
15 
16         for (int i = 0; i < sequence1.length(); i++) {
17             resultMatrix[i][0] = i *indelScore;
18 }
19         for (int j = 0; j < sequence2.length(); j++) {
20             resultMatrix[0][j] = resultMatrix[0][j] = j *indelScore;
21 }
22 
23         for (int i = 1; i < sequence1.length(); i++) {
24             for (int j = 1; j < sequence2.length(); j++) {
25                 resultMatrix[i][j] = Math.max(resultMatrix[i - 1][j] +indelScore,
26                         Math.max(resultMatrix[i][j - 1] + indelScore, resultMatrix[i - 1][j - 1] +
27                                 (sequence1.charAt(i) == sequence2.charAt(j) ?matchScore : mismatchScore)));
28 }
29 }
30 
31         returnresultMatrix;
32     }

根据评分矩阵来按最低顺序获得最佳对齐:

1     /**
2 * 一种计算两个的最佳全局最低对齐序列的实用方法
3 *
4 * @paramsimilarityMatrix 2维数组表示以前计算的全局最大相似度矩阵。
5 * @paramsequence1 代表第一个氨基酸序列的字符串。
6 * @paramsequence1 代表第二个氨基酸序列的字符串。
7 * @parammatchScore 代表分配给匹配的分数的浮点数。
8 * @parammismatchScore 一个浮点数,代表分配给不匹配项的分数。
9 * @paramindelScore 浮点数表示分配给插入和删除的分数。
10      */
11     public static OptimalAlignment obtainOptimalAlignmentByDownmostOrder(floatsimilarityMatrix[][],
12                                                                          String sequence1, String sequence2, double matchScore, double mismatchScore, doubleindelScore) {
13 
14         int i = similarityMatrix.length - 1;
15         int j = similarityMatrix[0].length - 1;
16         StringBuilder alignment1Builder = newStringBuilder();
17         StringBuilder alignment2Builder = newStringBuilder();
18 
19         sequence1 = "-" +sequence1;
20         sequence2 = "-" +sequence2;
21 
22         while (i != 0 && j != 0) {
23             if (similarityMatrix[i][j] == (similarityMatrix[i][j - 1] +indelScore)) {
24                 alignment1Builder.insert(0, "-");
25                 alignment2Builder.insert(0, sequence2.charAt(j));
26                 j--;
27             } else if (similarityMatrix[i][j] == (similarityMatrix[i - 1][j - 1] + (sequence1.charAt(i) == sequence2.charAt(j) ?matchScore : mismatchScore))) {
28                 alignment1Builder.insert(0, sequence1.charAt(i));
29                 alignment2Builder.insert(0, sequence2.charAt(j));
30                 i--;
31                 j--;
32             } else if (similarityMatrix[i][j] == (similarityMatrix[i - 1][j] +indelScore)){
33                 alignment1Builder.insert(0, sequence1.charAt(i));
34                 alignment2Builder.insert(0, "-");
35                 i--;
36 }
37 }
38 
39         return newOptimalAlignment(alignment1Builder.toString(), alignment2Builder.toString());
40     }

测试主函数:

1   public static voidmain(String[] args) {
2         String sequence1 = "GCATGCU";
3         String sequence2 = "GATTACA";
4 
5         float matchScore = 1;
6         float mismatchScore = -1;
7         float indelScore = -1;
8 
9         float[][] computedMatrix =NeedlemanWunsch.computeMatrix(sequence1, sequence2, matchScore, mismatchScore, indelScore);
10 
11         System.out.println("Best global downmost alignment: ");
12 System.out.println(NeedlemanWunsch.obtainOptimalAlignmentByDownmostOrder(computedMatrix, sequence1, sequence2, matchScore, mismatchScore, indelScore));
13     }

全局相似度矩阵:

字符串与模式匹配算法(六):Needleman–Wunsch算法第2张

结果:

字符串与模式匹配算法(六):Needleman–Wunsch算法第3张

免责声明:文章转载自《字符串与模式匹配算法(六):Needleman–Wunsch算法》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇linux(centos8):firewalld使用ipset管理ip地址的集合PHP获取上周五时间简单写法下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Yacc 与 Lex 快速入门

源地址: http://www.ibm.com/developerworks/cn/linux/sdk/lex/index.html Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another Compiler Compiler。 让我们从 Lex 开始吧。 Lex Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模...

BUAA_2019_MATLAB基础与应用_期末复习纲要

Matlab复习提纲 一、概述 1. Matlab(Matrix Laboratory)概述 1980年,由美国的 Clever Moler 博士开发; 是一款 科学与工程计算软件; 第四代智能计算机语言。 2. 功能与特点 开放性强、可扩展性强,兼容性强,直观灵活; MATLAB提供了丰富的矩阵运算处理功能,是基于矩阵运算的处理工具; 矩阵运...

Excel透视表基础之数据源、创建、基本术语、基本操作

数据源的基本要求: 每列数据的第一行包含该列标题 不能包含空行或空列 不能包含空单元格 不能包含合并单元格 不能包含同类字段 如果包含空行、空列则删除空行和空列。如果包含空单元格则填充空单元格。 如果包含合并单元格则将合并单元格取消,并将取消后的空单元格填充。方法:选择第一行、按着shift选择最后一行Ctrl + G定位空值,输入“=向上的单元格”...

使用POI创建word表格合并单元格兼容wps

poi创建word表格合并单元格代码如下: /** * @Description: 跨列合并 */ public void mergeCellsHorizontal(XWPFTable table, int row, int fromCell, int toCell) { for (int cellIndex = fromCell; cell...

Oracle 归档日志管理

一、Oracle日志介绍 1、Oracle日志分类分三大类: Alert log files--警报日志,Trace files--跟踪日志(用户和进程)和redo log 重做日志(记录数据库的更改)。本文主要关注Oracle的重做日志。重做日志分为在线重做日志和归档重做日志。online Redo log files--在线重做日志,又称联机重做日志...

使用Java创建Excel,并添加内容

使用Java创建Excel,并添加内容 一、依赖的Jar包 jxl.jar,使用jxl操作Excel   Jxl是一个开源的Java Excel API项目,通过Jxl,Java可以很方便的操作微软的Excel文档。除了Jxl之外,还有Apache的一个POI项目,也可以操作Excel,两者相比之下:Jxl使用方便,但功能相对POI比较弱。POI使用复杂。...