Abstract
We design a new sequence alignment system that base on L. Delcher’s [1] idea to aligning very long sequences. Because the traditional sequence alignment methods [12] spend too much time and memory space when align very long sequences. We use an idea, longest common subsequence (LCS), instead of suffix tree [5], and then we can solve sequence alignment problems more flexible. But it spends more time than using suffix tree. We improve LCS by using hash table, and it is a kind of trade off method between time and space. We also find some properties of LCS. So we can combine two shorter LCS’s results to get a longer LCS’s approximate result. In our experiment, we show our method is an effective method in practice.