Towards a better solution to the shortest common supersequence problem: The deposition and reduction algorithm

Abstract

The problem of finding the shortest common supersequence (SCS) of a set of sequences is an important problem with applications in many areas. It is also a key problem in biological sequences analysis. However, the problem is well-known to be NP-complete. Many heuristic algorithms have been proposed [1, 2]. However, the performances of many current heuristic algorithms are not very good, especially on many long sequences. In this paper, we have proposed a new heuristic algorithm, the Deposition and Reduction algorithm, for the SCS problem on biological sequence analysis. This algorithm is based on our previous study on DNA oligos [3]. In this paper, we extend the study to also include protein sequences (with an alphabet size of 20). The algorithm is proven to have a guaranteed performance ratio. And the experiments clearly show that with respect to the length of the results, our algorithm can perform comparative to or better than many of the best known algorithms, especially in situations where there are many long sequences. Our algorithm is also efficient in time and space needed. © 2006 IEEE.