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.

Parasite and egg burden, hepatic collagen and histologic pattern of liver granulomas in selection III high and low antibody responder mice infected with Schistosoma mansoni

Selection III mice have particular immunological characteristics: they are high (H III) or low (L III) antibody producer animals, yet both lines display similar T cell responses and macrophage activities. We submittedthese mice to infection with Schistosoma mansoni to assess in vivo parasite and egg burden, hepatic collagen and cellular composition of granulomas in both lines. Titration of anti-Schistosoma IgG by ELISA showed remarkably higher values inH III line, at both studied periods (8th and 12th weeks post-infection). Nevertheless, the number of adult worms recovered from the portal system was similar inboth lines, being not associated with anti-Schistosoma antibody levels. There isan increase in hepatic collagen from the 8th to the 12th weeks post-infection, which is paralleled by an increase in the number of eggs in the liver. This association apparently occurs at the same radio in H III and L III animals. The most important difference found between the two lines was the outstanding contrast interms of volume and eosinophil counts in the granulomas, with lesions from H IIImice clearly being larger and containing more of these cells than LIII lesions.

Protein recovery, separation and purification: selection of optimal techniques using an expert system

The paper discusses the utilization of new techniques ot select processes for protein recovery, separation and purification. It describesa rational approach that uses fundamental databases of proteins molecules to simplify the complex problem of choosing high resolution separation methods for multi component mixtures. It examines the role of modern computer techniques to help solving these questions.

Are parties domocratizing themselves? the evolution of leardership selection in Spain (1977-2008)

The aim of this paper is to verify, for the Spanish case, whether between 1977 and 2008 has increased the internal democracy of the major political parties (PSOE, AP / PP, PCE / IU, PNV and CDC). To do this, we will focus on their leadership selection processes, one of the key elements associated with intra-party democracy. The paper is going to introduce data on four different dimensions of leadership selection: the certification process, the voting procedure, the inclusiveness of the selectorate and, finally, the degree of competitiveness. The results will show that have been few changes in the leadership selection processes of the Spanish political parties since 1977. However, the results of the Spanish case will also be used to suggest some preliminary links between the four dimensions.

Knowledge of Catalan, public/private sector choice and earnings: Evidence from a double sample selection model

This paper explores the earnings return to Catalan knowledge for public and private workers in Catalonia. In doing so, we allow for a double simultaneous selection process. We consider, on the one hand, the non-random allocation of workers into one sector or another, and on the other, the potential self-selection into Catalan proficiency. In addition, when correcting the earnings equations, we take into account the correlation between the two selectivity rules. Our findings suggest that the apparent higher language return for public sector workers is entirely accounted for by selection effects, whereas knowledge of Catalan has a significant positive return in the private sector, which is somewhat higher when the selection processes are taken into account.

Development and selection of NKT cells.

NKT cells utilize a restricted alphabeta TCR repertoire that recognizes glycolipids in association with CD1d. The recent development of fluorescent CD1d tetramers loaded with the synthetic glycolipid alpha-galactosyl-ceramide has led to a clearer definition of NKT-cell subsets as well as important insights into their developmental origin. As many as four subsets may exist, differing in NK1.1 expression, TCR repertoire and dependence on CD1d and various glycolipids for development. Two different lineage-commitment models have been proposed, with most evidence favoring a byproduct of conventional-T-cell development.

Trade, firm selection, and innovation: the competition channel

The availability of rich firm-level data sets has recently led researchers to uncover new evidence on the effects of trade liberalization. First, trade openness forces the least productive firms to exit the market. Secondly, it induces surviving firms to increase their innovation efforts and thirdly, it increases the degree of product market competition. In this paper we propose a model aimed at providing a coherent interpretation of these findings. We introducing firm heterogeneity into an innovation-driven growth model, where incumbent firms operating in oligopolistic industries perform cost-reducing innovations. In this framework, trade liberalization leads to higher product market competition, lower markups and higher quantity produced. These changes in markups and quantities, in turn, promote innovation and productivity growth through a direct competition effect, based on the increase in the size of the market, and a selection effect, produced by the reallocation of resources towards more productive firms. Calibrated to match US aggregate and firm-level statistics, the model predicts that a 10 percent reduction in variable trade costs reduces markups by 1:15 percent, firm surviving probabilities by 1 percent, and induces an increase in productivity growth of about 13 percent. More than 90 percent of the trade-induced growth increase can be attributed to the selection effect.

Monophyletic origin of multiple clonal lineages in an asexual fish (Poecilia formosa).

Despite the advantage of avoiding the costs of sexual reproduction, asexual vertebrates are very rare and often considered evolutionarily disadvantaged when compared to sexual species. Asexual species, however, may have advantages when colonizing (new) habitats or competing with sexual counterparts. They are also evolutionary older than expected, leaving the question whether asexual vertebrates are not only rare because of their 'inferior' mode of reproduction but also because of other reasons. A paradigmatic model system is the unisexual Amazon molly, Poecilia formosa, that arose by hybridization of the Atlantic molly, Poecilia mexicana, as the maternal ancestor, and the sailfin molly, Poecilia latipinna, as the paternal ancestor. Our extensive crossing experiments failed to resynthesize asexually reproducing (gynogenetic) hybrids confirming results of previous studies. However, by producing diploid eggs, female F(1) -hybrids showed apparent preadaptation to gynogenesis. In a range-wide analysis of mitochondrial sequences, we examined the origin of P. formosa. Our analyses point to very few or even a single origin(s) of its lineage, which is estimated to be approximately 120,000 years old. A monophyletic origin was supported from nuclear microsatellite data. Furthermore, a considerable degree of genetic variation, apparent by high levels of clonal microsatellite diversity, was found. Our molecular phylogenetic evidence and the failure to resynthesize the gynogenetic P. formosa together with the old age of the species indicate that some unisexual vertebrates might be rare not because they suffer the long-term consequences of clonal reproduction but because they are only very rarely formed as a result of complex genetic preconditions necessary to produce viable and fertile clonal genomes and phenotypes ('rare formation hypothesis').

Sequencing and identification of expressed Schistosoma mansoni genes by random selection of cDNA clones from a directional library

We have initiated a gene discovery program in Schistosoma mansoni based on the technique of Expressed Sequence Tags (ESTs), i.e. partial sequences of cDNAs obtained from single passes in automatic DNA sequencers. ESTs can be used to identify genese onf the basis of their homology whith sequences from other species deposited in DNA or protein databases. Trasncripts with sequences without matches in teh databases may represent novel parasite-specific genes. This approach has shown to be very efficient and in less than two years a broad range of novel genes has already been ascertained, more than doubling the number of known S. mansoni genes.

On the maintenance of sex-chromosome polymorphism by sex-antagonistic selection

Complex sex-determination systems are a priori unstable and require specific selective forces for their maintenance. Analytical derivations have suggested that sex-antagonistic selection may play such a role, but this assumed absence of recombination between the sex-determining and sex-antagonistic genes. Using individual-based simulations, and focusing on the sex chromosome and coloration polymorphisms of platy fishes as a case study, we show that the conditions for polymorphism maintenance induce female-biases in primary sex ratios, so that sex-ratio selection makes the system collapse towards male- or female heterogamety as soon as recombinant genotypes appear. However, a polymorphism can still be maintained under scenarios comprising strong sexual selection against dull males, mild natural selection against bright females, and low recombination rates. Though such conditions are plausibly met in natural populations of fishes harbouring such polymorphisms, quantitative empirical evaluations are required to properly test whether sex-antagonistic selection is a causal agent, or if other selective processes are required (such as local mate competition favouring female biased sex ratios).

Analysis of the clonal diversity of Staphylococcus aureus methicillin-resistant strains isolated at João Pessoa, state of Paraíba, Brazil

To investigate the clonal diversity of Staphylococcus aureus strains isolated at João Pessoa, State of Paraíba, Brazil, digested genomic DNA were studied by pulsed-field gel electrophoresis (PFGE) in nine methicillin-resistant strains (MRSA) and three methicillin-sensitive strains (MSSA), selected among 67 isolates based on their antimicrobial susceptibility and epidemiology. The isolates were obtained between April and November 1992 from the Hospital of the Federal University of Paraíba, located in João Pessoa. Two MRSA isolates from the Oswaldo Cruz Hospital, São Paulo, Brazil, including an epidemic strain previously detected from different hospitals at the country were used as control. Five different patterns, were demonstrated by MRSA isolated in João Pessoa and these patterns were described in several epidemiologically unrelated hospitals in São Paulo. Our results suggest the interstate dissemination of a MRSA clone in João Pessoa which is similar to that described in other cities of Brazil.

Biological comparison between three clones of Trypanosoma cruzi and the strain of origin (Bolivia) with reference to clonal evolution studies

After isolating three clones of Trypanasoma cruzi (Bolivia), we first characterized them according to parasitaemia, pleomorphism and virulence, and then histopathologically. The study's interest lies on the hypothesis that clonal evolution of T. cruzi has a major impact on biologically relevant properties of this parasite. Data obtained from the studies of parasitaemia, pleomorphism and virulence showed no differences between the groups studied. As a final point, the histopathological study shows us a muscular tissue tropism both in clones and in their mother strain (Bolivia). In this paper, we conclude that Bolivia strain and clones isolated from it, pertaining to the same major clone share similar biological properties.

A critical role for the T cell receptor alpha-chain connecting peptide domain in positive selection of CD1-independent NKT cells.

Natural killer T (NKT) cells are a subset of mature alpha beta TCR(+) cells that co-express NK lineage markers. Whereas most NKT cells express a canonical Valpha14/Vbeta8.2 TCR and are selected by CD1d, a minority of NKT cells express a diverse TCR repertoire and develop independently of CD1d. Little is known about the selection requirements of CD1d-independent NKT cells. We show here that NKT cells develop in RAG-deficient mice expressing an MHC class II-restricted transgenic TCR (Valpha2/Vbeta8.1) but only under conditions that lead to negative selection of conventional T cells. Moreover development of NKT cells in these mice is absolutely dependent upon an intact TCR alpha-chain connecting peptide domain, which is required for positive selection of conventional T cells via recruitment of the ERK signaling pathway. Collectively our data demonstrate that NKT cells can develop as a result of high avidity TCR/MHC class II interactions and suggest that common signaling pathways are involved in the positive selection of CD1d-independent NKT cells and conventional T cells.