A Block Recursive Algorithm for Sequence Alignment
Based on a new way to compute check points, this paper presents a Block Recursive sequence alignment algorithm, which can run in a time requirement between 1.5mn and 3mn in general cases but between 1.5mn and 2mn for sequences with high similarities. Still, the algorithm keeps a linear space requirement and always guarantees an optimal alignment result. Some experiments show that it runs at least 10％ faster than the Hirschberg algorithm if the two compared sequences has a normalized edit distance less than 0.25.
sequences alignment Hirschberg algorithm Block Recursive linear space complezity check point
Wang Fang-Yuan Li Yu-Jian
Cellege of Computer Science and Technology Beijing University of Technology Beijing, China
国际会议
上海
英文
604-607
2008-05-16（万方平台首次上网日期，不代表论文的发表时间）