分块递归序列比对算法  

A Block Recursive Sequence Alignment Algorithm

作　　者：李玉鑑[1] 王方圆[1] 

机构地区：[1]北京工业大学计算机学院,北京100124

出　　处：《北京工业大学学报》2010年第2期255-260,共6页Journal of Beijing University of Technology

基　　金：国家自然科学基金资助项目(60775010);北京市自然科学基金资助项目(4052005);北京市属市管高等学校"中青年骨干教师培养计划"资助项目PHR(IHLB)

摘　　要：利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为m和n的2条序列,空间需求约5(m+n)+Lsmin(m-1,n-1)+C2~5(m+n)+Ls(m+n-2)+C2,而时间需求一般情况下约1.5mn^3mn,在待比对序列相似度较高时约1.5mn^2mn,并通过同源物种全基因组序列比对实验证明,如果归一化编辑距离小于0.25,那么该算法比Hirschberg算法快10%以上.Using a new way to compute check points, the authors present the Block Recursive Sequence Alignment Algorithm with a linear space requirement between 5 （ m ＋ n） ＋ Ls min （ m - 1, n - 1 ） ＋ Cz and 5 （ m ＋ n） ＋ Ls （m ＋ n - 2） ＋ C2 for the given two sequences which length is m, n apparatively. The algorithm has a time requirement between 1.5mn and 3mn in general cases but between 1.5mn and 2mn for sequences with high similarities. Some experiments in aligning genomes from homology species have further shown that it runs correctly and at least 10% faster than that of the Hirschberg Algorithm if the two compared sequences have a normalized edit distance less than 0.25.

关 键 词：序列比对 Hirschberg算法 分块递归 线性空间复杂度 检查点 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]