Please use this identifier to cite or link to this item:
Title: The multiple sequence sets: Problem and heuristic algorithms
Authors: Ning, K.
Leong, H.W. 
Keywords: Distribution and deposition
Multiple sequence sets
Performance ratio
Sequence features
Shortest common supersequence
Issue Date: 2011
Citation: Ning, K., Leong, H.W. (2011). The multiple sequence sets: Problem and heuristic algorithms. Journal of Combinatorial Optimization 22 (4) : 778-796. ScholarBank@NUS Repository.
Abstract: "Sequence set" is a mathematical model used in many applications such as biological sequences analysis and text processing. However, "single" sequence set model is not appropriate for the rapidly increasing problem size. For example, very large genome sequences should be separated and processed chunk by chunk. For these applications, the underlying mathematical model is "Multiple Sequence Sets" (MSS). To process multiple sequence sets, sequences are distributed to different sets and then sequences on each set are processed in parallel. Deriving effective algorithm for MSS processing is challenging. In this paper, we have first defined the cost functions for the problem of Process of Multiple Sequence Sets (PMSS). The PMSS problem is then formulated as to minimize the total cost of process. Based on the analysis of the features of multiple sequence sets, we have proposed the Distribution and Deposition (DDA) algorithm and DDA * algorithm for PMSS problem. In DDA algorithm, the sequences are first distributed to multiple sets according to their alphabet contents; then sequences in each set are processed by deposition algorithm. The DDA * algorithm differs from the DDA algorithm in that the DDA * algorithm distributes sequences by clustering based on a set of sequence features. Experiments showed that the results of DDA and DDA * are always smaller than other algorithms, and DDA * outperformed DDA in most instances. The DDA and DDA 3 algorithms were also efficient both in time and space. © 2010 Springer Science+Business Media, LLC.
Source Title: Journal of Combinatorial Optimization
ISSN: 13826905
DOI: 10.1007/s10878-010-9329-3
Appears in Collections:Staff Publications

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

Page view(s)

checked on Apr 21, 2018

Google ScholarTM



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