Local optima networks of hard combinatorial landscapes

Combinatorial optimization involves finding an optimal solution in a finite set of options; many everyday life problems are of this kind. However, the number of options grows exponentially with the size of the problem, such that an exhaustive search for the best solution is practically infeasible beyond a certain problem size. When efficient algorithms are not available, a practical approach to obtain an approximate solution to the problem at hand, is to start with an educated guess and gradually refine it until we have a good-enough solution. Roughly speaking, this is how local search heuristics work. These stochastic algorithms navigate the problem search space by iteratively turning the current solution into new candidate solutions, guiding the search towards better solutions. The search performance, therefore, depends on structural aspects of the search space, which in turn depend on the move operator being used to modify solutions. A common way to characterize the search space of a problem is through the study of its fitness landscape, a mathematical object comprising the space of all possible solutions, their value with respect to the optimization objective, and a relationship of neighborhood defined by the move operator. The landscape metaphor is used to explain the search dynamics as a sort of potential function. The concept is indeed similar to that of potential energy surfaces in physical chemistry. Borrowing ideas from that field, we propose to extend to combinatorial landscapes the notion of the inherent network formed by energy minima in energy landscapes. In our case, energy minima are the local optima of the combinatorial problem, and we explore several definitions for the network edges. At first, we perform an exhaustive sampling of local optima basins of attraction, and define weighted transitions between basins by accounting for all the possible ways of crossing the basins frontier via one random move. Then, we reduce the computational burden by only counting the chances of escaping a given basin via random kick moves that start at the local optimum. Finally, we approximate network edges from the search trajectory of simple search heuristics, mining the frequency and inter-arrival time with which the heuristic visits local optima. Through these methodologies, we build a weighted directed graph that provides a synthetic view of the whole landscape, and that we can characterize using the tools of complex networks science. We argue that the network characterization can advance our understanding of the structural and dynamical properties of hard combinatorial landscapes. We apply our approach to prototypical problems such as the Quadratic Assignment Problem, the NK model of rugged landscapes, and the Permutation Flow-shop Scheduling Problem. We show that some network metrics can differentiate problem classes, correlate with problem non-linearity, and predict problem hardness as measured from the performances of trajectory-based local search heuristics.

Implicit methods for qualitative modeling of gene regulatory networks.

Advancements in high-throughput technologies to measure increasingly complex biological phenomena at the genomic level are rapidly changing the face of biological research from the single-gene single-protein experimental approach to studying the behavior of a gene in the context of the entire genome (and proteome). This shift in research methodologies has resulted in a new field of network biology that deals with modeling cellular behavior in terms of network structures such as signaling pathways and gene regulatory networks. In these networks, different biological entities such as genes, proteins, and metabolites interact with each other, giving rise to a dynamical system. Even though there exists a mature field of dynamical systems theory to model such network structures, some technical challenges are unique to biology such as the inability to measure precise kinetic information on gene-gene or gene-protein interactions and the need to model increasingly large networks comprising thousands of nodes. These challenges have renewed interest in developing new computational techniques for modeling complex biological systems. This chapter presents a modeling framework based on Boolean algebra and finite-state machines that are reminiscent of the approach used for digital circuit synthesis and simulation in the field of very-large-scale integration (VLSI). The proposed formalism enables a common mathematical framework to develop computational techniques for modeling different aspects of the regulatory networks such as steady-state behavior, stochasticity, and gene perturbation experiments.

Multimodal MRI analysis of structural and functional networks in the human brain : application to two clinical studies : driving abilities under THC intoxication and early white matter changes in FXTAS

Les approches multimodales dans l'imagerie cérébrale non invasive sont de plus en plus considérées comme un outil indispensable pour la compréhension des différents aspects de la structure et de la fonction cérébrale. Grâce aux progrès des techniques d'acquisition des images de Resonance Magnetique et aux nouveaux outils pour le traitement des données, il est désormais possible de mesurer plusieurs paramètres sensibles aux différentes caractéristiques des tissues cérébraux. Ces progrès permettent, par exemple, d'étudier les substrats anatomiques qui sont à la base des processus cognitifs ou de discerner au niveau purement structurel les phénomènes dégénératifs et développementaux. Cette thèse met en évidence l'importance de l'utilisation d'une approche multimodale pour étudier les différents aspects de la dynamique cérébrale grâce à l'application de cette approche à deux études cliniques: l'évaluation structurelle et fonctionnelle des effets aigus du cannabis fumé chez des consommateurs réguliers et occasionnels, et l'évaluation de l'intégrité de la substance grise et blanche chez des jeunes porteurs de la prémutations du gène FMR1 à risque de développer le FXTAS (Fragile-X Tremor Ataxia Syndrome). Nous avons montré que chez les fumeurs occasionnels de cannabis, même à faible concentration du principal composant psychoactif (THC) dans le sang, la performance lors d'une tâche visuo-motrice est fortement diminuée, et qu'il y a des changements dans l'activité des trois réseaux cérébraux impliqués dans les processus cognitifs: le réseau de saillance, le réseau du contrôle exécutif, et le réseau actif par défaut (Default Mode). Les sujets ne sont pas en mesure de saisir les saillances dans l'environnement et de focaliser leur attention sur la tâche. L'augmentation de la réponse hémodynamique dans le cortex cingulaire antérieur suggère une augmentation de l'activité introspective. Une investigation des ef¬fets au niveau cérébral d'une exposition prolongée au cannabis, montre des changements persistants de la substance grise dans les régions associées à la mémoire et au traitement des émotions. Le niveau d'atrophie dans ces structures corrèle avec la consommation de cannabis au cours des trois mois précédant l'étude. Dans la deuxième étude, nous démontrons des altérations structurelles des décennies avant l'apparition du syndrome FXTAS chez des sujets jeunes, asymptomatiques, et porteurs de la prémutation du gène FMR1. Les modifications trouvées peuvent être liées à deux mécanismes différents. Les altérations dans le réseau moteur du cervelet et dans la fimbria de l'hippocampe, suggèrent un effet développemental de la prémutation. Elles incluent aussi une atrophie de la substance grise du lobule VI du cervelet et l'altération des propriétés tissulaires de la substance blanche des projections afférentes correspondantes aux pédoncules cérébelleux moyens. Les lésions diffuses de la substance blanche cérébrale peu¬vent être un marquer précoce du développement de la maladie, car elles sont liées à un phénomène dégénératif qui précède l'apparition des symptômes du FXTAS. - Multimodal brain imaging is becoming a leading tool for understanding different aspects of brain structure and function. Thanks to the advances in Magnetic Resonance imaging (MRI) acquisition schemes and data processing techniques, it is now possible to measure different parameters sensitive to different tissue characteristics. This allows for example to investigate anatomical substrates underlying cognitive processing, or to disentangle, at a pure structural level degeneration and developmental processes. This thesis highlights the importance of using a multimodal approach for investigating different aspects of brain dynamics by applying this approach to two clinical studies: functional and structural assessment of the acute effects of cannabis smoking in regular and occasional users, and grey and white matter assessment in young FMR1 premutation carriers at risk of developing FXTAS. We demonstrate that in occasional smokers cannabis smoking, even at low concentration of the main psychoactive component (THC) in the blood, strongly decrease subjects' performance on a visuo-motor tracking task, and globally alters the activity of the three brain networks involved in cognitive processing: the Salience, the Control Executive, and the Default Mode networks. Subjects are unable to capture saliences in the environment and to orient attention to the task; the increase in Hemodynamic Response in the Anterior Cingulate Cortex suggests an increase in self-oriented mental activity. A further investigation on long term exposure to cannabis, shows a persistent grey matter modification in brain regions associated with memory and affective processing. The degree of atrophy in these structures also correlates with the estimation of drug use in the three months prior the participation to the study. In the second study we demonstrate structural changes in young asymptomatic premutation carriers decades before the onset of FXTAS that might be related to two different mechanisms. Alteration of the cerebellar motor network and of the hippocampal fimbria/ fornix, may reflect a potential neurodevelopmental effect of the premutation. These include grey matter atrophy in lobule VI and modification of white matter tissue property in the corresponding afferent projections through the Middle Cerebellar Peduncles. Diffuse hemispheric white matter lesions that seem to appear closer to the onset of FXTAS and be related to a neurodegenerative phenomenon may mark the imminent onset of FXTAS.

Is blood still thicker than water? A life-course perspective on the transformation of family and friends' roles in personal networks

This thesis addresses the issue of the moving boundaries between family and friends' roles in personal networks, adopting a life-course perspective and using Switzerland as a case study. In a period of major changes in personal life happening in contemporary Western societies, understanding the organization of personal networks intertwined with the unfolding of individual life courses is of prime importance in facing new challenges with regard to social integration. The data stem from a representative national survey carried out in 2011 named Family tiMes, including 803 individuals born either in 1950-1955 or in 1970-1975. An innovative research design was adopted, combing cross-sectional ego-centered network data and retrospective longitudinal life-course data. The results show continuing boundaries between family and friends' roles and that family keeps a prominent role in personal networks despite the notable importance of friendship ties. One relationship stands out above all, that with the partner, followed quite a few steps behind by those with children. Regarding life courses, de-standardization tendencies were found in family formation and also a persistent gendering of occupational trajectories. Two kinds of life trajectories are particularly intertwined with personal networks, co-residence and partnership trajectories, both related to the unfolding of family life. In particular, transition to parenthood functions as a turning point in individuals' lives, deeply transforming their sociability. Finally, a twofold pluralization process was identified, affecting simultaneously the organization of personal networks and the unfolding of individual life courses. This thesis contributes to the literature on the sociology of family and personal life, and to fruitful interlinkage between the network approach and the life-course perspective.

Structural Brain Connectivity in School-Age Preterm Infants Provides Evidence for Impaired Networks Relevant for Higher Order Cognitive Skills and Social Cognition.

Extreme prematurity and pregnancy conditions leading to intrauterine growth restriction (IUGR) affect thousands of newborns every year and increase their risk for poor higher order cognitive and social skills at school age. However, little is known about the brain structural basis of these disabilities. To compare the structural integrity of neural circuits between prematurely born controls and children born extreme preterm (EP) or with IUGR at school age, long-ranging and short-ranging connections were noninvasively mapped across cortical hemispheres by connection matrices derived from diffusion tensor tractography. Brain connectivity was modeled along fiber bundles connecting 83 brain regions by a weighted characterization of structural connectivity (SC). EP and IUGR subjects, when compared with controls, had decreased fractional anisotropy-weighted SC (FAw-SC) of cortico-basal ganglia-thalamo-cortical loop connections while cortico-cortical association connections showed both decreased and increased FAw-SC. FAw-SC strength of these connections was associated with poorer socio-cognitive performance in both EP and IUGR children.

Beyond contact-based transmission networks: the role of spatial coincidence.

Animal societies rely on interactions between group members to effectively communicate and coordinate their actions. To date, the transmission properties of interaction networks formed by direct physical contacts have been extensively studied for many animal societies and in all cases found to inhibit spreading. Such direct interactions do not, however, represent the only viable pathways. When spreading agents can persist in the environment, indirect transmission via 'same-place, different-time' spatial coincidences becomes possible. Previous studies have neglected these indirect pathways and their role in transmission. Here, we use rock ant colonies, a model social species whose flat nest geometry, coupled with individually tagged workers, allowed us to build temporally and spatially explicit interaction networks in which edges represent either direct physical contacts or indirect spatial coincidences. We show how the addition of indirect pathways allows the network to enhance or inhibit the spreading of different types of agent. This dual-functionality arises from an interplay between the interaction-strength distribution generated by the ants' movement and environmental decay characteristics of the spreading agent. These findings offer a general mechanism for understanding how interaction patterns might be tuned in animal societies to control the simultaneous transmission of harmful and beneficial agents.

Bayesian Networks for the Age Classification of Living Individuals: a Study on Transition Analysis

Over the past few decades, age estimation of living persons has represented a challenging task for many forensic services worldwide. In general, the process for age estimation includes the observation of the degree of maturity reached by some physical attributes, such as dentition or several ossification centers. The estimated chronological age or the probability that an individual belongs to a meaningful class of ages is then obtained from the observed degree of maturity by means of various statistical methods. Among these methods, those developed in a Bayesian framework offer to users the possibility of coherently dealing with the uncertainty associated with age estimation and of assessing in a transparent and logical way the probability that an examined individual is younger or older than a given age threshold. Recently, a Bayesian network for age estimation has been presented in scientific literature; this kind of probabilistic graphical tool may facilitate the use of the probabilistic approach. Probabilities of interest in the network are assigned by means of transition analysis, a statistical parametric model, which links the chronological age and the degree of maturity by means of specific regression models, such as logit or probit models. Since different regression models can be employed in transition analysis, the aim of this paper is to study the influence of the model in the classification of individuals. The analysis was performed using a dataset related to the ossifications status of the medial clavicular epiphysis and results support that the classification of individuals is not dependent on the choice of the regression model.