Metaheuristics for Search Problems in Genomics - New Algorithms and Applications

In this thesis we made the first steps towards the systematic application of a methodology for automatically building formal models of complex biological systems. Such a methodology could be useful also to design artificial systems possessing desirable properties such as robustness and evolvability. The approach we follow in this thesis is to manipulate formal models by means of adaptive search methods called metaheuristics. In the first part of the thesis we develop state-of-the-art hybrid metaheuristic algorithms to tackle two important problems in genomics, namely, the Haplotype Inference by parsimony and the Founder Sequence Reconstruction Problem. We compare our algorithms with other effective techniques in the literature, we show strength and limitations of our approaches to various problem formulations and, finally, we propose further enhancements that could possibly improve the performance of our algorithms and widen their applicability. In the second part, we concentrate on Boolean network (BN) models of gene regulatory networks (GRNs). We detail our automatic design methodology and apply it to four use cases which correspond to different design criteria and address some limitations of GRN modeling by BNs. Finally, we tackle the Density Classification Problem with the aim of showing the learning capabilities of BNs. Experimental evaluation of this methodology shows its efficacy in producing network that meet our design criteria. Our results, coherently to what has been found in other works, also suggest that networks manipulated by a search process exhibit a mixture of characteristics typical of different dynamical regimes.

Analisi spaziale della longevità in Emilia-Romagna

Negli ultimi anni la longevità è divenuto un argomento di notevole interesse in diversi settori scientifici. Le ricerche volte ad indagare i meccanismi che regolano i fattori della longevità si sono moltiplicate nell’ultimo periodo interessando, in maniera diversa, alcune regioni del territorio italiano. Lo studio presentato nella tesi ha l’obiettivo di identificare eventuali aggregazioni territoriali caratterizzate da una significativa propensione alla longevità nella regione Emilia-Romagna mediante l’impiego di metodologie di clustering spaziale, alcune delle quali di recente implementazione. La popolazione in esame è costituita dagli individui residenti in Emilia- Romagna nel quinquennio 2000-2004 suddivisa in classi di età, sesso e comune. L’analisi è di tipo puramente spaziale, in cui l’unità geografica elementare è identificata dal comune, ed è stata condotta separatamente per i due sessi. L’identificazione delle aree regionali ad elevata longevità è avvenuta utilizzando quattro metodologie di clustering spaziale, basate sulla teoria della massima verosimiglianza, che si differenziano tra loro per la modalità di ricerca dei potenziali clusters. La differenza consiste nella capacità di identificare aggregazioni territoriali di forma regolare (spatial scan statistic, Kulldorff e Nagarwalla,1995; Kulldorff,1997, 1999) o dall’andamento geometrico “libero” (flexible scan statistic, Tango e Takahashi,2005; algoritmo genetico, Duczmal et al.,2007; greedy growth search, Yiannakoulias et al.,2007). Le caratteristiche di ciascuna metodologia consentono, in tal modo, di “catturare” le possibili conformazioni geografiche delle aggregazioni presenti sul territorio e la teoria statistica di base, comune ad esse, consente di effettuare agevolmente un confronto tra i risultati ottenuti. La persistenza di un’area caratterizzata da un’elevata propensione alla longevità consente, infatti, di ritenere il cluster identificato di notevole interesse per approfondimenti successivi. Il criterio utilizzato per la valutazione della persistenza di un cluster è stato derivato dalla teoria dei grafi, con particolare riferimento ai multigrafi. L’idea è confrontare, a parità di parametri di ricerca, i grafi associati alle aggregazioni spaziali identificate con le diverse metodologie attraverso una valutazione delle occorrenze dei collegamenti esistenti tra le coppie di vertici. Alcune valutazioni di carattere demografico ed un esame della letteratura esistente sugli studi di longevità, hanno indotto alla definizione di una classe (aperta) di età per rappresentare il fenomeno nella nostra ricerca: sono stati considerati gli individui con età superiore o uguale a 95 anni (indicata con 95+). La misura di sintesi utilizzata per descrivere il fenomeno è un indicatore specifico di longevità, mutuato dalla demografia, indicato con Centenarian Rate (CR) (Robine e Caselli, 2005). Esso è definito dal rapporto tra la popolazione 95+ e la popolazione residente, nello stesso comune, al censimento del 1961. L’idea alla base del CR è confrontare gli individui longevi di un istante temporale con quelli presenti, nella stessa area, circa 40 anni prima dell’osservazione, ipotizzando che l’effetto migratorio di una popolazione possa ritenersi trascurabile oltre i 60 anni di età. La propensione alla longevità coinvolge in maniera diversa le aree del territorio dell’Emilia-Romagna. Le province della regione caratterizzate da una maggiore longevità sono Bologna, Ravenna e parte di Forlì-Cesena mentre la provincia di Ferrara si distingue per un livello ridotto del fenomeno. La distinzione per sesso non appare netta: gli uomini con età 95+, numericamente inferiori alle donne, risiedono principalmente nei comuni delle province di Bologna e Ravenna, con qualche estensione nel territorio forlivese, analogamente a quanto accade per la popolazione femminile che mostra, tuttavia, una maggiore prevalenza nei territori di Bologna e Forlì-Cesena, includendo alcune aree del riminese. Le province occidentali della regione, invece, non risultano interessate significativamente da questo fenomeno. Le metodologie di cluster detection utilizzate nello studio hanno prodotto risultati pressoché simili seppur con criteri di ricerca differenti. La spatial scan statistic si conferma una metodologia efficace e veloce ma il vincolo geometrico regolare imposto al cluster condiziona il suo utilizzo, rivelando una scarsa adattabilità nell’identificazione di aggregazioni irregolari. La metodologia FSC ha evidenziato buone capacità di ricerca e velocità di esecuzione, completata da una descrizione chiara e dettagliata dei risultati e dalla possibilità di poter visualizzare graficamente i clusters finali, anche se con un livello minimo di dettaglio. Il limite principale della metodologia è la dimensione ridotta del cluster finale: l’eccessivo impegno computazionale richiesto dalla procedura induce a fissare il limite massimo al di sotto delle 30 aree, rendendola così utilizzabile solo nelle indagini in cui si ipotizza un’estensione limitata del fenomeno sul territorio. L’algoritmo genetico GA si rivela efficace nell’identificazione di clusters di qualsiasi forma ed estensione, seppur con una velocità di esecuzione inferiore rispetto alle procedure finora descritte. Senza un’adeguata selezione dei parametri di ricerca,la procedura può individuare clusters molto irregolari ed estesi, consigliando l’uso di penalizzazione non nulla in fase di ricerca. La scelta dei parametri di ricerca non è comunque agevole ed immediata e, spesso, è lasciata all’esperienza del ricercatore. Questo modo di procedere, in aggiunta alla mancanza di informazioni a priori sul fenomeno, aumenta il grado di soggettività introdotto nella selezione dei parametri influenzando i risultati finali. Infine, la metodologia GGS richiede un carico computazionale nettamente superiore rispetto a quello necessario per le altre metodologie utilizzate e l’introduzione di due parametri di controllo favorisce una maggiore arbitrarietà nella selezione dei valori di ricerca adeguati; inoltre, la recente implementazione della procedura e la mancanza di studi su dati reali inducono ad effettuare un numero maggiore di prove durante la fase di ricerca dei clusters.

Valutazione dell'efficacia delle procedure di Pushover convenzionali, modali ed adattive applicate a telai piani in c.a. regolari ed irregolari in elevazione.

The research performed during the PhD and presented in this thesis, allowed to make judgments on pushover analysis method about its application in evaluating the correct structural seismic response. In this sense, the extensive critical review of existing pushover procedures (illustrated in chapter 1) outlined their major issues related to assumptions and to hypothesis made in the application of the method. Therefore, with the purpose of evaluate the effectiveness of pushover procedures, a wide numerical investigation have been performed. In particular the attention has been focused on the structural irregularity on elevation, on the choice of the load vector and on its updating criteria. In the study eight pushover procedures have been considered, of which four are conventional type, one is multi-modal, and three are adaptive. The evaluation of their effectiveness in the identification of the correct dynamic structural response, has been done by performing several dynamic and static non-linear analysis on eight RC frames, characterized by different proprieties in terms of regularity in elevation. The comparisons of static and dynamic results have then permitted to evaluate the examined pushover procedures and to identify the expected margin of error by using each of them. Both on base shear-top displacement curves and on considered storey parameters, the best agreement with the dynamic response has been noticed on Multi-Modal Pushover procedure. Therefore the attention has been focused on Displacement-based Adative Pushover, coming to define for it an improvement strategy, and on modal combination rules, advancing an innovative method based on a quadratic combination of the modal shapes (QMC). This latter has been implemented in a conventional pushover procedure, whose results have been compared with those obtained by other multi-modal procedures. The development of research on pushover analysis is very important because the objective is to come to the definition of a simple, effective and reliable analysis method, indispensable tool in the seismic evaluation of new or existing structures.

Electron identification and reconstruction with the OPERA ECC bricks and search for muon neutrino to electron neutrino oscillations

The procedure for event location in OPERA ECC has been optimazed for penetrating particles while is less efficient for electrons. For this reason new procedure has been defined in order to recover event with an electromagnetic shower in its final state not located with the standard one. The new procedure include the standard procedure during which several electromagnetic shower hint has been defined by means of the available data. In case the event is not located, the presence of an electromagnetic shower hint trigger a dedicated procedure. The old and new location procedure has been then simulated in order to obtain the standard location efficiency and the possible gain due to the new one for the events with electromagnetic shower. Finally a Data-MC comparison has been performed for the 2008 and 2009 runs for what concern the NC in order to validate the Monte Carlo. Then the expected electron neutrino interactions for the 2008 and 2009 runs has been evaluated and compared with the available data.

Robust Adaptive Control with Applications to Multi-Agent Systems and Mobile Robotics

This thesis deals with robust adaptive control and its applications, and it is divided into three main parts. The first part is about the design of robust estimation algorithms based on recursive least squares. First, we present an estimator for the frequencies of biased multi-harmonic signals, and then an algorithm for distributed estimation of an unknown parameter over a network of adaptive agents. In the second part of this thesis, we consider a cooperative control problem over uncertain networks of linear systems and Kuramoto systems, in which the agents have to track the reference generated by a leader exosystem. Since the reference signal is not available to each network node, novel distributed observers are designed so as to reconstruct the reference signal locally for each agent, and therefore decentralizing the problem. In the third and final part of this thesis, we consider robust estimation tasks for mobile robotics applications. In particular, we first consider the problem of slip estimation for agricultural tracked vehicles. Then, we consider a search and rescue application in which we need to drive an unmanned aerial vehicle as close as possible to the unknown (and to be estimated) position of a victim, who is buried under the snow after an avalanche event. In this thesis, robustness is intended as an input-to-state stability property of the proposed identifiers (sometimes referred to as adaptive laws), with respect to additive disturbances, and relative to a steady-state trajectory that is associated with a correct estimation of the unknown parameter to be found.

[In search of] Digital biomarkers for objective pain assessment

Pain is a highly complex phenomenon involving intricate neural systems, whose interactions with other physiological mechanisms are not fully understood. Standard pain assessment methods, relying on verbal communication, often fail to provide reliable and accurate information, which poses a critical challenge in the clinical context. In the era of ubiquitous and inexpensive physiological monitoring, coupled with the advancement of artificial intelligence, these new tools appear as the natural candidates to be tested to address such a challenge. This thesis aims to conduct experimental research to develop digital biomarkers for pain assessment. After providing an overview of the state-of-the-art regarding pain neurophysiology and assessment tools, methods for appropriately conditioning physiological signals and controlling confounding factors are presented. The thesis focuses on three different pain conditions: cancer pain, chronic low back pain, and pain experienced by patients undergoing neurorehabilitation. The approach presented in this thesis has shown promise, but further studies are needed to confirm and strengthen these results. Prior to developing any models, a preliminary signal quality check is essential, along with the inclusion of personal and health information in the models to limit their confounding effects. A multimodal approach is preferred for better performance, although unimodal analysis has revealed interesting aspects of the pain experience. This approach can enrich the routine clinical pain assessment procedure by enabling pain to be monitored when and where it is actually experienced, and without the involvement of explicit communication,. This would improve the characterization of the pain experience, aid in antalgic therapy personalization, and bring timely relief, with the ultimate goal of improving the quality of life of patients suffering from pain.