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.

Molecular characterisation of intermediate snail hosts and the search for resistance genes

The relationship between schistosomes and their intermediate hosts is an extremely intricate one with strains and species of the parasite depending on particular species of snail, which in turn may vary in their susceptibility to the parasites. In order to gain a better understanding of the epidemiology of the disease we have been investigating the use of molecular markers for snail identification and for studying host-parasite relationships. In this paper we will draw on examples concerning schistosomiasis in West and East Africa to illustrate how a molecular analysis can be used as part of a "total evidence" approach to characterisation of Bulinus species and provide insights into parasite transmission. Particular emphasis is given to ribosomal RNA genes (rRNA), random amplified polymorphic DNA (RAPDs) and the mitochondrial gene cytochrome oxidase I (COI). Snails resistant to infection occur naturally and there is a genetic basis for this resistance. In Biomphalaria glabrata resistance to Schistosoma mansoni is known to be a polygenic trait and we have initiated a preliminary search for snail genomic regions linked to, or involved in, resistance by using a RAPD based approach in conjunction with progeny pooling methods. We are currently characterising a variety of STSs (sequence tagged sites) associated with resistance. These can be used for local linkage and interval mapping to define genomic regions associated with the resistance trait. The development of such markers into simple dot-blot or specific PCR-based assays may have a direct and practical application for the identification of resistant snails in natural populations.

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.

Forensic examination of ink by high-performance thin layer chromatography - The United States Secret Service Digital Ink Library

Forensic examinations of ink have been performed since the beginning of the 20th century. Since the 1960s, the International Ink Library, maintained by the United States Secret Service, has supported those analyses. Until 2009, the search and identification of inks were essentially performed manually. This paper describes the results of a project designed to improve ink samples' analytical and search processes. The project focused on the development of improved standardization procedures to ensure the best possible reproducibility between analyses run on different HPTLC plates. The successful implementation of this new calibration method enabled the development of mathematical algorithms and of a software package to complement the existing ink library.

The search for new antimalarial drugs from plants used to treat fever and malaria or plants ramdomly selected: a review

In this review we discuss the ongoing situation of human malaria in the Brazilian Amazon, where it is endemic causing over 610,000 new acute cases yearly, a number which is on the increase. This is partly a result of drug resistant parasites and new antimalarial drugs are urgently needed. The approaches we have used in the search of new drugs during decades are now reviewed and include ethnopharmocology, plants randomly selected, extracts or isolated substances from plants shown to be active against the blood stage parasites in our previous studies. Emphasis is given on the medicinal plant Bidens pilosa, proven to be active against the parasite blood stages in tests using freshly prepared plant extracts. The anti-sporozoite activity of one plant used in the Brazilian endemic area to prevent malaria is also described, the so called "Indian beer" (Ampelozizyphus amazonicus, Rhamnaceae). Freshly prepared extracts from the roots of this plant were totally inactive against blood stage parasites, but active against sporozoites of Plasmodium gallinaceum or the primary exoerythrocytic stages reducing tissue parasitism in inoculated chickens. This result will be of practical importance if confirmed in mammalian malaria. Problems and perspectives in the search for antimalarial drugs are discussed as well as the toxicological and clinical trials to validate some of the active plants for public health use in Brazil.

Visual search in spatial neglect studied with a preview paradigm.

Impaired visual search is a hallmark of spatial neglect. When searching for an unique feature (e.g., color) neglect patients often show only slight visual field asymmetries. In contrast, when the target is defined by a combination of features (e.g., color and form) they exhibit a severe deficit of contralesional search. This finding suggests a selective impairment of the serial deployment of spatial attention. Here, we examined this deficit with a preview paradigm. Neglect patients searched for a target defined by the conjunction of shape and color, presented together with varying numbers of distracters. The presentation time was varied such that on some trials participants previewed the target together with same-shape/different-color distracters, for 300 or 600 ms prior to the appearance of additional different-shape/same-color distracters. On the remaining trials the target and all distracters were shown simultaneously. Healthy participants exhibited a serial search strategy only when all items were presented simultaneously, whereas in both preview conditions a pop-out effect was observed. Neglect patients showed a similar pattern when the target was presented in the right hemifield. In contrast, when searching for a target in the left hemifield they showed serial search in the no-preview condition, as well as with a preview of 300 ms, and partly even at 600 ms. A control experiment suggested that the failure to fully benefit from item preview was probably independent of accurate perception of time. Our results, when viewed in the context of existing literature, lead us to conclude that the visual search deficit in neglect reflects two additive factors: a biased representation of attentional priority in favor of ipsilesional information and exaggerated capture of attention by ipsilesional abrupt onsets.

Search for Borrelia sp. in ticks collected from potential reservoirs in an urban forest reserve in the State of Mato Grosso do Sul, Brazil: a short report

A total of 128 ticks of the genus Amblyomma were recovered from 5 marsupials (Didelphis albiventris) - with 4 recaptures - and 17 rodents (16 Bolomys lasiurus and 1 Rattus norvegicus) captured in an urban forest reserve in Campo Grande, State of Mato Grosso do Sul, Brazil. Of the ticks collected, 95 (78.9%) were in larval form and 22 (21.1%) were nymphs; the only adult (0.8%) was identified as A. cajennense. Viewed under dark-field microscopy in the fourth month after seeding, 9 cultures prepared from spleens and livers of the rodents, blood of the marsupials, and macerates of Amblyomma sp. nymphs revealed spiral-shaped, spirochete-like structures resembling those of Borrelia sp. Some of them showed little motility, while others were non-motile. No such structures could be found either in positive Giemsa-stained culture smears or under electron microscopy. No PCR amplification of DNA from those cultures could be obtained by employing Leptospira sp., B. burgdorferi, and Borrelia sp. primers. These aspects suggest that the spirochete-like structures found in this study do not fit into the genera Borrelia or Leptospira, requiring instead to be isolated for proper identification.

Antigenic community between Schistosoma mansoni and Biomphalaria glabrata: on the search of candidate antigens for vaccines

We have previously confirmed the presence of common antigens between Schistosoma mansoni and its vector, Biomphalaria glabrata. Cross-reactive antigens may be important as possible candidates for vaccine and diagnosis of schistosomiasis. Sera from outbred mice immunized with a soluble Biomphalaria glabrata antigen (SBgA) of non-infected B. glabrata snails recognized molecules of SBgA itself and S. mansoni AWA by Western blot. Recognition of several molecules of the SBgA were inhibited by pre-incubation with AWA (16, 30, 36, 60 and 155 kDa). The only specific molecule of AWA, inhibited by SBgA, was a 120 kDa protein. In order to determine which epitopes of SBgA were glycoproteins, the antigen was treated with sodium metaperiodate and compared with non-treated antigen. Molecules of 140, 60 and 24 kDa in the SBgA appear to be glycoproteins. Possible protective effects of the SBgA were evaluated immunizing outbred mice in two different experiments using Freund's Adjuvant. In the first one (12 mice/group), we obtained a significant level of protection (46%) in the total worm load, with a high variability in worm recovery. In the second experiment (22 mice/group), no significant protection was observed, neither in worm load nor in egg production per female. Our results suggest that SBgA constitutes a rich source of candidate antigens for diagnosis and prophylactic studies.

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.