Metaheuristics for String Problems in Bio-informatics [Hardcover]

So-called string problems are abundant in bioinformatics and computational biology. New optimization problems dealing with DNA or protein sequences are constantly arising and researchers are highly in need of efficient optimization techniques for solving them.

One obstacle for optimization practitioners is the atypical nature of these problems which require an interdisciplinary approach in order to solve them efficiently and accurately.

Preface ix

Acknowledgments xi

List of Acronyms xiii

Chapter 1 Introduction 1

1.1 Complete methods for combinatorial optimization 3

1.1.1 Linear programming relaxation 6

1.1.2 Cutting plane techniques 9

1.1.3 General-purpose ILP solvers 18

1.1.4 Dynamic programming 19

1.2 Approximate methods: metaheuristics 20

1.2.1 Ant colony optimization 22

1.2.2 Evolutionary algorithms 24

1.2.3 Greedy randomized adaptive search procedures 25

1.2.4 Iterated local search 26

1.2.5 Simulated annealing 27

1.2.6 Other metaheuristics 29

1.2.7 Hybrid approaches 29

1.3 Outline of the book 32

Chapter 2 Minimum Common String Partition Problem 37

2.1 The MCSP problem 38

2.1.1 Technical description of the UMCSP problem 38

2.1.2 Literature review 39

2.1.3 Organization of this chapter 40

2.2 An ILP model for the UMCSP problem 40

2.3 Greedy approach 42

2.4 Construct, merge, solve and adapt 42

2.5 Experimental evaluation 45

2.5.1 Benchmarks 46

2.5.2 Tuning CMSAlã,