Please use this identifier to cite or link to this item: https://doi.org/10.1186/1471-2105-7-S4-S12
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
Source: 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. https://doi.org/10.1186/1471-2105-7-S4-S12
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39181
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

OPEN

PublishedView/Download

SCOPUSTM   
Citations

14
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

11
checked on Dec 11, 2017

Page view(s)

61
checked on Dec 9, 2017

Download(s)

2
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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