Hard instances of algorithms and proof systems

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

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.

Extreme Precipitation Modelling Using Geostatistics and Machine Learning Algorithms

The paper presents an approach for mapping of precipitation data. The main goal is to perform spatial predictions and simulations of precipitation fields using geostatistical methods (ordinary kriging, kriging with external drift) as well as machine learning algorithms (neural networks). More practically, the objective is to reproduce simultaneously both the spatial patterns and the extreme values. This objective is best reached by models integrating geostatistics and machine learning algorithms. To demonstrate how such models work, two case studies have been considered: first, a 2-day accumulation of heavy precipitation and second, a 6-day accumulation of extreme orographic precipitation. The first example is used to compare the performance of two optimization algorithms (conjugate gradients and Levenberg-Marquardt) of a neural network for the reproduction of extreme values. Hybrid models, which combine geostatistical and machine learning algorithms, are also treated in this context. The second dataset is used to analyze the contribution of radar Doppler imagery when used as external drift or as input in the models (kriging with external drift and neural networks). Model assessment is carried out by comparing independent validation errors as well as analyzing data patterns.

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.

Machine learning algorithms for spatial data. Case studies: Environmental pollution, natural hazards, renewable resources

This paper presents general problems and approaches for the spatial data analysis using machine learning algorithms. Machine learning is a very powerful approach to adaptive data analysis, modelling and visualisation. The key feature of the machine learning algorithms is that they learn from empirical data and can be used in cases when the modelled environmental phenomena are hidden, nonlinear, noisy and highly variable in space and in time. Most of the machines learning algorithms are universal and adaptive modelling tools developed to solve basic problems of learning from data: classification/pattern recognition, regression/mapping and probability density modelling. In the present report some of the widely used machine learning algorithms, namely artificial neural networks (ANN) of different architectures and Support Vector Machines (SVM), are adapted to the problems of the analysis and modelling of geo-spatial data. Machine learning algorithms have an important advantage over traditional models of spatial statistics when problems are considered in a high dimensional geo-feature spaces, when the dimension of space exceeds 5. Such features are usually generated, for example, from digital elevation models, remote sensing images, etc. An important extension of models concerns considering of real space constrains like geomorphology, networks, and other natural structures. Recent developments in semi-supervised learning can improve modelling of environmental phenomena taking into account on geo-manifolds. An important part of the study deals with the analysis of relevant variables and models' inputs. This problem is approached by using different feature selection/feature extraction nonlinear tools. To demonstrate the application of machine learning algorithms several interesting case studies are considered: digital soil mapping using SVM, automatic mapping of soil and water system pollution using ANN; natural hazards risk analysis (avalanches, landslides), assessments of renewable resources (wind fields) with SVM and ANN models, etc. The dimensionality of spaces considered varies from 2 to more than 30. Figures 1, 2, 3 demonstrate some results of the studies and their outputs. Finally, the results of environmental mapping are discussed and compared with traditional models of geostatistics.

UOC Algorithms

Aplicació per a iPad a mode de repositori de continguts relacionats amb l'ensenyament d'assignatures d'informàtica.

Evaluation of organ-specific peripheral doses after 2-dimensional, 3-dimensional and hybrid intensity modulated radiation therapy for breast cancer based on Monte Carlo and convolution/superposition algorithms: implications for secondary cancer risk assessment.

To make a comprehensive evaluation of organ-specific out-of-field doses using Monte Carlo (MC) simulations for different breast cancer irradiation techniques and to compare results with a commercial treatment planning system (TPS). Three breast radiotherapy techniques using 6MV tangential photon beams were compared: (a) 2DRT (open rectangular fields), (b) 3DCRT (conformal wedged fields), and (c) hybrid IMRT (open conformal+modulated fields). Over 35 organs were contoured in a whole-body CT scan and organ-specific dose distributions were determined with MC and the TPS. Large differences in out-of-field doses were observed between MC and TPS calculations, even for organs close to the target volume such as the heart, the lungs and the contralateral breast (up to 70% difference). MC simulations showed that a large fraction of the out-of-field dose comes from the out-of-field head scatter fluence (>40%) which is not adequately modeled by the TPS. Based on MC simulations, the 3DCRT technique using external wedges yielded significantly higher doses (up to a factor 4-5 in the pelvis) than the 2DRT and the hybrid IMRT techniques which yielded similar out-of-field doses. In sharp contrast to popular belief, the IMRT technique investigated here does not increase the out-of-field dose compared to conventional techniques and may offer the most optimal plan. The 3DCRT technique with external wedges yields the largest out-of-field doses. For accurate out-of-field dose assessment, a commercial TPS should not be used, even for organs near the target volume (contralateral breast, lungs, heart).

Améliorations et optimisation globale de la méthode des analogues pour la prévision statistique des précipitations. Développement d'un outil de prévision et application opérationnelle au bassin du Rhône à l'amont du Léman.

Le bassin du Rhône à l'amont du Léman peut être sujet à de fortes précipitations en mesure de provoquer des crues significatives. L'objectif du projet MINERVE dans lequel s'inscrit le présent travail consiste à fournir des outils pour la prévision et la gestion des crues par des actions préventives sur les aménagements hydroélectriques à accumulation. Pour satisfaire ce dernier, il est nécessaire de prévoir au mieux les cumuls de précipitations pour les jours suivants. Ceci est actuellement effectué par le modèle numérique de prévision de MétéoSuisse ; mais, en raison des grandes incertitudes liées à la quantification des événements extrêmes, il a été décidé qu'une approche parallèle de nature statistique pourrait compléter l'information disponible. Ainsi, nous avons adapté la méthode des analogues, qui est une technique de prévision statistique des précipitations, au contexte alpin du bassin d'étude. Pour ce faire, plusieurs paramétrisations de la méthode ont été documentées et calibrées. Afin de prendre en main la méthode, nous avons effectué de multiples analyses paramétriques sur les variables synoptiques, mais également sur la constitution de groupements pluviométriques. Une partie conséquente de cette étude a été consacrée à la programmation d'un logiciel de prévision automatique par la méthode des analogues, ainsi qu'à un outil de visualisation des résultats sous forme de cartes et graphiques. Ce logiciel, nommé Atmoswing, permet d'implémenter un grand nombre de méthodes différentes de prévision par analogie. L'outil est opérationnel depuis mi-2011 et nous a permis de confirmer l'intérêt de la prévision par analogie. La méthode étant ici appliquée à un nouveau contexte, un grand nombre de variables synoptiques ont été évaluées. Nous avons alors confirmé l'intérêt des deux niveaux d'analogie sur la circulation atmosphérique et sur le flux d'humidité, tout en apportant des améliorations à celles-ci. Il en résulte des paramétrisations présentant des scores de performance supérieurs aux méthodes de référence considérées. Nous avons également évalué d'autres améliorations, comme l'introduction d'une fenêtre temporelle glissante afin de rechercher de meilleures analogies synoptiques à d'autres heures de la journée, ce qui s'est avéré intéressant, tout comme une prévision infrajournalière à pas de temps de 6 h. Finalement, nous avons introduit une technique d'optimisation globale, les algorithmes génétiques, capable de calibrer la méthode des analogues en considérant tous les paramètres des différents niveaux d'analogie de manière conjointe. Avec cette technique, nous pouvons nous approcher objectivement d'une paramétrisation optimale. Le choix des niveaux atmosphériques et des fenêtres temporelles et spatiales étant automatisé, cette technique peut engendrer un gain de temps, même si elle est relativement exigeante en calculs. Nous avons ainsi pu améliorer la méthode des analogues, et y ajouter de nouveaux degrés de liberté, notamment des fenêtres spatiales et des pondérations différenciées selon les niveaux atmosphériques retenus.

Enhancing fault management performance of two-step QoS routing algorithms in GMPLS networks

In this paper a novel methodology aimed at minimizing the probability of network failure and the failure impact (in terms of QoS degradation) while optimizing the resource consumption is introduced. A detailed study of MPLS recovery techniques and their GMPLS extensions are also presented. In this scenario, some features for reducing the failure impact and offering minimum failure probabilities at the same time are also analyzed. Novel two-step routing algorithms using this methodology are proposed. Results show that these methods offer high protection levels with optimal resource consumption

Enhancing MPLS QoS routing algorithms by using the network protection degree paradigm

IP based networks still do not have the required degree of reliability required by new multimedia services, achieving such reliability will be crucial in the success or failure of the new Internet generation. Most of existing schemes for QoS routing do not take into consideration parameters concerning the quality of the protection, such as packet loss or restoration time. In this paper, we define a new paradigm to develop new protection strategies for building reliable MPLS networks, based on what we have called the network protection degree (NPD). This NPD consists of an a priori evaluation, the failure sensibility degree (FSD), which provides the failure probability and an a posteriori evaluation, the failure impact degree (FID), to determine the impact on the network in case of failure. Having mathematical formulated these components, we point out the most relevant components. Experimental results demonstrate the benefits of the utilization of the NPD, when used to enhance some current QoS routing algorithms to offer a certain degree of protection

Improving Clustering Algorithms for Image Segmentation using Contour and Region Information

In image segmentation, clustering algorithms are very popular because they are intuitive and, some of them, easy to implement. For instance, the k-means is one of the most used in the literature, and many authors successfully compare their new proposal with the results achieved by the k-means. However, it is well known that clustering image segmentation has many problems. For instance, the number of regions of the image has to be known a priori, as well as different initial seed placement (initial clusters) could produce different segmentation results. Most of these algorithms could be slightly improved by considering the coordinates of the image as features in the clustering process (to take spatial region information into account). In this paper we propose a significant improvement of clustering algorithms for image segmentation. The method is qualitatively and quantitative evaluated over a set of synthetic and real images, and compared with classical clustering approaches. Results demonstrate the validity of this new approach

Field optimisation of MosquiTRAP sampling for monitoring Aedes aegypti Linnaeus (Diptera: Culicidae)

A sticky trap designed to capture gravid Aedes (Stegomyia) aegypti mosquitoes, MosquiTRAP, has been evaluated for monitoring this species in Brazil. However, the effects of trap densities on the capture rate of Ae. aegypti females and the sensitivity of vector detection are still unknown. After a preliminary study has identified areas of high and low female mosquito abundance, a set of experiments was conducted in four neighbourhoods of Belo Horizonte (state of Minas Gerais, Brazil) using densities of 1, 2, 4, 8, 16, 32 and 64 traps per block. Trap sensitivity (positive MosquiTRAP index) increased significantly when 1-8 MosquiTRAPs were installed per block in both high and low abundance areas. A strong fit was obtained for the total number of mosquitoes captured with increasing trap densities through a non-linear function (Box-Lucas) (r² = 0,994), which likely exhibits saturation towards an equilibrium level. The capacity of the Mean Female Aedes Index to distinguish between areas of high and low Ae. aegypti abundance was also investigated; the achieved differentiation was shown to be dependent on the MosquiTRAP density.