Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/160603
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Campo DC | Valor | Lengua/Idioma |
---|---|---|
dc.contributor.author | Blum, Christian | - |
dc.contributor.author | Blesa, Maria J. | - |
dc.date.accessioned | 2018-02-13T14:36:41Z | - |
dc.date.available | 2018-02-13T14:36:41Z | - |
dc.date.issued | 2018 | - |
dc.identifier | doi: 10.1016/j.asoc.2017.10.005 | - |
dc.identifier | issn: 1568-4946 | - |
dc.identifier.citation | Applied Soft Computing Journal 62: 15- 28 (2018) | - |
dc.identifier.uri | http://hdl.handle.net/10261/160603 | - |
dc.description.abstract | Finding 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. | - |
dc.description.sponsorship | This work was partially funded by project SGR 2014-1034 ( AGAUR, Generalitat de Catalunya ). Our experiments have been executed in the High Performance Computing environment managed by the rd lab at the Technical University of Barcelona ( http://rdlab.cs.upc.edu ) and we would like to thank them for their support. | - |
dc.publisher | Elsevier | - |
dc.rights | closedAccess | - |
dc.subject | Hybrid algorithms | - |
dc.subject | Combinatorial optimization | - |
dc.subject | Longest common subsequences | - |
dc.subject | Integer linear programming | - |
dc.subject | Heuristic | - |
dc.title | Hybrid techniques based on solving reduced problem instances for a longest common subsequence problem | - |
dc.type | artículo | - |
dc.identifier.doi | 10.1016/j.asoc.2017.10.005 | - |
dc.date.updated | 2018-02-13T14:36:41Z | - |
dc.description.version | Peer Reviewed | - |
dc.language.rfc3066 | eng | - |
dc.contributor.funder | Generalitat de Catalunya | - |
dc.contributor.funder | Universitat Politècnica de Catalunya | - |
dc.relation.csic | Sí | - |
dc.identifier.funder | http://dx.doi.org/10.13039/501100002809 | es_ES |
dc.type.coar | http://purl.org/coar/resource_type/c_6501 | es_ES |
item.openairetype | artículo | - |
item.grantfulltext | none | - |
item.cerifentitytype | Publications | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.fulltext | No Fulltext | - |
Aparece en las colecciones: | (IIIA) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
accesoRestringido.pdf | 15,38 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
8
checked on 08-abr-2024
WEB OF SCIENCETM
Citations
5
checked on 14-feb-2024
Page view(s)
249
checked on 23-abr-2024
Download(s)
83
checked on 23-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.