Stochastic modeling of bacterial protein domains distribution to predict horizontal gene transfer

In questo elaborato, abbiamo tentato di modellizzare i processi che regolano la presenza dei domini proteici. I domini proteici studiati in questa tesi sono stati ottenuti dai genomi batterici disponibili nei data base pubblici (principalmente dal National Centre for Biotechnology Information: NCBI) tramite una procedura di simulazione computazionale. Ci siamo concentrati su organismi batterici in quanto in essi la presenza di geni trasmessi orizzontalmente, ossia che parte del materiale genetico non provenga dai genitori, e assodato che sia presente in una maggiore percentuale rispetto agli organismi più evoluti. Il modello usato si basa sui processi stocastici di nascita e morte, con l'aggiunta di un parametro di migrazione, usato anche nella descrizione dell'abbondanza relativa delle specie in ambito delle biodiversità ecologiche. Le relazioni tra i parametri, calcolati come migliori stime di una distribuzione binomiale negativa rinormalizzata e adattata agli istogrammi sperimentali, ci induce ad ipotizzare che le famiglie batteriche caratterizzate da un basso valore numerico del parametro di immigrazione abbiano contrastato questo deficit con un elevato valore del tasso di nascita. Al contrario, ipotizziamo che le famiglie con un tasso di nascita relativamente basso si siano adattate, e in conseguenza, mostrano un elevato valore del parametro di migrazione. Inoltre riteniamo che il parametro di migrazione sia direttamente proporzionale alla quantità di trasferimento genico orizzontale effettuato dalla famiglia batterica.

Solving the logically constrained multiple choice multiple knapsack problem: A real case

In questa tesi viene analizzato un problema di ottimizzazione proposto da alcuni esercizi commerciali che hanno la necessita` di selezionare e disporre i propri ar- ticoli in negozio. Il problema nasce dall’esigenza di massimizzare il profitto com- plessivo atteso dei prodotti in esposizione, trovando per ognuno una locazione sugli scaffali. I prodotti sono suddivisi in dipartimenti, dai quali solo un ele- mento deve essere selezionato ed esposto. In oltre si prevede la possibilita` di esprimere vincoli sulla locazione e compatibilita` dei prodotti. Il problema risul- tante `e una generalizzazione dei gia` noti Multiple-Choice Knapsack Problem e Multiple Knapsack Problem. Dopo una ricerca esaustiva in letteratura si `e ev- into che questo problema non `e ancora stato studiato. Si `e quindi provveduto a formalizzare il problema mediante un modello di programmazione lineare intera. Si propone un algoritmo esatto per la risoluzione del problema basato su column generation e branch and price. Sono stati formulati quattro modelli differenti per la risoluzione del pricing problem su cui si basa il column generation, per individuare quale sia il piu` efficiente. Tre dei quattro modelli proposti hanno performance comparabili, mentre l’ultimo si `e rivelato piu` inefficiente. Dai risul- tati ottenuti si evince che il metodo risolutivo proposto `e adatto a istanze di dimensione medio-bassa.