Smith-Waterman算法是一种用于生物信息学中序列比对的算法,特别是用于局部序列比对。它由Temple F. Smith和Michael S. Waterman在1981年提出。与全局比对算法(如Needleman-Wunsch算法)不同,Smith-Waterman算法专注于找出两个序列之间的最佳局部对齐,而不是整个序列的对齐。一、基本概念
Needleman-Wunsch(NW)算法是一种用于生物信息学中的序列比对算法,特别是用于蛋白质和核酸序列的全局比对。这个算法由Saul B. Needleman和Christian D. Wunsch在1970年提出,其目的是找到两个序列之间最长的公共子序列,即使在序列的两端也可以存在不匹配的情况。一、算法原理Needleman-Wunsch算法基于动态规划原理,构建一个二维矩阵来记录两个序列之间的比对信息。矩阵的大小为(m+1)×(n+1),其中m和n分别分别是两个序列的长度。矩阵的第一行和第一列分别代表序列的空白(即序列的开始处),并且初始化为0。
BLAST算法(Basic Local Alignment Search Tool),是一种在生物信息学领域广泛使用的序列比对搜索工具。它是由美国国家生物技术信息中心(NCBI)开发和管理的,主要功能是将输入的核酸或蛋白质序列与数据库中的已知序列进行比对,以获得序列相似度等信息,进而判断序列的来源或进化关系。