摘要
利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为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.
出处
《北京工业大学学报》
EI
CAS
CSCD
北大核心
2010年第2期255-260,共6页
Journal of Beijing University of Technology
基金
国家自然科学基金资助项目(60775010)
北京市自然科学基金资助项目(4052005)
北京市属市管高等学校"中青年骨干教师培养计划"资助项目PHR(IHLB)
