分块递归序列比对算法

    A Block Recursive Sequence Alignment Algorithm

    • 摘要: 利用分块递归的思想, 结合检查点计算方法, 提出一种线性空间复杂度序列比对算法, 对于给定长为mn的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%以上.

       

      Abstract: 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) +Lsmin (m-1, n-1) +C2 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.

       

    /

    返回文章
    返回