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

ABSTRACT:

Background

The problem of finding a Shortest Common Supersequence (SCS) of a set of sequences is an important problem with applications in many areas. It is a key problem in biological sequences analysis. The SCS problem is well-known to be NP-complete. Many heuristic algorithms have been proposed. Some heuristics work well on a few long sequences (as in sequence comparison applications); others work well on many short sequences (as in oligo-array synthesis). Unfortunately, most do not work well on large SCS instances where there are many, long sequences.

Results

In this paper, we present a Deposition and Reduction (DR) algorithm for solving large SCS instances of biological sequences. There are two processes in our DR algorithm: deposition process, and reduction process. Th

SUBMITTER: Ning K 

PROVIDER: S-EPMC1780115 | biostudies-literature | 2006 Dec

REPOSITORIES: biostudies-literature