Hard instances of algorithms and proof systems

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

Numerical Taxonomy of Old World Phlebotominae (Diptera: Psychodidae): 2. Restatement of Classification upon Subgeneric Morphological Characters

Numerical analyses (correspondence analysis, ascending hierarchical classification, and cladistics) were done with morphological characters of adult phlebotomine sand flies. The resulting classification largely confirms that of classical taxonomy for supra-specific groups from the Old World, though the positions of some groups are adjusted. The taxa Spelaeophlebotomus Theodor 1948, Idiophlebotomus Quate & Fairchild 1961, Australophlebotomus Theodor 1948 and Chinius Leng 1987 are notably distinct from other Old World groups, particularly from the genus Phlebotomus Rondani & Berté 1840. Spelaeomyia Theodor 1948 and, in particular, Parvidens Theodor & Mesghali 1964 are clearly separate from Sergentomyia França & Parrot 1920.

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.

International consensus conference on PFAPA syndrome: evaluation of a new set of classification criteria

INTRODUCTION: PFAPA syndrome is characterized by periodic fever, associated with pharyngitis, cervical adenitis and/or aphthous stomatitis and belongs to the auto-inflammatory diseases. Diagnostic criteria are based on clinical features and the exclusion of other periodic fever syndromes. An analysis of a large cohort of patients has shown weaknesses for these criteria and there is a lack of international consensus. An International Conference was held in Morges in November 2008 to propose a new set of classification criteria based on a consensus among experts in the field.OBJECTIVE: We aimed to verify the applicability of the new set of classification criteria.PATIENTS & METHODS: 80 patients diagnosed with PFAPA syndrome from 3 centers (Genoa, Lausanne and Geneva) for pediatric rheumatology were included in the study. A detailed description of the clinical and laboratory features was obtained. The new classification criteria and the actual diagnostic criteria were applied to the patients.RESULTS: Only 40/80 patients (50%) fulfilled all criteria of the new classification. 31 patients were excluded because they didn't meet one of the 7 diagnostic criteria, 7 because of 2 criteria, and one because of 3 criteria. When we applied the current criteria to the same patients, 11/80 patients (13.7%) needed to be excluded. 8/80 patients (10%) were excluded from both sets. Exclusion was related only to some of the criteria. Number of patients for each not fulfilled criterion (new set of criteria/actual criteria): age (1/6), symptoms between episodes (2/2), delayed growth (4/1), main symptoms (21/0), periodicity, length of fever, interval between episodes, and length of disease (20/0). The application of some of the new criteria was not easy, as they were both very restrictive and needed precise information from the patients.CONCLUSION: Our work has shown that the new set of classification criteria can be applied to patients suspected for PFAPA syndrome, but it seems to be more restrictive than the actual diagnostic criteria. A further work of validation needs to be done in order to determine if this new set of classification criteria allow a good discrimination between PFAPA patients and other causes of recurrent fever syndromes.

Classification of human astrocytic gliomas on the basis of gene expression: a correlated group of genes with angiogenic activity emerges as a strong predictor of subtypes.

The development of targeted treatment strategies adapted to individual patients requires identification of the different tumor classes according to their biology and prognosis. We focus here on the molecular aspects underlying these differences, in terms of sets of genes that control pathogenesis of the different subtypes of astrocytic glioma. By performing cDNA-array analysis of 53 patient biopsies, comprising low-grade astrocytoma, secondary glioblastoma (respective recurrent high-grade tumors), and newly diagnosed primary glioblastoma, we demonstrate that human gliomas can be differentiated according to their gene expression. We found that low-grade astrocytoma have the most specific and similar expression profiles, whereas primary glioblastoma exhibit much larger variation between tumors. Secondary glioblastoma display features of both other groups. We identified several sets of genes with relatively highly correlated expression within groups that: (a). can be associated with specific biological functions; and (b). effectively differentiate tumor class. One prominent gene cluster discriminating primary versus nonprimary glioblastoma comprises mostly genes involved in angiogenesis, including VEGF fms-related tyrosine kinase 1 but also IGFBP2, that has not yet been directly linked to angiogenesis. In situ hybridization demonstrating coexpression of IGFBP2 and VEGF in pseudopalisading cells surrounding tumor necrosis provided further evidence for a possible involvement of IGFBP2 in angiogenesis. The separating groups of genes were found by the unsupervised coupled two-way clustering method, and their classification power was validated by a supervised construction of a nearly perfect glioma classifier.

UOC Algorithms

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