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|
|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 . 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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
WEB OF SCIENCETM
checked on Nov 20, 2017
checked on Dec 10, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.