A branch-and-price approach for Pure Parsimony haplotyping

Questa tesi rappresenta il risultato dello studio dettagliato di metodi di decomposizione per problemi di grandi dimensioni e la loro applicazione ad un problema particolare di biologia computazionale. I progressi nelle prestazioni dei computer e nelle tecniche di programmazione degli ultimi decenni hanno ampliato l’insieme di problemi che possono essere facilmente risolti come programmi lineari interi. Tuttavia, molte applicazioni richiedono ancora formulazioni che interessano una quantità di informazioni non trattabili per descrivere la geometria dello spazio delle soluzioni. In questi casi, vengono usati metodi di decomposizione per ridurre la dimensione del problema. In questa tesi proponiamo l’applicazione di alcuni di questi metodi, come la riformulazione di Dantzig-Wolfe, la generazione di colonne e il rilassamento Lagrangiano, ad un problema legato allo studio del genoma umano. Il DNA umano è costituito da due doppie catene formate da sequenze di nucleotidi. Tra questi nucleotidi, siamo interessati a quelli che individuano Single Nucleotide Polymorphisms (SNPs), in quanto descrivono le differenze tra individui della stessa specie. Definiamo un aplotipo come una sequenza di nucleotidi che descrivono una parte degli SNPs di un particolare cromosoma, e un genotipo come una sequenza che aggrega le informazioni sugli SNPs per una doppia catena di DNA. Il problema oggetto di studio ricade nella più ampia famiglia di problemi riguardanti l’Haplotype Inference, che consiste nel ricavare la struttura degli aplotipi avendo solo l’informazione riguardante i genotipi di una popolazione. In particolare, consideriamo il criterio di Pure Parsimony, per il quale cerchiamo il numero minimo di aplotipi necessari a formare tutti i genotipi dati. Questo problema è APX-hard. I diversi approcci usati per la soluzione di questo problema possono essere divisi in due principali categorie: la prima utilizza formulazioni con un numero polinomiale di variabili e vincoli, che sono risolte applicando un algoritmo branch-and-cut; la seconda classe presenta formulazioni con numero esponenziale di variabili e vincoli, risolte con un algoritmo di tipo branch-and-cut-and-price. Questa tesi si prefigge lo scopo di studiare come risolvere con un approccio di tipo branch-and-price una nuova formulazione che presenta un numero esponenziale di variabili e polinomiale di vincoli, ottenendo un algoritmo competitivo rispetto a quelli proposti in letteratura. Inizialmente, proponiamo un excursus nello stato dell’arte per il problema di Haplotype Inference, con particolare attenzione agli approcci di programmazione lineare intera per il problema di Haplotype Inference by Pure Parsimony (HIPP) problem. Successivamente consideriamo una nuova formulazione per HIPP che comprende un insieme di vincoli quadratici. Applicando la riformulazione di Dantzig-Wolfe, otteniamo una nuova formulazione lineare intera, con un numero esponenziale di variabili e polinomiale di vincoli. Questo modello viene usato per implementare un algoritmo di tipo branch-and-price. A causa del grande numero di variabili coinvolte, abbiamo bisogno di un algoritmo di generazione di colonne per risolvere il rilassamento lineare ad un qualsiasi nodo dell’albero di branching. Una soluzione iniziale ammissibile si trova facilmente utilizzando delle euristiche, e viene usata per costruire il Restricted Master Problem (RMP). Il pricing problem risultante è quadratico. Proponiamo diversi modi per risolvere il pricing problem. Tra i metodi esatti, consideriamo il modello lineare ottenuto linearizzando la funzione obiettivo quadratica e un algoritmo Smart Enumeration, che partiziona l’insieme di tutte le possibili soluzioni e risolve il pricing problem ristretto ad ogni singolo sottoinsieme. Per quanto riguarda le euristiche, proponiamo una local-search e una Early-terminated Smart Enumeration, in cui fermiamo la Smart Enumeration non appena troviamo una variabile da aggiungere al RMP. L’andamento oscillatorio delle variabili duali coinvolte nella definizione del pricing problem viene limitato stabilizzandole: consideriamo come coefficienti per il pricing problem una combinazione convessa tra i veri valori delle variabili duali e uno stability center scelto. Abbiamo esteso la dimostrazione di convergenza di questa procedura al caso in cui le variabili duali stabilizzate risultano essere ammissibili per il problema duale. Per risolvere il problema all’interezza, usiamo la soluzione del rilassamento lineare come punto di partenza per un algoritmo branch-and-price. La regola di branching proposta, e dimostrata corretta, si ispira alla famosa regola di Ryan-Foster per problemi di tipo set-partitioning. Ulteriori osservazioni sulla similitudine tra I vincoli della formulazione e un set-covering multiplo suggerisce di rilassare la formulazione. Tuttavia, l’algoritmo branch-and-price proposto finora potrebbe non restituire una soluzione ammissibile per HIPP, quindi bisogna ampliare la regola di branching proposta per recuperare la soluzione ottima. Abbiamo implementato l’algoritmo branch-and-price proposto in C++, con l’aiuto delle librerie SCIP e il solutore Cplex, e l’abbiamo testato su diverse classi di istanze usate in letteratura, sia simulate che derivanti da dati reali, e istanze create ad hoc. L’algoritmo proposto per la nostra formulazione risulta essere competitivo con i metodi di soluzione di formulazioni polinomiali dello stato dell’arte. Infatti, notiamo che la distanza tra il rilassamento lineare e l’inviluppo convesso è minore per la nostra formulazione rispetto alle altre formulazioni. I risultati computazionali mostrano l’efficienza del nostro algoritmo, in particolare sull’insieme di istanze che presentano un numero maggiore di genotipi. Abbiamo quindi mostrato come una procedura di tipo branch-and-price fornisce un buon metodo per risolvere problemi la cui formulazione presenta un numero esponenziale di variabili e un numero polinomiale di vincoli. Futuri sviluppi possono riguardare miglioramentii nei dettagli implementativi, ad esempio considerando diversi ordinamenti per i genotipi o combinando metodi esatti e altre euristiche per la risoluzione del pricing problem. Inoltre, si potrebbe generalizzare il metodo proposto per la risoluzione di problemi di tipo set-partitioning.