Combinatorial optimization methods for problems in genomics

Abstract

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.