系统进化分析是生物信息学中的重要研究领域,它的主要研究手段是从一组同源的DNA或蛋白质序列出发,计算各个序列之间的进化距离,进而构建反映物种进化关系的进化树。构建进化树的方法主要分为三类,即距离法、简约法和似然法。本文将对距离法做一些探索性的改进研究。传统的距离法一般通过多序列比对计算距离矩阵,而多序列比对是一个NP难问题,在序列数目较多时难以获得最优比对结果。一种解决方法是采用启发式的多序列比对算法,另一种方法是通过计算某种序列之间的两两距离代替多序列比对。对于计算两两距离的方法而言,Hansan H.Out和Khalid Sayood提出了一种基于LZ复杂度的距离,能够正确地重构某些进化树。本文则试图通过利用一种满足三角不等式的归一化编辑距离来绕过多序列比对的困难,但仍然需要对序列进行两两比对分析。序列的两两比对通常采用Needle-Wunschman算法,其时间和空间复杂度均为O（mn） （m, n为比对两序列的长度）,对长序列容易超过计算机的内存限制。Hirschberg算法具有线性空间复杂度,可以用来解决Needle-Wunschman算法的内存问题,但是计算时间需求要多一倍,约为O（ ）。本文试图在时间和空间复杂度之间进行折衷,通过引入一种新的检查点（Check_Point）计算方法,提出了基于分块递归的序列比对算法。理论分析表明,该算法的空间需求大约在到O（5（m+n） + L_s×min（ m - 1, n - 1） + C₂）O （5（ m + n ） + L_s×（ m + n - 2） + C₂）之间,时间需求介于O（1.5mn）到O （3m n ）之间,但在序列相似度较高时介于O（1.5mn ）到O （2 mn）之间。同源物种的线粒体全基因组序列比对实验进一步证明了新算法的正确性,表明在序列之间的归一化编辑距离小于0.25时,新算法能够比Hirschberg算法快10%以上。因此分块递归序列比对算法在诸如同源序列分析、系统进化树构造等领域具有一定的应用价值。由于直接通过序列比对得到的距离易受序列长度影响,与真实进化距离的差别较大,因此需要进行归一化处理才能减小序列长度对构建进化树的影响。本文采用的归一化编辑距离是一种取值介于[0,1]之间的度量,由于能够完全满足三角不等式,所以还可以避免某些与进化树相关的负枝长问题。最后,本文通过两组实验说明了这种归一化编辑距离能够用来成功地构建某些已经被多种方法验证过的进化树。