Metaheuristics for String Problems in Bio-informatics

6Alignment Problems

This chapter provides an overview of pairwise and multiple alignment problems. Solution techniques are discussed, with special emphasis on combinatorial optimization (CO), with the goal of providing conceptual insights and references to literature written by a broad community of researchers and practitioners.

6.1. Introduction

Real-world systems and phenomena are often conveniently represented by strings and sequences of symbols, as is the case of spins in magnetic unidimensional systems, or sequences of bits in the recording and transmission of digital data. Analysis of a sequence of symbols aims to extrapolate from it the information that it carries, i.e. its properties and characteristics. In the field of molecular biology, DNA and RNA strings have an immediate and intrinsic interpretation as sequences of symbols and, for example, one may be interested in determining the activity of specific subsequences. Since researchers in molecular biology claim that similar primary biological structures correspond to similar activities, techniques that compare sequences are used to obtain information about an unknown sequence from the knowledge of two or more sequences that have already been. Comparing genomic sequences drawn from individuals from different species consists of determining their similarity or difference. Such comparisons are needed to identify not only functionally relevant DNA regions, but also spot fatal mutations and evolutionary relationships. ...