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.

Analytical challenges in the fields of Nanobioscience and Nanobiotecnology: integrated methods for separation and characterization

Nano(bio)science and nano(bio)technology play a growing and tremendous interest both on academic and industrial aspects. They are undergoing rapid developments on many fronts such as genomics, proteomics, system biology, and medical applications. However, the lack of characterization tools for nano(bio)systems is currently considered as a major limiting factor to the final establishment of nano(bio)technologies. Flow Field-Flow Fractionation (FlFFF) is a separation technique that is definitely emerging in the bioanalytical field, and the number of applications on nano(bio)analytes such as high molar-mass proteins and protein complexes, sub-cellular units, viruses, and functionalized nanoparticles is constantly increasing. This can be ascribed to the intrinsic advantages of FlFFF for the separation of nano(bio)analytes. FlFFF is ideally suited to separate particles over a broad size range (1 nm-1 μm) according to their hydrodynamic radius (rh). The fractionation is carried out in an empty channel by a flow stream of a mobile phase of any composition. For these reasons, fractionation is developed without surface interaction of the analyte with packing or gel media, and there is no stationary phase able to induce mechanical or shear stress on nanosized analytes, which are for these reasons kept in their native state. Characterization of nano(bio)analytes is made possible after fractionation by interfacing the FlFFF system with detection techniques for morphological, optical or mass characterization. For instance, FlFFF coupling with multi-angle light scattering (MALS) detection allows for absolute molecular weight and size determination, and mass spectrometry has made FlFFF enter the field of proteomics. Potentialities of FlFFF couplings with multi-detection systems are discussed in the first section of this dissertation. The second and the third sections are dedicated to new methods that have been developed for the analysis and characterization of different samples of interest in the fields of diagnostics, pharmaceutics, and nanomedicine. The second section focuses on biological samples such as protein complexes and protein aggregates. In particular it focuses on FlFFF methods developed to give new insights into: a) chemical composition and morphological features of blood serum lipoprotein classes, b) time-dependent aggregation pattern of the amyloid protein Aβ1-42, and c) aggregation state of antibody therapeutics in their formulation buffers. The third section is dedicated to the analysis and characterization of structured nanoparticles designed for nanomedicine applications. The discussed results indicate that FlFFF with on-line MALS and fluorescence detection (FD) may become the unparallel methodology for the analysis and characterization of new, structured, fluorescent nanomaterials.

Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Cyclic alternating pattern in sleep and its relationship to creativity

Background/Objectives: Sleep has been shown to enhance creativity, but the reason for this enhancement is not entirely known. There are several different physiological states associated with sleep. In addition to rapid (REM) and non-rapid eye movement (NREM) sleep, NREM sleep can be broken down into Stages (1-4) that are characterized by the degree of EEG slow wave activity. In addition, during NREM sleep there are transient but cyclic alternating patterns (CAP) of EEG activity and these CAPs can also be divided into three subtypes (A1-A3) according to speed of the EEG waves. Differences in CAP ratios have been previously linked to cognitive performances. The purpose of this study was to learn the relationship CAP activity during sleep and creativity. Methods: The participants were 8 healthy young adults (4 women), who underwent 3 consecutive nights of polysomnographic recording and took the Abbreviated Torrance Test for Adults (ATTA) on the 2 and 3rd mornings after the recordings. Results: There were positive correlations between Stage 1 of NREM sleep and some measures of creativity such as fluency (R= .797; p=.029) and flexibility ( R=.43; p=.002), between Stage 4 of Non-REM sleep and originality (R= .779; p=.034) and a global measure of figural creativity (R= .758; p=.040). There was also a negative correlation between REM sleep and originality (R= -.827; p= .042) . During NREM sleep the CAP rate, which in young people is primarily the A1 subtype, also correlated with originality (R= .765; p =.038). Conclusions: NREM sleep is associated with low levels of cortical arousal and low cortical arousal may enhance the ability of people to access to the remote associations that are critical for creative innovations. In addition, A1 CAP activity reflects frontal activity and the frontal lobes are important for divergent thinking, also a critical aspect of creativity.

Carbon fluxes and allocation pattern in an apple orchard

Carbon fluxes and allocation pattern, and their relationship with the main environmental and physiological parameters, were studied in an apple orchard for one year (2010). I combined three widely used methods: eddy covariance, soil respiration and biometric measurements, and I applied a measurement protocol allowing a cross-check between C fluxes estimated using different methods. I attributed NPP components to standing biomass increment, detritus cycle and lateral export. The influence of environmental and physiological parameters on NEE, GPP and Reco was analyzed with a multiple regression model approach. I found that both NEP and GPP of the apple orchard were of similar magnitude to those of forests growing in similar climate conditions, while large differences occurred in the allocation pattern and in the fate of produced biomass. Apple production accounted for 49% of annual NPP, organic material (leaves, fine root litter, pruned wood and early fruit drop) contributing to detritus cycle was 46%, and only 5% went to standing biomass increment. The carbon use efficiency (CUE), with an annual average of 0.68 ± 0.10, was higher than the previously suggested constant values of 0.47-0.50. Light and leaf area index had the strongest influence on both NEE and GPP. On a diurnal basis, NEE and GPP reached their peak approximately at noon, while they appeared to be limited by high values of VPD and air temperature in the afternoon. The proposed models can be used to explain and simulate current relations between carbon fluxes and environmental parameters at daily and yearly time scale. On average, the annual NEP balanced the carbon annually exported with the harvested apples. These data support the hypothesis of a minimal or null impact of the apple orchard ecosystem on net C emission to the atmosphere.

Aging of nuclear power plant cables: in search of non-destructive diagnostic quantities

The safety systems of nuclear power plants rely on low-voltage power, instrumentation and control cables. Inside the containment area, cables operate in harsh environments, characterized by relatively high temperature and gamma-irradiation. As these cables are related to fundamental safety systems, they must be able to withstand unexpected accident conditions and, therefore, their condition assessment is of utmost importance as plants age and lifetime extensions are required. Nowadays, the integrity and functionality of these cables are monitored mainly through destructive test which requires specific laboratory. The investigation of electrical aging markers which can provide information about the state of the cable by non-destructive testing methods would improve significantly the present diagnostic techniques. This work has been made within the framework of the ADVANCE (Aging Diagnostic and Prognostics of Low-Voltage I\&C Cables) project, a FP7 European program. This Ph.D. thesis aims at studying the impact of aging on cable electrical parameters, in order to understand the evolution of the electrical properties associated with cable degradation. The identification of suitable aging markers requires the comparison of the electrical property variation with the physical/chemical degradation mechanisms of polymers for different insulating materials and compositions. The feasibility of non-destructive electrical condition monitoring techniques as potential substitutes for destructive methods will be finally discussed studying the correlation between electrical and mechanical properties. In this work, the electrical properties of cable insulators are monitored and characterized mainly by dielectric spectroscopy, polarization/depolarization current analysis and space charge distribution. Among these techniques, dielectric spectroscopy showed the most promising results; by means of dielectric spectroscopy it is possible to identify the frequency range where the properties are more sensitive to aging. In particular, the imaginary part of permittivity at high frequency, which is related to oxidation, has been identified as the most suitable aging marker based on electrical quantities.

Learning Methods and Algorithms for Semantic Text Classification across Multiple Domains

Information is nowadays a key resource: machine learning and data mining techniques have been developed to extract high-level information from great amounts of data. As most data comes in form of unstructured text in natural languages, research on text mining is currently very active and dealing with practical problems. Among these, text categorization deals with the automatic organization of large quantities of documents in priorly defined taxonomies of topic categories, possibly arranged in large hierarchies. In commonly proposed machine learning approaches, classifiers are automatically trained from pre-labeled documents: they can perform very accurate classification, but often require a consistent training set and notable computational effort. Methods for cross-domain text categorization have been proposed, allowing to leverage a set of labeled documents of one domain to classify those of another one. Most methods use advanced statistical techniques, usually involving tuning of parameters. A first contribution presented here is a method based on nearest centroid classification, where profiles of categories are generated from the known domain and then iteratively adapted to the unknown one. Despite being conceptually simple and having easily tuned parameters, this method achieves state-of-the-art accuracy in most benchmark datasets with fast running times. A second, deeper contribution involves the design of a domain-independent model to distinguish the degree and type of relatedness between arbitrary documents and topics, inferred from the different types of semantic relationships between respective representative words, identified by specific search algorithms. The application of this model is tested on both flat and hierarchical text categorization, where it potentially allows the efficient addition of new categories during classification. Results show that classification accuracy still requires improvements, but models generated from one domain are shown to be effectively able to be reused in a different one.

Methods for Biodata Analysis in different Omic Contexts

The world of Computational Biology and Bioinformatics presently integrates many different expertise, including computer science and electronic engineering. A major aim in Data Science is the development and tuning of specific computational approaches to interpret the complexity of Biology. Molecular biologists and medical doctors heavily rely on an interdisciplinary expert capable of understanding the biological background to apply algorithms for finding optimal solutions to their problems. With this problem-solving orientation, I was involved in two basic research fields: Cancer Genomics and Enzyme Proteomics. For this reason, what I developed and implemented can be considered a general effort to help data analysis both in Cancer Genomics and in Enzyme Proteomics, focusing on enzymes which catalyse all the biochemical reactions in cells. Specifically, as to Cancer Genomics I contributed to the characterization of intratumoral immune microenvironment in gastrointestinal stromal tumours (GISTs) correlating immune cell population levels with tumour subtypes. I was involved in the setup of strategies for the evaluation and standardization of different approaches for fusion transcript detection in sarcomas that can be applied in routine diagnostic. This was part of a coordinated effort of the Sarcoma working group of "Alleanza Contro il Cancro". As to Enzyme Proteomics, I generated a derived database collecting all the human proteins and enzymes which are known to be associated to genetic disease. I curated the data search in freely available databases such as PDB, UniProt, Humsavar, Clinvar and I was responsible of searching, updating, and handling the information content, and computing statistics. I also developed a web server, BENZ, which allows researchers to annotate an enzyme sequence with the corresponding Enzyme Commission number, the important feature fully describing the catalysed reaction. More to this, I greatly contributed to the characterization of the enzyme-genetic disease association, for a better classification of the metabolic genetic diseases.

Pattern peristaltico uterino nell'adenomiosi isolata: studio prospettico

Obiettivi dello studio: valutare con l’ecografia transvaginale la peristalsi uterina in fase periovulatoria in donne con adenomiosi isolata, confrontandola con un gruppo di controllo e, secondariamente, valutare il grado di accordo tra gli sperimentatori nella descrizione dei pattern di contrattilità. Disegno dello studio: studio osservazione prospettico condotto presso il Policlinico S. Orsola- Malpighi di Bologna, Italia. Materiali e Metodi: sono state reclutate pazienti afferenti al Centro per valutazione ambulatoriale, suddivise sulla base dei criteri di inclusione ed esclusione nei gruppi A (adenomiosi) e B (controlli) e sono state sottoposte da un unico ecografista esperto a ecografia transvaginale con registrazione di un video della durata di 180 secondi della scansione sagittale dell’utero. La registrazione è stata rivalutata off line da due sperimentatori esperti ecografisti, non a conoscenza della storia clinica delle pazienti e in cieco l’uno rispetto all’altro, che hanno descritto il pattern contrattile. È stata stimata una numerosità campionaria di 18 pazienti per gruppo per ottenere una differenza del 20% nell’obiettivo primario con una significatività del 5% (power 80%). Risultati: di 51 pazienti reclutate nello studio, a seguito di drop out 36 sono state sottoposte alla videoregistrazione ecografica (18 per gruppo). Il pattern peristaltico nel gruppo A è risultato alterato in maniera statisticamente significativa rispetto al gruppo B con un p value= 0,02. Sono stati osservati un pattern retrogrado nel 27,8% vs 72,2%, anterogrado del 11,1% vs 16,7%, opposto 38,9% vs 5,6% e random nel 22,2% vs 5,6%, rispettivamente nel gruppo A e B. Il calcolo dell’accordo interosservatore ha portato a un κ value di 0,92. Conclusioni: l’adenomiosi isolata è associata a disperistalsi uterina, che concorrerebbe nello sviluppo dei sintomi tipici dell’adenomiosi. L’ecografia transvaginale rappresenta uno strumento accessibile e utile nella valutazione della contrattilità uterina in quanto il grado di accordo tra gli sperimentatori è ottimo.

[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.