Please use this identifier to cite or link to this item:
Title: Towards a better solution to the shortest common supersequence problem: The deposition and reduction algorithm
Authors: Ning, K.
Leong, H.W. 
Issue Date: 2006
Citation: Ning, K., Leong, H.W. (2006). Towards a better solution to the shortest common supersequence problem: The deposition and reduction algorithm. BMC Bioinformatics 7 (SUPPL.4). ScholarBank@NUS Repository.
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. The deposition process is responsible for generating a small set of common supersequences; and the reduction process shortens these common supersequences by removing some characters while preserving the common supersequence property. Our evaluation on simulated data and real DNA and protein sequences show that our algorithm consistently produces the best results compared to many well-known heuristic algorithms, and especially on large instances. Conclusion: Our DR algorithm provides a partial answer to the open problem of designing efficient heuristic algorithm for SCS problem on many long sequences. Our algorithm has a bounded approximation ratio. The algorithm is efficient, both in running time and space complexity and our evaluation shows that it is practical even for SCS problems on many long sequences. © 2006 Ning and Leong; licensee BioMed Central Ltd.
Source Title: BMC Bioinformatics
ISSN: 14712105
DOI: 10.1186/1471-2105-7-S4-S12
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
2006-towards_better_solution_shortest-published.pdf280.27 kBAdobe PDF




checked on Mar 14, 2019


checked on Mar 6, 2019

Page view(s)

checked on Mar 10, 2019


checked on Mar 10, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.