比对算法 - 版本历史

点击空白处刷新：/* BLAST矩阵 */

2026-03-10T00:31:20Z

BLAST矩阵

←上一版本		2026年3月10日 (二) 08:31的版本
第59行：		第59行：

	==== BLAST矩阵 ====		==== BLAST矩阵 ====
	将一致的计算为+~~4分，不一致的计算为~~-5分		将一致的计算为+5分，不一致的计算为-4分

	和上一张差不多		和上一张差不多

卡布喜·米糖：/* 全局比对之Needleman-Wunsch算法 */（算法发明者名字打错了）

2026-03-02T00:47:03Z

全局比对之Needleman-Wunsch算法：（算法发明者名字打错了）

←上一版本		2026年3月2日 (一) 08:47的版本
第147行：		第147行：
	无后效性，也就是马尔可夫性，后面的决策不能对前面的决策产生影响。		无后效性，也就是马尔可夫性，后面的决策不能对前面的决策产生影响。

	下面证明Needleman-~~Swunch算法的正确性。定义f~~(i,j)表示序列A到了第i个碱基，序列B到了第j个碱基，最小罚分。		下面证明Needleman-Wunsch算法的正确性。定义f(i,j)表示序列A到了第i个碱基，序列B到了第j个碱基，最小罚分。

	f(i,j)=min{f(i-1, j)-2, f(i, j-1)-2, f(i-1, j-1)+【A[i]与B[j]的是否匹配？+1或-1】}		f(i,j)=min{f(i-1, j)-2, f(i, j-1)-2, f(i-1, j-1)+【A[i]与B[j]的是否匹配？+1或-1】}
第172行：		第172行：
	许多名字里带有Dot的软件可以用打点法比对序列如Dnadot，（dotlet似乎属于SIB		许多名字里带有Dot的软件可以用打点法比对序列如Dnadot，（dotlet似乎属于SIB

	=== 全局比对之Needleman-~~Swunch算法~~ ===		=== 全局比对之Needleman-Wunsch算法 ===
	1970年由名字里的二人开发。		1970年由名字里的二人开发。

	换一种方法理解打点法，您会发现她很像一种打分，只不过是0/1		换一种方法理解打点法，您会发现她很像一种打分，只不过是0/1
	[[文件:NStrue.png\|缩略图\|~~Needlemanswunch矩阵初始化~~]]		[[文件:NStrue.png\|缩略图\|Needleman-Wunsch矩阵初始化]]
	下面我们使用更加酷炫的动态规划（走格子），Needleman-~~Swunch的走格子步骤如下~~		下面我们使用更加酷炫的动态规划（走格子），Needleman-Wunsch的走格子步骤如下

	选取错配、匹配、空位对应的奖惩制度（注：上一个人编辑时用的错配和空位-1分，匹配+1分；此我为了讲述方便，后改为错配-1分、匹配+1分、空位-2分）		选取错配、匹配、空位对应的奖惩制度（注：上一个人编辑时用的错配和空位-1分，匹配+1分；此我为了讲述方便，后改为错配-1分、匹配+1分、空位-2分）

Jerrywang：添加了动态规划相关内容

2026-03-01T14:52:46Z

添加了动态规划相关内容

←上一版本		2026年3月1日 (日) 22:52的版本
第158行：		第158行：

	在上面这个问题中，延续之前的状态定义f(i,j)表示走到格子(i,j)的和的最小绝对值。子问题划分还是完全的，但是如果当前A[i][j]碰到一个很大的负数，则前面我们希望有一个尽可能贴近A[i][j]的正数和最好，而非越小越好。		在上面这个问题中，延续之前的状态定义f(i,j)表示走到格子(i,j)的和的最小绝对值。子问题划分还是完全的，但是如果当前A[i][j]碰到一个很大的负数，则前面我们希望有一个尽可能贴近A[i][j]的正数和最好，而非越小越好。

			解决上面这个问题，重新定义状态：f(i,j,x)表示走到格子(i,j)，和的绝对值是x，是否可行。这种可行性的问题，只要子问题出现可行的，则当前问题就可行，显然满足最优子结构。但是要考虑此算法的时间空间复杂度问题，如果网格中每个数的绝对值都很小，也许就是一种可行的动态规划解法。如果x范围极大，动态规划则不可行，只能老老实实用meet-in-the-middle算法了。

	希望以上能够帮助读者理解动态规划和贪心的区别，以及动态规划的正确性证明。		希望以上能够帮助读者理解动态规划和贪心的区别，以及动态规划的正确性证明。

Jerrywang：添加了关于动态规划算法的详细阐述和正确性证明。我学过信息学。

2026-03-01T14:43:17Z

添加了关于动态规划算法的详细阐述和正确性证明。我学过信息学。

@@ 第131行： / 第131行： @@
 （有人知道这个点是怎么来的吗？道理上来说贪心算法不一定是全局最优）
-由理查德贝尔曼开发。
+由理查德贝尔曼（算法、数学家，并非生物学家）提出。
 '''切记局部最优不是全局最优——<s>信息巨佬补</s>'''
-局部最优是贪心，全局才是动态规划
+'''<s>来补了！以下是信息学内容：</s>'''
 === 打点法 ===

2026年1月9日 (五) 09:28 扶摇棘

2026-01-09T09:28:27Z

←上一版本		2026年1月9日 (五) 17:28的版本
第127行：		第127行：
	核心原理是，如果你每一步都是最优解，那最后也一定是最优解。		核心原理是，如果你每一步都是最优解，那最后也一定是最优解。

	~~也就是说，因为你在列表走格子的时候每次都取了最优解，所以比对结果也应该是最优解。~~		也就是说，<u>因为你在列表走格子的时候每次都取了最优解，所以比对结果也应该是最优解</u>。

			（有人知道这个点是怎么来的吗？道理上来说贪心算法不一定是全局最优）

	1950由理查德贝尔曼开发。		1950由理查德贝尔曼开发。

Sofia：自动添加 Sofia 模板和分类

2025-08-23T08:35:21Z

自动添加 Sofia 模板和分类

←上一版本		2025年8月23日 (六) 16:35的版本
第157行：		第157行：
	2，方法：如图		2，方法：如图
	<br>[[文件:比对算法举例.jpg\|替代=错配-1分、匹配+1分、空位-2分\|500x500像素\|错配-1分、匹配+1分、空位-2分]]		<br>[[文件:比对算法举例.jpg\|替代=错配-1分、匹配+1分、空位-2分\|500x500像素\|错配-1分、匹配+1分、空位-2分]]

			{{学科分类}}

			[[Category:生物信息学]]

2025年7月16日 (三) 03:10 W. Machine

2025-07-16T03:10:44Z

←上一版本		2025年7月16日 (三) 11:10的版本
第150行：		第150行：
	[[文件:NStrue.png\|缩略图\|Needlemanswunch矩阵初始化]]		[[文件:NStrue.png\|缩略图\|Needlemanswunch矩阵初始化]]
	下面我们使用更加酷炫的动态规划（走格子），Needleman-Swunch的走格子步骤如下		下面我们使用更加酷炫的动态规划（走格子），Needleman-Swunch的走格子步骤如下

			选取错配、匹配、空位对应的奖惩制度（注：上一个人编辑时用的错配和空位-1分，匹配+1分；此我为了讲述方便，后改为错配-1分、匹配+1分、空位-2分）

	1，初始化矩阵，将两条序列用上一张图中的方法分别列出并且在开头处空一格，形成一个二维表格，在表格的左上角的边缘打上0，-1，-2，。。。一直到表格结束		1，初始化矩阵，将两条序列用上一张图中的方法分别列出并且在开头处空一格，形成一个二维表格，在表格的左上角的边缘打上0，-1，-2，。。。一直到表格结束

	2		2，方法：如图
			<br>[[文件:比对算法举例.jpg\|替代=错配-1分、匹配+1分、空位-2分\|500x500像素\|错配-1分、匹配+1分、空位-2分]]

佛山水泵厂中学：/* 动态规划 */

2025-05-07T09:22:05Z

动态规划

←上一版本		2025年5月7日 (三) 17:22的版本
第132行：		第132行：

	'''切记局部最优不是全局最优——<s>信息巨佬补</s>'''		'''切记局部最优不是全局最优——<s>信息巨佬补</s>'''

			局部最优是贪心，全局才是动态规划

	=== 打点法 ===		=== 打点法 ===

佛山水泵厂中学：/* 动态规划 */

2025-05-07T09:20:54Z

动态规划

←上一版本		2025年5月7日 (三) 17:20的版本
第130行：		第130行：

	1950由理查德贝尔曼开发。		1950由理查德贝尔曼开发。

			'''切记局部最优不是全局最优——<s>信息巨佬补</s>'''

	=== 打点法 ===		=== 打点法 ===

Hukk：修改标点符号

2025-04-23T08:00:28Z

修改标点符号

←上一版本		2025年4月23日 (三) 16:00的版本
第7行：		第7行：
	* 同源性只能用有没有来形容，不能说“70%同源”这种胡话，类似于“这个布尔函数<ref>布尔函数是信息技术课上的一种数据存储形式		* 同源性只能用有没有来形容，不能说“70%同源”这种胡话，类似于“这个布尔函数<ref>布尔函数是信息技术课上的一种数据存储形式

	只有0和正数两种值</ref>有80%~~是0”~~		只有0和正数两种值</ref>有80%是0”。
	* ~~也就是说，一致度要求完全一样，相似度只要性质差不多也能算进去~~		* 也就是说，一致度要求完全一样，相似度只要性质差不多也能算进去。
	* ~~同源性是定性概念，一致度和相似度是定量概念~~		* 同源性是定性概念，一致度和相似度是定量概念。

	== 比对类型 ==		== 比对类型 ==
	~~局部比对找出两个序列中高相似度的片段~~		局部比对找出两个序列中高相似度的片段。

	~~全局比对构建打分矩阵，打分。。。~~		全局比对构建打分矩阵，打分……

	~~半局部比对对一条序列使用局部比对，另一条使用全局比对，如此求得最大匹配度~~		半局部比对对一条序列使用局部比对，另一条使用全局比对，如此求得最大匹配度。

	== 比对矩阵 ==		== 比对矩阵 ==
	~~如果希望对蛋白质或核酸序列进行比对，需要借助于矩阵（对于计分表的更高端叫法）打分，分高者相似~~		对蛋白质或核酸序列进行比对，需要借助于矩阵（对于计分表的更高端叫法）打分，得分越高则代表二者越相似。

	=== 核酸矩阵 ===		=== 核酸矩阵 ===
第106行：		第106行：
	PAM矩阵是目前蛋白质序列比较中最广泛使用的记分方法之一，基础的PAM-1 矩阵反应的是进化产生的'''每一百个氨基酸平均发生一个突变的量值（统计方法得到）'''。		PAM矩阵是目前蛋白质序列比较中最广泛使用的记分方法之一，基础的PAM-1 矩阵反应的是进化产生的'''每一百个氨基酸平均发生一个突变的量值（统计方法得到）'''。

	PAM-1是由相似度大于85%~~的序列计算产生~~		PAM-1是由相似度大于85%的序列计算产生。

	PAM-1 自乘n次，可以得到PAM-n，即发生了多次突变。也就是说PAM越大，相似度越小。n即允许发生的点突变数。		PAM-1 自乘n次，可以得到PAM-n，即发生了多次突变。也就是说PAM越大，相似度越小。n即允许发生的点突变数。

	==== BLOSUM矩阵 ====		==== BLOSUM矩阵 ====
	BLOSUM 矩阵都是通过对大量符合特定要求的序列计算而来。如BLOSUM62表示计算了相似度>62%~~的蛋白质序列得到结果~~		BLOSUM 矩阵都是通过对大量符合特定要求的序列计算而来。如BLOSUM62表示计算了相似度>62%的蛋白质序列得到结果。

	~~PAM基于全局比对，BLOSUM基于局部比对~~		PAM基于全局比对，BLOSUM基于局部比对。
	[[文件:屏幕截图(8).png\|缩略图\|比较PAM和BLOSUM]]		[[文件:屏幕截图(8).png\|缩略图\|比较PAM和BLOSUM]]

	==== GCM矩阵/遗传密码子矩阵 ====		==== GCM矩阵/遗传密码子矩阵 ====
	~~两个氨基酸之间密码子所需的突变次数越多，替换代价越大（多用于进化树）~~		两个氨基酸之间密码子所需的突变次数越多，替换代价越大。（多用于进化树）

	==== 疏水矩阵 ====		==== 疏水矩阵 ====
	~~疏水性相近的氨基酸得分更高~~		疏水性相近的氨基酸得分更高。

	== 比对序列 ==		== 比对序列 ==

	=== 动态规划 ===		=== 动态规划 ===
	~~核心原理是，如果你每一步都是最优解，那最后也一定是最优解~~		核心原理是，如果你每一步都是最优解，那最后也一定是最优解。

	~~也就是说，因为你在列表走格子的时候每次都取了最优解，所以比对结果也应该是最优解~~		也就是说，因为你在列表走格子的时候每次都取了最优解，所以比对结果也应该是最优解。

	~~1950由理查德贝尔曼开发~~		1950由理查德贝尔曼开发。

	=== 打点法 ===		=== 打点法 ===
	[[文件:序列比对笑传之compare cat brothers.png\|缩略图\|compare cat brothers]]		[[文件:序列比对笑传之compare cat brothers.png\|缩略图\|compare cat brothers]]将两条序列用这一张图中的方法分别列出，形成一个二维表格，在字母相同（实际上是氨基酸相同）的位置打上点。
	~~首先您需要找到两条序列THEFASTCAT和THEFATCAT~~

	~~将他们将两条序列用这一张图中的方法分别列出，形成一个二维表格，在字母相同（实际上是氨基酸相同）的位置打上点~~		如果打点后产生了对角线或者与其相同的平行线，这些区域具有一致性。

	~~如果您发现打点后产生了对角线或者与其相同的平行线，这些区域具有一致性~~		可用于寻找序列中的重复片段。

	~~可用于寻找序列中的重复片段~~

	许多名字里带有Dot的软件可以用打点法比对序列如Dnadot，（dotlet似乎属于SIB		许多名字里带有Dot的软件可以用打点法比对序列如Dnadot，（dotlet似乎属于SIB

	=== 全局比对之Needleman-Swunch算法 ===		=== 全局比对之Needleman-Swunch算法 ===
	~~1970年由名字里的二人开发~~		1970年由名字里的二人开发。

	换一种方法理解打点法，您会发现她很像一种打分，只不过是0/1		换一种方法理解打点法，您会发现她很像一种打分，只不过是0/1

比对算法 - 版本历史

点击空白处刷新：​/* BLAST矩阵 */

卡布喜·米糖：​/* 全局比对之Needleman-Wunsch算法 */（算法发明者名字打错了）

Jerrywang：​添加了动态规划相关内容

Jerrywang：​添加了关于动态规划算法的详细阐述和正确性证明。我学过信息学。

2026年1月9日 (五) 09:28 扶摇棘

Sofia：​自动添加 Sofia 模板和分类

2025年7月16日 (三) 03:10 W. Machine

佛山水泵厂中学：​/* 动态规划 */

佛山水泵厂中学：​/* 动态规划 */

Hukk：​修改标点符号

点击空白处刷新：/* BLAST矩阵 */

卡布喜·米糖：/* 全局比对之Needleman-Wunsch算法 */（算法发明者名字打错了）

Jerrywang：添加了动态规划相关内容

Jerrywang：添加了关于动态规划算法的详细阐述和正确性证明。我学过信息学。

Sofia：自动添加 Sofia 模板和分类

佛山水泵厂中学：/* 动态规划 */

佛山水泵厂中学：/* 动态规划 */

Hukk：修改标点符号