Please use this identifier to cite or link to this item: https://doi.org/10.1109/IMSCCS.2006.136
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. First International Multi- Symposiums on Computer and Computational Sciences, IMSCCS'06 1 : 84-90. ScholarBank@NUS Repository. https://doi.org/10.1109/IMSCCS.2006.136
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.
Source Title: First International Multi- Symposiums on Computer and Computational Sciences, IMSCCS'06
URI: http://scholarbank.nus.edu.sg/handle/10635/41639
ISBN: 0769525814
DOI: 10.1109/IMSCCS.2006.136
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

WEB OF SCIENCETM
Citations

1
checked on Nov 20, 2017

Page view(s)

63
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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