English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/160603
Share/Impact:
Statistics
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Title

Hybrid techniques based on solving reduced problem instances for a longest common subsequence problem

AuthorsBlum, Christian ; Blesa, Maria J.
KeywordsHybrid algorithm
Combinatorial optimization
Longest common subsequences
Integer linear programming
Heuristic
Issue Date2018
PublisherElsevier
CitationApplied Soft Computing Journal 62: 15- 28 (2018)
AbstractFinding the longest common subsequence of a given set of input strings is a relevant problem arising in various practical settings. One of these problems is the so-called longest arc-preserving common subsequence problem. This NP-hard combinatorial optimization problem was introduced for the comparison of arc-annotated ribonucleic acid (RNA) sequences. In this work we present an integer linear programming (ILP) formulation of the problem. As even in the context of rather small problem instances the application of a general purpose ILP solver is not viable due to the size of the model, we study alternative ways based on model reduction in order to take profit from this ILP model. First, we present a heuristic way for reducing the model, with the subsequent application of an ILP solver. Second, we propose the application of an iterative hybrid algorithm that makes use of an ILP solver for generating high quality solutions at each iteration. Experimental results concerning artificial and real problem instances show that the proposed techniques outperform an available technique from the literature.
URIhttp://hdl.handle.net/10261/160603
Identifiersdoi: 10.1016/j.asoc.2017.10.005
issn: 1568-4946
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work
 

Related articles:


WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.