An algorithm for semi-infinite polynomial optimization

"Vegeu el resum a l'inici del document del fitxer adjunt."

A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

A parameter-free approach for solving combinatorial optimization problems through biased randomization of efficient heuristics

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases.

On the stability of the optimal value and the optimal set in optimization problems

The paper develops a stability theory for the optimal value and the optimal set mapping of optimization problems posed in a Banach space. The problems considered in this paper have an arbitrary number of inequality constraints involving lower semicontinuous (not necessarily convex) functions and one closed abstract constraint set. The considered perturbations lead to problems of the same type as the nominal one (with the same space of variables and the same number of constraints), where the abstract constraint set can also be perturbed. The spaces of functions involved in the problems (objective and constraints) are equipped with the metric of the uniform convergence on the bounded sets, meanwhile in the space of closed sets we consider, coherently, the Attouch-Wets topology. The paper examines, in a unified way, the lower and upper semicontinuity of the optimal value function, and the closedness, lower and upper semicontinuity (in the sense of Berge) of the optimal set mapping. This paper can be seen as a second part of the stability theory presented in [17], where we studied the stability of the feasible set mapping (completed here with the analysis of the Lipschitz-like property).

Artificial Snow Optimization in Winter Sport Destinations Using a Multi-agent Simulation

This paper presents the Juste-Neige system for predicting the snow height on the ski runs of a resort using a multi-agent simulation software. Its aim is to facilitate snow cover management in order to i) reduce the production cost of artificial snow and to improve the profit margin for the companies managing the ski resorts; and ii) to reduce the water and energy consumption, and thus to reduce the environmental impact, by producing only the snow needed for a good skiing experience. The software provides maps with the predicted snow heights for up to 13 days. On these maps, the areas most exposed to snow erosion are highlighted. The software proceeds in three steps: i) interpolation of snow height measurements with a neural network; ii) local meteorological forecasts for every ski resort; iii) simulation of the impact caused by skiers using a multi-agent system. The software has been evaluated in the Swiss ski resort of Verbier and provides useful predictions.

SwissSidechain: a molecular and structural database of non-natural sidechains.

Amino acids form the building blocks of all proteins. Naturally occurring amino acids are restricted to a few tens of sidechains, even when considering post-translational modifications and rare amino acids such as selenocysteine and pyrrolysine. However, the potential chemical diversity of amino acid sidechains is nearly infinite. Exploiting this diversity by using non-natural sidechains to expand the building blocks of proteins and peptides has recently found widespread applications in biochemistry, protein engineering and drug design. Despite these applications, there is currently no unified online bioinformatics resource for non-natural sidechains. With the SwissSidechain database (http://www.swisssidechain.ch), we offer a central and curated platform about non-natural sidechains for researchers in biochemistry, medicinal chemistry, protein engineering and molecular modeling. SwissSidechain provides biophysical, structural and molecular data for hundreds of commercially available non-natural amino acid sidechains, both in l- and d-configurations. The database can be easily browsed by sidechain names, families or physico-chemical properties. We also provide plugins to seamlessly insert non-natural sidechains into peptides and proteins using molecular visualization software, as well as topologies and parameters compatible with molecular mechanics software.

Socioeconomic status, structural and functional measures of social support, and mortality: The British Whitehall II Cohort Study, 1985-2009.

The authors examined the associations of social support with socioeconomic status (SES) and with mortality, as well as how SES differences in social support might account for SES differences in mortality. Analyses were based on 9,333 participants from the British Whitehall II Study cohort, a longitudinal cohort established in 1985 among London-based civil servants who were 35-55 years of age at baseline. SES was assessed using participant's employment grades at baseline. Social support was assessed 3 times in the 24.4-year period during which participants were monitored for death. In men, marital status, and to a lesser extent network score (but not low perceived support or high negative aspects of close relationships), predicted both all-cause and cardiovascular mortality. Measures of social support were not associated with cancer mortality. Men in the lowest SES category had an increased risk of death compared with those in the highest category (for all-cause mortality, hazard ratio = 1.59, 95% confidence interval: 1.21, 2.08; for cardiovascular mortality, hazard ratio = 2.48, 95% confidence interval: 1.55, 3.92). Network score and marital status combined explained 27% (95% confidence interval: 14, 43) and 29% (95% confidence interval: 17, 52) of the associations between SES and all-cause and cardiovascular mortality, respectively. In women, there was no consistent association between social support indicators and mortality. The present study suggests that in men, social isolation is not only an important risk factor for mortality but is also likely to contribute to differences in mortality by SES.

NS2 protein of hepatitis C virus interacts with structural and non-structural proteins towards virus assembly.

Growing experimental evidence indicates that, in addition to the physical virion components, the non-structural proteins of hepatitis C virus (HCV) are intimately involved in orchestrating morphogenesis. Since it is dispensable for HCV RNA replication, the non-structural viral protein NS2 is suggested to play a central role in HCV particle assembly. However, despite genetic evidences, we have almost no understanding about NS2 protein-protein interactions and their role in the production of infectious particles. Here, we used co-immunoprecipitation and/or fluorescence resonance energy transfer with fluorescence lifetime imaging microscopy analyses to study the interactions between NS2 and the viroporin p7 and the HCV glycoprotein E2. In addition, we used alanine scanning insertion mutagenesis as well as other mutations in the context of an infectious virus to investigate the functional role of NS2 in HCV assembly. Finally, the subcellular localization of NS2 and several mutants was analyzed by confocal microscopy. Our data demonstrate molecular interactions between NS2 and p7 and E2. Furthermore, we show that, in the context of an infectious virus, NS2 accumulates over time in endoplasmic reticulum-derived dotted structures and colocalizes with both the envelope glycoproteins and components of the replication complex in close proximity to the HCV core protein and lipid droplets, a location that has been shown to be essential for virus assembly. We show that NS2 transmembrane region is crucial for both E2 interaction and subcellular localization. Moreover, specific mutations in core, envelope proteins, p7 and NS5A reported to abolish viral assembly changed the subcellular localization of NS2 protein. Together, these observations indicate that NS2 protein attracts the envelope proteins at the assembly site and it crosstalks with non-structural proteins for virus assembly.

Structural Analysis of Networks

Network analysis naturally relies on graph theory and, more particularly, on the use of node and edge metrics to identify the salient properties in graphs. When building visual maps of networks, these metrics are turned into useful visual cues or are used interactively to filter out parts of a graph while querying it, for instance. Over the years, analysts from different application domains have designed metrics to serve specific needs. Network science is an inherently cross-disciplinary field, which leads to the publication of metrics with similar goals; different names and descriptions of their analytics often mask the similarity between two metrics that originated in different fields. Here, we study a set of graph metrics and compare their relative values and behaviors in an effort to survey their potential contributions to the spatial analysis of networks.

Functional analysis and structural modeling of human APOBEC3G reveal the role of evolutionarily conserved elements in the inhibition of human immunodeficiency virus type 1 infection and Alu transposition.

Retroelements are important evolutionary forces but can be deleterious if left uncontrolled. Members of the human APOBEC3 family of cytidine deaminases can inhibit a wide range of endogenous, as well as exogenous, retroelements. These enzymes are structurally organized in one or two domains comprising a zinc-coordinating motif. APOBEC3G contains two such domains, only the C terminal of which is endowed with editing activity, while its N-terminal counterpart binds RNA, promotes homo-oligomerization, and is necessary for packaging into human immunodeficiency virus type 1 (HIV-1) virions. Here, we performed a large-scale mutagenesis-based analysis of the APOBEC3G N terminus, testing mutants for (i) inhibition of vif-defective HIV-1 infection and Alu retrotransposition, (ii) RNA binding, and (iii) oligomerization. Furthermore, in the absence of structural information on this domain, we used homology modeling to examine the positions of functionally important residues and of residues found to be under positive selection by phylogenetic analyses of primate APOBEC3G genes. Our results reveal the importance of a predicted RNA binding dimerization interface both for packaging into HIV-1 virions and inhibition of both HIV-1 infection and Alu transposition. We further found that the HIV-1-blocking activity of APOBEC3G N-terminal mutants defective for packaging can be almost entirely rescued if their virion incorporation is forced by fusion with Vpr, indicating that the corresponding region of APOBEC3G plays little role in other aspects of its action against this pathogen. Interestingly, residues forming the APOBEC3G dimer interface are highly conserved, contrasting with the rapid evolution of two neighboring surface-exposed amino acid patches, one targeted by the Vif protein of primate lentiviruses and the other of yet-undefined function.

Optimisation de la cryo microscopie électronique pour les études des minicercles d'ADN

RESUME : Bien que les propriétés physiques de la structure de l'ADN aient été intensivement étudiées pendant plus de 50 ans il y a encore beaucoup de questions importantes qui attendent des réponses. Par exemple, qu'arrive-t-il à la structure de la double hélice d'ADN nue (sans protéines liées) lorsqu'elle est fortement courbée, de la même manière que dans les nucléosomes? Cet ADN nu est-il facilement plié (il reste dans le régime élastique) ou réduit-il la contrainte de flexion en formant des sites hyperflexibles «kinks» (il sort du régime élastique en cassant l'empilement des paires de bases à certains endroits) ? La microscopie électronique peut fournir une réponse à cette question par visualisation directe des minicercles d'ADN de la longueur d'un tour de nucléosome (environ 90 paires de bases). Pour que la réponse soit scientifiquement valide, on doit observer les molécules d'ADN lorsqu'elles sont en suspension dans la solution d'intérêt et sans que des colorations, produits chimiques ou fixatifs n'aient été ajoutés, étant donné que ceux-ci peuvent changer les propriétés de l'ADN. La technique de la cryo-microscopie électronique (cryo-EM) développée par le groupe de Jacques Dubochet au début des années 80, permet la visualisation directe des molécules d'ADN suspendues dans des couche minces vitrifiées de solutions aqueuses. Toutefois, le faible contraste qui caractérise la cryo-EM combinée avec la très petite taille des minicercles d'ADN rendent nécessaire l'optimisation de plusieurs étapes, aussi bien dans la préparation des échantillons que dans le processus d'acquisition d'images afin d'obtenir deux clichés stéréo qui permettent la reconstruction 3-D des minicercles d'ADN. Dans la première partie de ma thèse, je décris l'optimisation de certains paramètres pour la cryoEM et des processus d'acquisition d'image utilisant comme objets de test des plasmides et d'autres molécules d'ADN. Dans la deuxième partie, je .décris comment j'ai construit les minicercles d'ADN de 94 bp et comment j'ai introduit des modifications structurelles comme des coupures ou des lacunes. Dans la troisième partie, je décris l'analyse des reconstructions des rninicercles d'ADN. Cette analyse, appuyée par des tests biochimiques, indique fortement que des molécules d'ADN sont capables de former de petites molécules circulaires de 94 bp sans dépasser les limites d'élasticité, indiquant que les minicercles adoptent une forme circulaire régulière où la flexion est redistribuée le long la molécule. ABSTRACT : Although physical properties of DNA structure have been intensively studied for over 50 years there are still many important questions that need to be answered. For example, what happens to protein-free double-stranded DNA when it is strongly bent, as in DNA forming nucleosomes? Is such protein-free DNA smoothly bent (i.e. it remains within elastic limits of DNA rigidity) or does it release its bending stress by forming sharp kinks (i.e. it exits the elastic regime and breaks the stacking between neighbouring base-pairs in localized regions)? Electron microscopy can provide an answer to this question by directly visualizing DNA minicircles that have the size of nucleosome gyres (ca 90 bp). For the answer to be scientifically valid, one needs to observe DNA molecules while they are still suspended in the solution of interest and no staining chemicals or fixatives have been added since these can change the properties of the DNA. CryoEM techniques developed by Jacques Dubochet's group beginning in the 1980's permit direct visualization of DNA molecules suspended in cryo-vitrified layers of aqueous solutions. However, a relatively weak contrast of cryo-EM preparations combined with the very small size of the DNA minicircles made it necessary to optimize many of the steps and parameters of the cryo-EM specimen preparation and image acquisition processes in order to obtain stereo-pairs of images that permit the 3-D reconstruction of the observed DNA minicircles. In the first part of my thesis I describe the optimization of the cryo-EM preparation and the image acquisition processes using plasmid size DNA molecules as a test object. In the second part, I describe how I formed the 94 by DNA minicircles and how I introduced structural modifications like nicks or gaps. In the third part, I describe the cryo-EM analysis of the constructed DNA minicircles. That analysis, supported by biochemical tests, strongly indicates that DNA minicircles as small as 94 by remain within the elastic limits of DNA structure, i.e. the minicircles adopt a regular circular shape where bending is redistributed along the molecules.

Optimization of spatial resolution for peripheral magnetic resonance angiography.

RATIONALE AND OBJECTIVES: To determine optimum spatial resolution when imaging peripheral arteries with magnetic resonance angiography (MRA). MATERIALS AND METHODS: Eight vessel diameters ranging from 1.0 to 8.0 mm were simulated in a vascular phantom. A total of 40 three-dimensional flash MRA sequences were acquired with incremental variations of fields of view, matrix size, and slice thickness. The accurately known eight diameters were combined pairwise to generate 22 "exact" degrees of stenosis ranging from 42% to 87%. Then, the diameters were measured in the MRA images by three independent observers and with quantitative angiography (QA) software and used to compute the degrees of stenosis corresponding to the 22 "exact" ones. The accuracy and reproducibility of vessel diameter measurements and stenosis calculations were assessed for vessel size ranging from 6 to 8 mm (iliac artery), 4 to 5 mm (femoro-popliteal arteries), and 1 to 3 mm (infrapopliteal arteries). Maximum pixel dimension and slice thickness to obtain a mean error in stenosis evaluation of less than 10% were determined by linear regression analysis. RESULTS: Mean errors on stenosis quantification were 8.8% +/- 6.3% for 6- to 8-mm vessels, 15.5% +/- 8.2% for 4- to 5-mm vessels, and 18.9% +/- 7.5% for 1- to 3-mm vessels. Mean errors on stenosis calculation were 12.3% +/- 8.2% for observers and 11.4% +/- 15.1% for QA software (P = .0342). To evaluate stenosis with a mean error of less than 10%, maximum pixel surface, the pixel size in the phase direction, and the slice thickness should be less than 1.56 mm2, 1.34 mm, 1.70 mm, respectively (voxel size 2.65 mm3) for 6- to 8-mm vessels; 1.31 mm2, 1.10 mm, 1.34 mm (voxel size 1.76 mm3), for 4- to 5-mm vessels; and 1.17 mm2, 0.90 mm, 0.9 mm (voxel size 1.05 mm3) for 1- to 3-mm vessels. CONCLUSION: Higher spatial resolution than currently used should be selected for imaging peripheral vessels.

Enzymic, phylogenetic, and structural characterization of the unusual papain-like protease domain of Plasmodium falciparum SERA5.

Serine repeat antigen 5 (SERA5) is an abundant antigen of the human malaria parasite Plasmodium falciparum and is the most strongly expressed member of the nine-gene SERA family. It appears to be essential for the maintenance of the erythrocytic cycle, unlike a number of other members of this family, and has been implicated in parasite egress and/or erythrocyte invasion. All SERA proteins possess a central domain that has homology to papain except in the case of SERA5 (and some other SERAs), where the active site cysteine has been replaced with a serine. To investigate if this domain retains catalytic activity, we expressed, purified, and refolded a recombinant form of the SERA5 enzyme domain. This protein possessed chymotrypsin-like proteolytic activity as it processed substrates downstream of aromatic residues, and its activity was reversed by the serine protease inhibitor 3,4-diisocoumarin. Although all Plasmodium SERA enzyme domain sequences share considerable homology, phylogenetic studies revealed two distinct clusters across the genus, separated according to whether they possess an active site serine or cysteine. All Plasmodia appear to have at least one member of each group. Consistent with separate biological roles for members of these two clusters, molecular modeling studies revealed that SERA5 and SERA6 enzyme domains have dramatically different surface properties, although both have a characteristic papain-like fold, catalytic cleft, and an appropriately positioned catalytic triad. This study provides impetus for the examination of SERA5 as a target for antimalarial drug design.