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...
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