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.5
mn and 3
mn in general cases but between 1.5
mn and 2
mn 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.