Metaheuristics for String Problems in Bio-informatics

5Consensus String Problems

This chapter provides an overview of some string selection and comparison problems, with special emphasis on consensus string problems. The intrinsic properties of the problems are studied and the most popular solution techniques given, including some recently-proposed heuristic and metaheuristic approaches. Finally, a simple and efficient ILP-based heuristic that can be used for any of the problems considered is presented. Future directions are discussed in the last section.

5.1. Introduction

Among string selection and comparison problems there is a class of problems known as consensus string problems, where a finite set of strings is given and one is interested in finding their consensus, i.e. a new string that agrees as much as possible with all the given strings. In other words, the objective is to determine a consensus string that once one or more criteria have been defined represents all the given strings. The idea of consensus can be related to several different objectives and prospectives. Some of them are considered in this chapter and are listed in the following:

1. 1) the consensus is a new string whose total distance from all given strings is minimal (closest string problem);
2. 2) the consensus is a new string close to most of the given strings (close to most string problem);
3. 3) the consensus is a new string whose total distance from all given strings is maximal (farthest string problem);
4. 4) the consensus is a new string far from most of the ...