生物序列比对算法的研究

随着生物信息学数据的大量积累,通过对核酸序列或蛋白质序列进行比对,可以有效地分析和预测一些新发现基因的功能。序列比对的理论基础是进化学说,如果两个序列之间具有足够的相似性,可以推测二者有共同的进化祖先;二个具有同源性的生物,其序列具有一定的相似性。如果一个新测定的DNA序列与一已知的基因序列很相似,那么,该基因序列含有与已知基因序列相似的结构和功能。因此,序列比对方法的应用对于基因结构和功能的研究具有较大的实际意义。双序列比对是序列分析的常用方法之一,是多序列比对和数据库搜索的基础。传统的双序列比对算法时间和空间复杂度均为O(m*n)。我们在介绍传统的动态规划算法后,将就时间和空间方面提出建议,并加以具体描述。