A Block Recursive Sequence Alignment Algorithm

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) +L_smin (m-1, n-1) +C₂ and 5 (m+n) +L_s (m+n-2) +C₂ 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.