The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

A numerical algorithm for finding solutions of a generalized Nash equilibrium problem

A family of nonempty closed convex sets is built by using the data of the Generalized Nash equilibrium problem (GNEP). The sets are selected iteratively such that the intersection of the selected sets contains solutions of the GNEP. The algorithm introduced by Iusem-Sosa (2003) is adapted to obtain solutions of the GNEP. Finally some numerical experiments are given to illustrate the numerical behavior of the algorithm.

Why do creative industries cluster? An analysis of the determinants of clustering of creative industries

Creative industries tend to concentrate mainly around large- and medium-sized cities, forming creative local production systems. The text analyses the forces behind clustering of creative industries to provide the first empirical explanation of the determinants of creative employment clustering following a multidisciplinary approach based on cultural and creative economics, evolutionary geography and urban economics. A comparative analysis has been performed for Italy and Spain. The results show different patterns of creative employment clustering in both countries. The small role of historical and cultural endowments, the size of the place, the average size of creative industries, the productive diversity and the concentration of human capital and creative class have been found as common factors of clustering in both countries.

Estudio sobre la extracción de puntos característicos en imágenes y sus aplicaciones

En aquest treball realitzem un estudi sobre la detecció y la descripció de punts característics, una tecnologia que permet extreure informació continguda en les imatges. Primerament presentem l'estat de l'art juntament amb una avaluació dels mètodes més rellevants. A continuació proposem els nous mètodes que hem creat de detecció i descripció, juntament amb l'algorisme òptim anomenat DART, el qual supera l'estat de l'art. Finalment mostrem algunes aplicacions on s'utilitzen els punts DART. Basant-se en l'aproximació de l'espai d'escales Gaussià, el detector proposat pot extreure punts de distint tamany invariants davant canvis en el punt de vista, la rotació i la iluminació. La reutilització de l'espai d'escales durant el procés de descripció, així com l'ús d'estructures simplificades i optimitzades, permeten realitzar tot el procediment en un temps computacional menor a l'obtingut fins al moment. Així s'aconsegueixen punts invariants i distingibles de forma ràpida, el qual permet la seva utilització en aplicacions com el seguiment d'objectes, la reconstrucció d'escenaris 3D i en motors de cerca visual.

Clustering or scattering: the underlying reason for regulating distance among retail outlets

Concerns on the clustering of retail industries and professional services in main streets had traditionally been the public interest rationale for supporting distance regulations. Although many geographic restrictions have been suppressed, deregulation has hinged mostly upon the theory results on the natural tendency of outlets to differentiate spatially. Empirical evidence has so far offered mixed results. Using the case of deregulation of pharmacy establishment in a region of Spain, we empirically show how pharmacy locations scatter, and that there is not rationale for distance regulation apart from the underlying private interest of very few incumbents.

Structural prediction of peptides bound to MHC class I.

An ab initio structure prediction approach adapted to the peptide-major histocompatibility complex (MHC) class I system is presented. Based on structure comparisons of a large set of peptide-MHC class I complexes, a molecular dynamics protocol is proposed using simulated annealing (SA) cycles to sample the conformational space of the peptide in its fixed MHC environment. A set of 14 peptide-human leukocyte antigen (HLA) A0201 and 27 peptide-non-HLA A0201 complexes for which X-ray structures are available is used to test the accuracy of the prediction method. For each complex, 1000 peptide conformers are obtained from the SA sampling. A graph theory clustering algorithm based on heavy atom root-mean-square deviation (RMSD) values is applied to the sampled conformers. The clusters are ranked using cluster size, mean effective or conformational free energies, with solvation free energies computed using Generalized Born MV 2 (GB-MV2) and Poisson-Boltzmann (PB) continuum models. The final conformation is chosen as the center of the best-ranked cluster. With conformational free energies, the overall prediction success is 83% using a 1.00 Angstroms crystal RMSD criterion for main-chain atoms, and 76% using a 1.50 Angstroms RMSD criterion for heavy atoms. The prediction success is even higher for the set of 14 peptide-HLA A0201 complexes: 100% of the peptides have main-chain RMSD values < or =1.00 Angstroms and 93% of the peptides have heavy atom RMSD values < or =1.50 Angstroms. This structure prediction method can be applied to complexes of natural or modified antigenic peptides in their MHC environment with the aim to perform rational structure-based optimizations of tumor vaccines.

An algorithm for semi-infinite polynomial optimization

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

An approximation algorithm for #k-SAT

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

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.

Comparing Multilevel Clustering Methods on Weighted Graphs : The Case of Worldwide Air Passenger Traffic 2000-2004

Specific properties emerge from the structure of large networks, such as that of worldwide air traffic, including a highly hierarchical node structure and multi-level small world sub-groups that strongly influence future dynamics. We have developed clustering methods to understand the form of these structures, to identify structural properties, and to evaluate the effects of these properties. Graph clustering methods are often constructed from different components: a metric, a clustering index, and a modularity measure to assess the quality of a clustering method. To understand the impact of each of these components on the clustering method, we explore and compare different combinations. These different combinations are used to compare multilevel clustering methods to delineate the effects of geographical distance, hubs, network densities, and bridges on worldwide air passenger traffic. The ultimate goal of this methodological research is to demonstrate evidence of combined effects in the development of an air traffic network. In fact, the network can be divided into different levels of âeurooecohesionâeuro, which can be qualified and measured by comparative studies (Newman, 2002; Guimera et al., 2005; Sales-Pardo et al., 2007).

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.