Skip to main content
Erschienen in: Soft Computing 17/2017

06.10.2016 | Focus

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

verfasst von: Evelia Lizárraga, Maria J. Blesa, Christian Blum, Günther R. Raidl

Erschienen in: Soft Computing | Ausgabe 17/2017

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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 comprehensive experimental comparison among the proposed techniques shows, first, that larger neighborhood search generally outperforms both greedy strategies. Second, while large neighborhood search shows to be competitive with the stand-alone application of CPLEX for small- and medium-sized problem instances, it outperforms CPLEX in the context of larger instances.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Boucher C, Landau GM, Levy A, Pritchard D, Weimann O (2013) On approximating string selection problems with outliers. Theor Comput Sci 498:107–114MathSciNetCrossRefMATH Boucher C, Landau GM, Levy A, Pritchard D, Weimann O (2013) On approximating string selection problems with outliers. Theor Comput Sci 498:107–114MathSciNetCrossRefMATH
Zurück zum Zitat Gusfield D (1997) Algorithms on strings, trees, and sequences. Computer science and computational biology. Cambridge University Press, CambridgeCrossRefMATH Gusfield D (1997) Algorithms on strings, trees, and sequences. Computer science and computational biology. Cambridge University Press, CambridgeCrossRefMATH
Zurück zum Zitat Landau GM, Schmidt JP, Sokol D (2001) An algorithm for approxixmate tandem repeat. J Comput Biol 8(1):1–18CrossRef Landau GM, Schmidt JP, Sokol D (2001) An algorithm for approxixmate tandem repeat. J Comput Biol 8(1):1–18CrossRef
Zurück zum Zitat Lizárraga E, Blesa MJ, Blum C, Raidl GR (2015) On solving the most strings with few bad columns problem: an ILP model and heuristics. In: Proceedings of INISTA 2015—international symposium on innovations in intelligent systems and applications, IEEE Press, pp 1–8 Lizárraga E, Blesa MJ, Blum C, Raidl GR (2015) On solving the most strings with few bad columns problem: an ILP model and heuristics. In: Proceedings of INISTA 2015—international symposium on innovations in intelligent systems and applications, IEEE Press, pp 1–8
Zurück zum Zitat López-Ibáñez M, Dubois-Lacoste J, Stützle T, Birattari M (2011) The \(\sf irace\) package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université libre de Bruxelles, Belgium López-Ibáñez M, Dubois-Lacoste J, Stützle T, Birattari M (2011) The \(\sf irace\) package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université libre de Bruxelles, Belgium
Zurück zum Zitat Meneses C, Oliveira C, Pardalos P (2005) Optimization techniques for string selection and comparison problems in genomics. IEEE Eng Med Biol Mag 24(3):81–87CrossRef Meneses C, Oliveira C, Pardalos P (2005) Optimization techniques for string selection and comparison problems in genomics. IEEE Eng Med Biol Mag 24(3):81–87CrossRef
Zurück zum Zitat Mousavi S, Babaie M, Montazerian M (2012) An improved heuristic for the far from most strings problem. J Heuristics 18:239–262CrossRef Mousavi S, Babaie M, Montazerian M (2012) An improved heuristic for the far from most strings problem. J Heuristics 18:239–262CrossRef
Zurück zum Zitat Pappalardo E, Pardalos PM, Stracquadanio G (2013) Optimization approaches for solving string selection problems. SpringerBriefs in optimization. Springer, New YorkCrossRefMATH Pappalardo E, Pardalos PM, Stracquadanio G (2013) Optimization approaches for solving string selection problems. SpringerBriefs in optimization. Springer, New YorkCrossRefMATH
Zurück zum Zitat Pisinger D, Ropke S (2010) Large neighborhood search. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics, International series in operations research and management science, vol 146. Springer, New York, pp 399–419 Pisinger D, Ropke S (2010) Large neighborhood search. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics, International series in operations research and management science, vol 146. Springer, New York, pp 399–419
Zurück zum Zitat Rajasekaran S, Hu Y, Luo J, Nick H, Pardalos PM, Sahni S, Shaw G (2001) Efficient algorithms for similarity search. J Comb Optim 5(1):125–132MathSciNetCrossRefMATH Rajasekaran S, Hu Y, Luo J, Nick H, Pardalos PM, Sahni S, Shaw G (2001) Efficient algorithms for similarity search. J Comb Optim 5(1):125–132MathSciNetCrossRefMATH
Zurück zum Zitat Rajasekaran S, Nick H, Pardalos PM, Sahni S, Shaw G (2001) Efficient algorithms for local alignment search. J Comb Optim 5(1):117–124MathSciNetCrossRefMATH Rajasekaran S, Nick H, Pardalos PM, Sahni S, Shaw G (2001) Efficient algorithms for local alignment search. J Comb Optim 5(1):117–124MathSciNetCrossRefMATH
Zurück zum Zitat Smith T, Waterman M (1981) Identification of common molecular subsequences. J Mol Biol 147(1):195–197CrossRef Smith T, Waterman M (1981) Identification of common molecular subsequences. J Mol Biol 147(1):195–197CrossRef
Metadaten
Titel
Large neighborhood search for the most strings with few bad columns problem
verfasst von
Evelia Lizárraga
Maria J. Blesa
Christian Blum
Günther R. Raidl
Publikationsdatum
06.10.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 17/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-016-2379-4

Weitere Artikel der Ausgabe 17/2017

Soft Computing 17/2017 Zur Ausgabe