Optimization Techniques for Solving Complex Problems

CHAPTER 16

Metaheuristics in Bioinformatics: DNA Sequencing and Reconstruction

C. COTTA, A. J. FERNÁNDEZ, J. E. GALLARDO, G. LUQUE, and E. ALBA

Universidad de Málaga, Spain

16.1 INTRODUCTION

In recent decades, advances in the fields of molecular biology and genomic technologies have led to a very important growth in the biological information generated by the scientific community. The needs of biologists to utilize, interpret, and analyze that large amount of data have increased the importance of bioinformatics [1]. This area is an interdisciplinary field involving biology, computer science, mathematics, and statistics for achieving faster and better methods in those tasks.

Most bioinformatic tasks are formulated as difficult combinatorial problems. Thus, in most cases it is not feasible to solve large instances using exact techniques such as branch and bound. As a consequence, the use of metaheuristics and other approximate techniques is mandatory. In short, a metaheuristic [2,3] can be defined as a top-level general strategy that guides other heuristics to search for good solutions. Up to now there has been no commonly accepted definition for the term metaheuristic. It is just in the last few years that some researchers in the field have proposed a definition. Some fundamental characteristics:

• The goal is efficient exploration of the search space to find (nearly) optimal solutions. ...