<span style="color: rgb(51, 51, 51); font-family: " pingfang="" sc",="" "lantinghei="" "microsoft="" yahei",="" arial,="" 宋体,="" sans-serif,="" tahoma;="" font-size:="" 16px;"="">序列比对（Sequence Alignment）的基本问题是比较两个或两个以上符号序列的相似性或不相似性。从生物学的初衷来看，这一问题包含了以下几个意义：从相互重叠的序列片断中重构DNA的完整序列。在各种试验条件下从探测数据（probe data）中决定物理和基因图存贮，遍历和比较数据库中的DNA序列，比较两个或多个序列的相似性，在数据库中搜索相关序列和子序列，寻找核苷酸（nucleotides）的连续产生模式，找出蛋白质和DNA序列中的信息成分。序列比对考虑了DNA序列的生物学特性，如序列局部发生的插入，删除（前两种简称为indel）和替代，序列的目标函数获得序列之间突变集最小距离加权和或最大相似性和，对齐的方法包括全局对齐，局部对齐，代沟惩罚等。两个序列比对常采用动态规划算法，这种算法在序列长度较小时适用，然而对于海量基因序列（如人的DNA序列高达10^9bp），这一方法就不太适用，甚至采用算法复杂性为线性的也难以奏效。因此，启发式方法的引入势在必然，著名的BLAST和FASTA算法及相应的改进方法均是从此前提出发的。
 

分类