Hard instances of algorithms and proof systems

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

Bioinformática: interfaz web para estudiar el efecto de diferentes condiciones sobre la expresión de los genes

El trabajo realizado se divide en dos bloques bien diferenciados, ambos relacionados con el análisis de microarrays. El primer bloque consiste en agrupar las condiciones muestrales de todos los genes en grupos o clústers. Estas agrupaciones se obtienen al aplicar directamente sobre la microarray los siguientes algoritmos de agrupación: SOM,PAM,SOTA,HC y al aplicar sobre la microarray escalada con PC y MDS los siguientes algoritmos: SOM,PAM,SOTA,HC y K-MEANS. El segundo bloque consiste en realizar una búsqueda de genes basada en los intervalos de confianza de cada clúster de la agrupación activa. Las condiciones de búsqueda ajustadas por el usuario se validan para cada clúster respecto el valor basal 0 y respecto el resto de clústers, para estas validaciones se usan los intervalos de confianza. Estos dos bloques se integran en una aplicación web ya existente, el applet PCOPGene, alojada en el servidor: http://revolutionresearch.uab.es.

The Role of the European Union in the Processes to Ban Cluster Munitions

At the end of 2008 the Convention on Cluster Munitions (CCM) that outlawed almost all types of cluster munitions was signed. It was the product of the so-called Oslo process, which had been set up two years earlier as a reaction to the failure to add a new protocol banning cluster munitions to the Convention on Certain Conventional Weapons (CCW). The position of the EU in these two processes was ambivalent: on the one hand it belonged to the strongest proponents for a new protocol within the CCW, but on the other hand the member states were in general not able to act jointly in the Oslo Process. According to this working paper especially the aspect of national security and the related relationship to the United States influenced the stances of many member states and complicated the formation of a common European position. There were common normative values of the EU detected, which played a role in the CCW, but they were only secondary to other interests of the member states.

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.

Break zones in the distributions of alleles and species in alpine plants

Aim  We test for the congruence between allele-based range boundaries (break zones) in silicicolous alpine plants and species-based break zones in the silicicolous flora of the European Alps. We also ask whether such break zones coincide with areas of large elevational variation.Location  The European Alps.Methods  On a regular grid laid across the entire Alps, we determined areas of allele- and species-based break zones using respective clustering algorithms, identifying discontinuities in cluster distributions (breaks), and quantifying integrated break densities (break zones). Discontinuities were identified based on the intra-specific genetic variation of 12 species and on the floristic distribution data from 239 species, respectively. Coincidence between the two types of break zones was tested using Spearman's correlation. Break zone densities were also regressed on topographical complexity to test for the effect of elevational variation.Results  We found that two main break zones in the distribution of alleles and species were significantly correlated. Furthermore, we show that these break zones are in topographically complex regions, characterized by massive elevational ranges owing to high mountains and deep glacial valleys. We detected a third break zone in the distribution of species in the eastern Alps, which is not correlated with topographic complexity, and which is also not evident from allelic distribution patterns. Species with the potential for long-distance dispersal tended to show larger distribution ranges than short-distance dispersers.Main conclusions  We suggest that the history of Pleistocene glaciations is the main driver of the congruence between allele-based and species-based distribution patterns, because occurrences of both species and alleles were subject to the same processes (such as extinction, migration and drift) that shaped the distributions of species and genetic lineages. Large elevational ranges have had a profound effect as a dispersal barrier for alleles during post-glacial immigration. Because plant species, unlike alleles, cannot spread via pollen but only via seed, and thus disperse less effectively, we conclude that species break zones are maintained over longer time spans and reflect more ancient patterns than allele break zones.Conny Thiel-Egenter and Nadir Alvarez contributed equally to this paper and are considered joint first authors.

Characterization of the Aspergillus nidulans biotin biosynthetic gene cluster and use of the bioDA gene as a new transformation marker.

The genes involved in the biosynthesis of biotin were identified in the hyphal fungus Aspergillus nidulans through homology searches and complementation of Escherichia coli biotin-auxotrophic mutants. Whereas the 7,8-diaminopelargonic acid synthase and dethiobiotin synthetase are encoded by distinct genes in bacteria and the yeast Saccharomyces cerevisiae, both activities are performed in A. nidulans by a single enzyme, encoded by the bifunctional gene bioDA. Such a bifunctional bioDA gene is a genetic feature common to numerous members of the ascomycete filamentous fungi and basidiomycetes, as well as in plants and oömycota. However, unlike in other eukaryota, the three bio genes contributing to the four enzymatic steps from pimeloyl-CoA to biotin are organized in a gene cluster in pezizomycotina. The A. nidulans auxotrophic mutants biA1, biA2 and biA3 were all found to have mutations in the 7,8-diaminopelargonic acid synthase domain of the bioDA gene. Although biotin auxotrophy is an inconvenient marker in classical genetic manipulations due to cross-feeding of biotin, transformation of the biA1 mutant with the bioDA gene from either A. nidulans or Aspergillus fumigatus led to the recovery of well-defined biotin-prototrophic colonies. The usefulness of bioDA gene as a novel and robust transformation marker was demonstrated in co-transformation experiments with a green fluorescent protein reporter, and in the efficient deletion of the laccase (yA) gene via homologous recombination in a mutant lacking non-homologous end-joining activity.

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.

Leukemic cluster growth in culture is an independent risk factor for acute myeloid leukemia and short survival in patients with myelodysplastic syndrome

In patients with myelodysplastic syndrome (MDS) precursor cell cultures (colony-forming unit cells, CFU-C) can provide an insight into the growth potential of malignant myeloid cells. In a retrospective single-center study of 73 untreated MDS patients we assessed whether CFU-C growth patterns were of prognostic value in addition to established criteria. Abnormalities were classified as qualitative (i.e. leukemic cluster growth) or quantitative (i.e. strongly reduced/absent growth). Thirty-nine patients (53%) showed leukemic growth, 26 patients (36%) had strongly reduced/absent colony growth, and 12 patients showed both. In a univariate analysis the presence of leukemic growth was associated with strongly reduced survival (at 10 years 4 vs. 34%, p = 0.004), and a high incidence of transformation to AML (76 vs. 32%, p = 0.01). Multivariate analysis identified leukemic growth as a strong and independent predictor of early death (relative risk 2.12, p = 0.03) and transformation to AML (relative risk 2.63, p = 0.04). Quantitative abnormalities had no significant impact on the disease course. CFU- C assays have significant predictive value in addition to established prognostic factors in MDS. Leukemic growth identifies a subpopulation of MDS patients with poor prognosis.

Universal screening and decolonization for control of MRSA in nursing homes : a cluster randomized controlled study

OBJECTIVE The risk of carrying methicillin-resistant Staphylococcus aureus (MRSA) is higher among nursing home (NH) residents than in the general population. However, control strategies are not clearly defined in this setting. In this study, we compared the impact of standard precautions either alone (control) or combined with screening of residents and decolonization of carriers (intervention) to control MRSA in NHs. DESIGN Cluster randomized controlled trial SETTING NHs of the state of Vaud, Switzerland PARTICIPANTS Of 157 total NHs in Vaud, 104 (67%) participated in the study. INTERVENTION Standard precautions were enforced in all participating NHs, and residents underwent MRSA screening at baseline and 12 months thereafter. All carriers identified in intervention NHs, either at study entry or among newly admitted residents, underwent topical decolonization combined with environmental disinfection, except in cases of MRSA infection, MRSA bacteriuria, or deep skin ulcers. RESULTS NHs were randomly allocated to a control group (51 NHs, 2,412 residents) or an intervention group (53 NHs, 2,338 residents). Characteristics of NHs and residents were similar in both groups. The mean screening rates were 86% (range, 27%-100%) in control NHs and 87% (20%-100%) in intervention NHs. Prevalence of MRSA carriage averaged 8.9% in both control NHs (range, 0%-43%) and intervention NHs (range, 0%-38%) at baseline, and this rate significantly declined to 6.6% in control NHs and to 5.8% in intervention NHs after 12 months. However, the decline did not differ between groups (P=.66). CONCLUSION Universal screening followed by decolonization of carriers did not significantly reduce the prevalence of the MRSA carriage rate at 1 year compared with standard precautions

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