Introduzione

La bioinformatica e' una nuova disciplina che si occupa dello sviluppo e dell'integrazione delle applicazioni della scienza dell'informazione al servizio della ricerca scientifica in campo biotecnologico. Per fare ciò utilizza strumenti informatici per analizzare i dati biologici che descrivono sequenze di geni, composizione e struttura delle proteine, processi biochimici nelle cellule, etc.
Inizialmente in questa tesina verrà spiegato cosa sono i riarrangiamenti genomici facendo riferimento ad alcuni esempi (differenze nell'ordine dei geni tra il cavolo e la rapa) e alla sindrome di Waardenburg.

Nella seconda parte verranno spiegati gli ordinamenti da inversione, cioè la trasformazione di un genoma in un altro attraverso una serie di inversioni inerente al fenomeno di riarrangiamento, evidenziando il problema della distanza inversa,  dell'ordinamento da inversione e dello spostamento del pancake.

Successivamente si vedrà come, attraverso gli algoritmi di approssimazione, si possa trovare una soluzione approssimata per garantire performance migliori.

Nell'ultima parte, infine, verrà spiegato come, l'utilizzo dei breakpoints (punti di rottura) possa condurre ad un algoritmo migliore per l'ordinamento da inversione, spiegando gli algoritmi BreackpointReversalSort, ImprovedBreakpointReversalSort e successivamente l'utilizzo dei grafici in breakpoints.