COMBINATORIAL OPTIMIZATION METHODS FOR PROBLEMS IN GENOMICS

In the last few years, the advances in biology conduct research from pure biological science to other new areas. This was made possible due to the possibility to deal with genomic and proteomic material using math- ematical models. Problems in genomic are among the most di cult in computational biology. They usually address the task of determining combinatorial properties of biological material, by comparing, discovering similarities and patterns in genomic and proteomic sequences. Biological data occur as sequences of elements, that belong to an alphabet A. A sequence of such elements is identi ed as a string. Strings contain genetic material (DNA or RNA), that encode "biological" instructions, for exam- ple to produce the proteins that regulate the life of organisms. The analysis of biological sequences represents an interesting and di cult combinatorial problems. As many of these problems are NP-hard, the study of improved techniques is necessary in order to solve this class of problems exactly, or at least with some guarantee of solution quality. This work is focused on problems related to con gurations of genomic and proteomic sequences, by modeling them as integer linear programming (ILP) problems. Presented models are solved by applying heuristic methods combined with standard algorithms and commercial packages for integer programming in order to improve the e ciency of such techniques for the speci c problems.

I recenti progressi in genomica hanno sollevato una miriade di problemi estremamente stimolanti dal punto di vista computazionale; in particolare, per molti di essi e' stata provata l'appartenenza alla classe dei problemi NP-hard. Sulla base di questi risultati, grande attenzione e' stata posta allo sviluppo di algoritmi che fornissero soluzioni soddisfacenti con uno sforzo computazionale contenuto; in tale contesto, i metodi di ottimizzazione rappresentano un valido approccio in quanto molti problemi richiedono l'individuazione di soluzioni caratterizzati da costo minimo. Questo lavoro di tesi introduce nuovi metodi di ottimizzazione combinatoria per l'analisi e il design di sequenze nucleotidiche. In particolare, la tesi e' focalizzata su metodi effi cienti per la risoluzione del Non-Unique Probe Selection Problem e del Closest String Problem. I risultati sperimentali hanno evidenziato che i nuovi approcci introdotti rappresentano metodi e fficienti e competitivi con lo stato dell'arte e, in molti casi, essi sono in grado di individuare soluzioni migliori rispetto a quelle note in letteratura.