求进化距离的改进算法  

The Improved Algorithm Computerizing the Evolutionary Distance

作　　者：谢扬 王攻本[2] 

机构地区：[1]北京大学计算机科学与技术系 [2]北京大学分校

出　　处：《北京大学学报（自然科学版）》1991年第1期43-50,共8页Acta Scientiarum Naturalium Universitatis Pekinensis

基　　金：国家自然科学基金

摘　　要：本文在Seller算法的基础上提出了一个新的求进化距离的改进算法。该法通过计算来求出一条最短路径,去掉了指针矩阵。并且在求最短路径时采用了分支与定界、对角线方向扩展、相邻对角线传递等技术。从而不仅使改进算法的空间耗费由Seller算法的平方级(O(m×n))降为线性级(O(m+n)),并且其时间耗费仍能保持Fickett算法的结果。该算法已在IBM-PC/AT上实现。This paper describes a new improved algorithm computerizing the evolutionary distance between two molecular sequences, based on Seller's algorithm. The new algoruthm eliminates the pointer matrix and illustrates one of the shortest pathes with repetitive computation. It employs many sophisticated techniques such as branch and bound, diagonal stretching and adjacant diagonal passing-on. The space-complexity of the improved algorithm is linear, while it's time-complexity equals to that of Fickett's result.

关 键 词：进化距离 算法 生物分子 序列 

分 类 号：Q71[生物学—分子生物学]