Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Large neighborhood search for the most strings with few bad columns problem

Autor
Lizárraga, E.; Blesa, M.; Blum, C.; Raidl, G.
Tipus d'activitat
Article en revista
Revista
Soft computing
Data de publicació
2017-09
Volum
21
Número
17
Pàgina inicial
4901
Pàgina final
4915
DOI
https://doi.org/10.1007/s00500-016-2379-4 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/104908 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007%2Fs00500-016-2379-4 Obrir en finestra nova
Resum
In this work, we consider the following NP-hard combinatorial optimization problem from computational biology. Given a set of input strings of equal length, the goal is to identify a maximum cardinality subset of strings that differ maximally in a pre-defined number of positions. First of all, we introduce an integer linear programming model for this problem. Second, two variants of a rather simple greedy strategy are proposed. Finally, a large neighborhood search algorithm is presented. A compr...
Citació
Lizárraga, E., Blesa, M., Blum, C., Raidl, G. Large neighborhood search for the most strings with few bad columns problem. "Soft computing", Setembre 2017, vol. 21, núm. 17, p. 4901-4915.
Paraules clau
Most Strings With Few Bad Columns, Integer Linear Programming, Large Neighborhood Search
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius