Christian Blum is a senior scientist at the Spanish National Research Council (CSIC) in Bellaterra, Spain. Paola Festa is Associate Professor in Operations Research at the University of Naples Federico II, Italy.

• Preface ixAcknowledgments xiList of Acronyms xiiiChapter 1 Introduction 11.1 Complete methods for combinatorial optimization 31.1.1 Linear programming relaxation 61.1.2 Cutting plane techniques 91.1.3 General-purpose ILP solvers 181.1.4 Dynamic programming 191.2 Approximate methods: metaheuristics 201.2.1 Ant colony optimization 221.2.2 Evolutionary algorithms 241.2.3 Greedy randomized adaptive search procedures 251.2.4 Iterated local search 261.2.5 Simulated annealing 271.2.6 Other metaheuristics 291.2.7 Hybrid approaches 291.3 Outline of the book 32Chapter 2 Minimum Common String Partition Problem 372.1 The MCSP problem 382.1.1 Technical description of the UMCSP problem 382.1.2 Literature review 392.1.3 Organization of this chapter 402.2 An ILP model for the UMCSP problem 402.3 Greedy approach 422.4 Construct, merge, solve and adapt 422.5 Experimental evaluation 452.5.1 Benchmarks 462.5.2 Tuning CMSA 462.5.3 Results 472.6 Future work 54Chapter 3 Longest Common Subsequence Problems 553.1 Introduction 563.1.1 LCS problems 563.1.2 ILP models for LCS and RFLCS problems 593.1.3 Organization of this chapter 613.2 Algorithms for the LCS problem 613.2.1 Beam search 613.2.2 Upper bound 643.2.3 Beam search framework 643.2.4 Beam–ACO 673.2.5 Experimental evaluation 713.3 Algorithms for the RFLCS problem 753.3.1 CMSA 773.3.2 Experimental evaluation 803.4 Future work 85Chapter 4 The Most Strings With Few Bad Columns Problem 874.1 The MSFBC problem 884.1.1 Literature review 884.2 An ILP model for the MSFBC problem 894.3 Heuristic approaches 904.3.1 Frequency-based greedy 914.3.2 Truncated pilot method 914.4 ILP-based large neighborhood search 924.5 Experimental evaluation 944.5.1 Benchmarks 944.5.2 Tuning of LNS 964.5.3 Results 974.6 Future work 104Chapter 5 Consensus String Problems 1075.1 Introduction 1075.1.1 Creating diagnostic probes for bacterial infections 1085.1.2 Primer design 1085.1.3 Discovering potential drug targets 1085.1.4 Motif search 1095.2 Organization of this chapter 1105.3 The closest string problem and the close to most string problem 1105.3.1 ILP models for the CSP and the CTMSP 1115.3.2 Literature review 1125.3.3 Exact approaches for the CSP 1135.3.4 Approximation algorithms for the CSP 1135.3.5 Heuristics and metaheuristics for the CSP 1145.4 The farthest string problem and the far from most string problem 1175.4.1 ILP models for the FSP and the FFMSP 1175.4.2 Literature review 1185.4.3 Heuristics and metaheuristics for the FFMSP 1195.5 An ILP-based heuristic 1415.6 Future work 146Chapter 6 Alignment Problems 1496.1 Introduction 1496.1.1 Organization of this chapter 1506.2 The pairwise alignment problem 1516.2.1 Smith and Waterman’s algorithm 1546.3 The multiple alignment problem 1576.3.1 Heuristics for the multiple alignment problem 1616.3.2 Metaheuristics for the multiple alignment problem 1626.4 Conclusion and future work 173Chapter 7 Conclusions 1757.1 DNA sequencing 1757.1.1 DNA fragment assembly 1767.1.2 DNA sequencing by hybridization 1777.2 Founder sequence reconstruction 1807.2.1 The FSRP problem 1817.2.2 Existing heuristics and metaheuristics 1827.3 Final remarks 184Bibliography 187Index 205

Christian Blum is a senior scientist at the Spanish National Research Council (CSIC) in Bellaterra, Spain. Paola Festa is Associate Professor in Operations Research at the University of Naples Federico II, Italy.

• Preface ixAcknowledgments xiList of Acronyms xiiiChapter 1 Introduction 11.1 Complete methods for combinatorial optimization 31.1.1 Linear programming relaxation 61.1.2 Cutting plane techniques 91.1.3 General-purpose ILP solvers 181.1.4 Dynamic programming 191.2 Approximate methods: metaheuristics 201.2.1 Ant colony optimization 221.2.2 Evolutionary algorithms 241.2.3 Greedy randomized adaptive search procedures 251.2.4 Iterated local search 261.2.5 Simulated annealing 271.2.6 Other metaheuristics 291.2.7 Hybrid approaches 291.3 Outline of the book 32Chapter 2 Minimum Common String Partition Problem 372.1 The MCSP problem 382.1.1 Technical description of the UMCSP problem 382.1.2 Literature review 392.1.3 Organization of this chapter 402.2 An ILP model for the UMCSP problem 402.3 Greedy approach 422.4 Construct, merge, solve and adapt 422.5 Experimental evaluation 452.5.1 Benchmarks 462.5.2 Tuning CMSA 462.5.3 Results 472.6 Future work 54Chapter 3 Longest Common Subsequence Problems 553.1 Introduction 563.1.1 LCS problems 563.1.2 ILP models for LCS and RFLCS problems 593.1.3 Organization of this chapter 613.2 Algorithms for the LCS problem 613.2.1 Beam search 613.2.2 Upper bound 643.2.3 Beam search framework 643.2.4 Beam–ACO 673.2.5 Experimental evaluation 713.3 Algorithms for the RFLCS problem 753.3.1 CMSA 773.3.2 Experimental evaluation 803.4 Future work 85Chapter 4 The Most Strings With Few Bad Columns Problem 874.1 The MSFBC problem 884.1.1 Literature review 884.2 An ILP model for the MSFBC problem 894.3 Heuristic approaches 904.3.1 Frequency-based greedy 914.3.2 Truncated pilot method 914.4 ILP-based large neighborhood search 924.5 Experimental evaluation 944.5.1 Benchmarks 944.5.2 Tuning of LNS 964.5.3 Results 974.6 Future work 104Chapter 5 Consensus String Problems 1075.1 Introduction 1075.1.1 Creating diagnostic probes for bacterial infections 1085.1.2 Primer design 1085.1.3 Discovering potential drug targets 1085.1.4 Motif search 1095.2 Organization of this chapter 1105.3 The closest string problem and the close to most string problem 1105.3.1 ILP models for the CSP and the CTMSP 1115.3.2 Literature review 1125.3.3 Exact approaches for the CSP 1135.3.4 Approximation algorithms for the CSP 1135.3.5 Heuristics and metaheuristics for the CSP 1145.4 The farthest string problem and the far from most string problem 1175.4.1 ILP models for the FSP and the FFMSP 1175.4.2 Literature review 1185.4.3 Heuristics and metaheuristics for the FFMSP 1195.5 An ILP-based heuristic 1415.6 Future work 146Chapter 6 Alignment Problems 1496.1 Introduction 1496.1.1 Organization of this chapter 1506.2 The pairwise alignment problem 1516.2.1 Smith and Waterman’s algorithm 1546.3 The multiple alignment problem 1576.3.1 Heuristics for the multiple alignment problem 1616.3.2 Metaheuristics for the multiple alignment problem 1626.4 Conclusion and future work 173Chapter 7 Conclusions 1757.1 DNA sequencing 1757.1.1 DNA fragment assembly 1767.1.2 DNA sequencing by hybridization 1777.2 Founder sequence reconstruction 1807.2.1 The FSRP problem 1817.2.2 Existing heuristics and metaheuristics 1827.3 Final remarks 184Bibliography 187Index 205

Christian Blum is a senior scientist at the Spanish National Research Council (CSIC) in Bellaterra, Spain. Paola Festa is Associate Professor in Operations Research at the University of Naples Federico II, Italy.

• Preface ixAcknowledgments xiList of Acronyms xiiiChapter 1 Introduction 11.1 Complete methods for combinatorial optimization 31.1.1 Linear programming relaxation 61.1.2 Cutting plane techniques 91.1.3 General-purpose ILP solvers 181.1.4 Dynamic programming 191.2 Approximate methods: metaheuristics 201.2.1 Ant colony optimization 221.2.2 Evolutionary algorithms 241.2.3 Greedy randomized adaptive search procedures 251.2.4 Iterated local search 261.2.5 Simulated annealing 271.2.6 Other metaheuristics 291.2.7 Hybrid approaches 291.3 Outline of the book 32Chapter 2 Minimum Common String Partition Problem 372.1 The MCSP problem 382.1.1 Technical description of the UMCSP problem 382.1.2 Literature review 392.1.3 Organization of this chapter 402.2 An ILP model for the UMCSP problem 402.3 Greedy approach 422.4 Construct, merge, solve and adapt 422.5 Experimental evaluation 452.5.1 Benchmarks 462.5.2 Tuning CMSA 462.5.3 Results 472.6 Future work 54Chapter 3 Longest Common Subsequence Problems 553.1 Introduction 563.1.1 LCS problems 563.1.2 ILP models for LCS and RFLCS problems 593.1.3 Organization of this chapter 613.2 Algorithms for the LCS problem 613.2.1 Beam search 613.2.2 Upper bound 643.2.3 Beam search framework 643.2.4 Beam–ACO 673.2.5 Experimental evaluation 713.3 Algorithms for the RFLCS problem 753.3.1 CMSA 773.3.2 Experimental evaluation 803.4 Future work 85Chapter 4 The Most Strings With Few Bad Columns Problem 874.1 The MSFBC problem 884.1.1 Literature review 884.2 An ILP model for the MSFBC problem 894.3 Heuristic approaches 904.3.1 Frequency-based greedy 914.3.2 Truncated pilot method 914.4 ILP-based large neighborhood search 924.5 Experimental evaluation 944.5.1 Benchmarks 944.5.2 Tuning of LNS 964.5.3 Results 974.6 Future work 104Chapter 5 Consensus String Problems 1075.1 Introduction 1075.1.1 Creating diagnostic probes for bacterial infections 1085.1.2 Primer design 1085.1.3 Discovering potential drug targets 1085.1.4 Motif search 1095.2 Organization of this chapter 1105.3 The closest string problem and the close to most string problem 1105.3.1 ILP models for the CSP and the CTMSP 1115.3.2 Literature review 1125.3.3 Exact approaches for the CSP 1135.3.4 Approximation algorithms for the CSP 1135.3.5 Heuristics and metaheuristics for the CSP 1145.4 The farthest string problem and the far from most string problem 1175.4.1 ILP models for the FSP and the FFMSP 1175.4.2 Literature review 1185.4.3 Heuristics and metaheuristics for the FFMSP 1195.5 An ILP-based heuristic 1415.6 Future work 146Chapter 6 Alignment Problems 1496.1 Introduction 1496.1.1 Organization of this chapter 1506.2 The pairwise alignment problem 1516.2.1 Smith and Waterman’s algorithm 1546.3 The multiple alignment problem 1576.3.1 Heuristics for the multiple alignment problem 1616.3.2 Metaheuristics for the multiple alignment problem 1626.4 Conclusion and future work 173Chapter 7 Conclusions 1757.1 DNA sequencing 1757.1.1 DNA fragment assembly 1767.1.2 DNA sequencing by hybridization 1777.2 Founder sequence reconstruction 1807.2.1 The FSRP problem 1817.2.2 Existing heuristics and metaheuristics 1827.3 Final remarks 184Bibliography 187Index 205