In this lecture we will describe the different methods related to metaheuristics that are commonly used to solve combinatorial optimization problems. Most of the problems of bioinformatics are optimization problems that are known to be very difficult to solve. A first part introduces complexity measures and NP-completeness. The second part deals with the methods that have been designed to solve NP-complete problems such as Hill-Climbing, Tabu Search, Genetic algorithms, hybrid methods. We will see that those methods are often based on common knowledge or natural processes.
In this lecture we show how the metaheuristics are used to solve two well-known problems of bioinformatics : multiple alignment and phylogenetic reconstruction. we focus on the adaptation of those methods to tackle the resolution of the related problems.
The fasta file format is widely used by researchers to store sequences before they are processed by multiple alignment or phylogenetic reconstruction softwares. Although simple, the fasta file format can not store semantic or context information about a sequence such as accession number, bibliography or 2D structural information. We show how the XML format can help increase the meaning of files and can be used to simply retrieve the desired information. Some of the XML formats for bioinformatics are discussed as well as some software packages and XSL.
Examples of XML file :