Needleman-Wunsch 算法是一种用于比较两条 DNA 序列或蛋白质序列的算法。这种算法通过计算两个序列之间的最佳匹配得分来确定它们之间的相似性。 该算法的基本思想是，将两条序列对齐并计算它们之间的匹配得分。匹配得分是指两个序列中的相同字符的数量。如果两个字符不同，则会受到一个惩罚。此外，还可以添加一个空位罚分，以防止序列之间出现过多的空位。 在 Needleman-Wunsch 算法中，使用动态规划方法来找到最佳匹配得分。首先，创建一个二维矩阵，其中行和列分别代表两条序列。然后，从左上角开始，填充矩阵中的每个单元格。对于每个单元格，它可以选择与其上方、左侧或左上方的单元格进行匹配。选择哪种匹配取决于它们之间的匹配得分和空位罚分。 最终，当矩阵的最后一行和最后一列被填充时，就可以找到最佳匹配得分。这个得分表示两条序列之间的相似程度。同时，可以通过回溯矩阵来找到最佳匹配路径，从而得到对齐后的序列。 总的来说，Needleman-Wunsch 算法是一种非常有用的工具，可以帮助生物学家和其他研究人员分析和比较 DNA 或蛋白质序列。 2.1.3 Blast 算法 Blast（Basic Local Alignment Search Tool）算法是一种用于生物信息学中的序列比对算法，由美国国家生物技术信息中心（NCBI）开发。它的主要功能是找出两个或多个序列之间的相似性，并确定它们的同源性。 Blast 算法的基本原理是基于局部比对的思想，即在两个序列中寻找一段尽可能长且相似度尽可能高的子序列。这个子序列被称为“最佳局部比对”。Blast 算法通过使用动态规划的方法来计算两个序列之间的相似度得分，并使用一定的阈值来判断是否为有效的比对结果。 Blast 算法主要包括以下几种类型： 1. Blastn：用于核酸序列之间的比对。 2. Blastp：用于蛋白质序列之间的比对。 3. Blastx：将核酸序列翻译成所有可能的蛋白质序列，然后与蛋白质数据库进行比对。 4. Tblastn：将蛋白质序列与核酸数据库进行比对。 5. Tblastx：将两个核酸序列分别翻译成所有可能的蛋白质序列，然后进行比对。 Blast 算法的优点是速度快、准确度高，可以处理大规模的数据。但是它也存在一些缺点，例如无法处理插入和删除等复杂的序列变异情况，以及对于短序列的比对效果不佳等。