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.

Semi-supervised segmentation of ultrasound images based on patch representation and continuous min cut.

Ultrasound segmentation is a challenging problem due to the inherent speckle and some artifacts like shadows, attenuation and signal dropout. Existing methods need to include strong priors like shape priors or analytical intensity models to succeed in the segmentation. However, such priors tend to limit these methods to a specific target or imaging settings, and they are not always applicable to pathological cases. This work introduces a semi-supervised segmentation framework for ultrasound imaging that alleviates the limitation of fully automatic segmentation, that is, it is applicable to any kind of target and imaging settings. Our methodology uses a graph of image patches to represent the ultrasound image and user-assisted initialization with labels, which acts as soft priors. The segmentation problem is formulated as a continuous minimum cut problem and solved with an efficient optimization algorithm. We validate our segmentation framework on clinical ultrasound imaging (prostate, fetus, and tumors of the liver and eye). We obtain high similarity agreement with the ground truth provided by medical expert delineations in all applications (94% DICE values in average) and the proposed algorithm performs favorably with the literature.

On dome-shaped norms of reaction for size-to-age at maturity in fishes

The optimal size-to-age at maturity depends on growth and mortality rates, which vary with environment. Therefore, organisms in spatially or temporaly changing environments should develop adaptative phenotypic plasticity for this trait. Experimental work by Alm (1959) on several fish species shows a dome-shape norm of reaction for size-to-age at maturity: size at maturity is smaller in both fast-growing and slow-growing fishes, than it is in fish with a medium growth rate. Using computer simulations, we show that such a dome-shaped norm of reaction is optimal when assuming a finite life span and a negative relationship between production and survival rates. This latter assumption is supported by empirical data, as well as by physiological and emographic arguments.

Fission yeast: in shape to divide.

How are cell morphogenesis and cell cycle coordinated? The fission yeast is a rod-shaped unicellular organism widely used to study how a cell self-organizes in space and time. Here, we discuss recent advances in understanding how the cell acquires and maintains its regular rod shape and uses it to control cell division. The cellular body plan is established by microtubules, which mark antipodal growth zones and medial division. In turn, cellular dimensions are defined by the small GTPase Cdc42 and downstream regulators of vesicle trafficking. Yeast cells then repetitively use their simple rod shape to orchestrate the position and timing of cell division.

Effects of physiological self-crowding of DNA on shape and biological properties of DNA molecules with various levels of supercoiling.

DNA in bacterial chromosomes and bacterial plasmids is supercoiled. DNA supercoiling is essential for DNA replication and gene regulation. However, the density of supercoiling in vivo is circa twice smaller than in deproteinized DNA molecules isolated from bacteria. What are then the specific advantages of reduced supercoiling density that is maintained in vivo? Using Brownian dynamics simulations and atomic force microscopy we show here that thanks to physiological DNA-DNA crowding DNA molecules with reduced supercoiling density are still sufficiently supercoiled to stimulate interaction between cis-regulatory elements. On the other hand, weak supercoiling permits DNA molecules to modulate their overall shape in response to physiological changes in DNA crowding. This plasticity of DNA shapes may have regulatory role and be important for the postreplicative spontaneous segregation of bacterial chromosomes.

Opportunity to shape the prevention and management of obesity

Cooperation and Working Together (CAWT), the cross border health and social care partnership has been working with the Departments of Health to progress a three year cross border obesity prevention and management project aimed at families. They have been successful in securing funding from the EU INTERREG IVA programme. A planning workshop focussing on this will be held on Friday 26 June 2009.

Nature's shape.

Review of the book : "What shape is a snowflake?", by I.S. Weidenfeld & Nicholson, London, UK

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.

Optimization of the piggyBac Transposon Using mRNA and Insulators: Toward a More Reliable Gene Delivery System.

Integrating and expressing stably a transgene into the cellular genome remain major challenges for gene-based therapies and for bioproduction purposes. While transposon vectors mediate efficient transgene integration, expression may be limited by epigenetic silencing, and persistent transposase expression may mediate multiple transposition cycles. Here, we evaluated the delivery of the piggyBac transposase messenger RNA combined with genetically insulated transposons to isolate the transgene from neighboring regulatory elements and stabilize expression. A comparison of piggyBac transposase expression from messenger RNA and DNA vectors was carried out in terms of expression levels, transposition efficiency, transgene expression and genotoxic effects, in order to calibrate and secure the transposition-based delivery system. Messenger RNA reduced the persistence of the transposase to a narrow window, thus decreasing side effects such as superfluous genomic DNA cleavage. Both the CTF/NF1 and the D4Z4 insulators were found to mediate more efficient expression from a few transposition events. We conclude that the use of engineered piggyBac transposase mRNA and insulated transposons offer promising ways of improving the quality of the integration process and sustaining the expression of transposon vectors.