Efficient algorithms for similarity search

The problem of our interest takes as input a database of m sequences from a n alphabet Sigma and an integer k. The goal is to report all the pairs of s equences that have a matching subsequence of length at least k. We employ t wo algorithms to solve this problem. The first algorithm is based on sortin g and the second is based on generalized suffix trees. We provide experimen tal data comparing the performances of these algorithms. The generalized su ffix tree based algorithm performs better than the sorting based algorithm.