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.

Notch1 functions as a tumor suppressor in mouse skin.

Notch proteins are important in binary cell-fate decisions and inhibiting differentiation in many developmental systems, and aberrant Notch signaling is associated with tumorigenesis. The role of Notch signaling in mammalian skin is less well characterized and is mainly based on in vitro studies, which suggest that Notch signaling induces differentiation in mammalian skin. Conventional gene targeting is not applicable to establishing the role of Notch receptors or ligands in the skin because Notch1-/- embryos die during gestation. Therefore, we used a tissue-specific inducible gene-targeting approach to study the physiological role of the Notch1 receptor in the mouse epidermis and the corneal epithelium of adult mice. Unexpectedly, ablation of Notch1 results in epidermal and corneal hyperplasia followed by the development of skin tumors and facilitated chemical-induced skin carcinogenesis. Notch1 deficiency in skin and in primary keratinocytes results in increased and sustained expression of Gli2, causing the development of basal-cell carcinoma-like tumors. Furthermore, Notch1 inactivation in the epidermis results in derepressed beta-catenin signaling in cells that should normally undergo differentiation. Enhanced beta-catenin signaling can be reversed by re-introduction of a dominant active form of the Notch1 receptor. This leads to a reduction in the signaling-competent pool of beta-catenin, indicating that Notch1 can inhibit beta-catenin-mediated signaling. Our results indicate that Notch1 functions as a tumor-suppressor gene in mammalian skin.

Biochemistry and mode of action of the Bacillus sphaericus toxins

Bacillus sphaericus produces at least two toxins which are highly toxic to mosquito larvae. The binary toxin, which is comprised of proteins of 51.4 and 41.9 kDa, is present in all highly insecticidal strains. The 100 kDa SSII-1 toxin is present in most highly insecticidal as well as the weakly insecticidal strains. The current status of studies on biochemistry and mode of action of these toxins is reviewed.

Codis no lineals en Magma: noves construccions

L'objectiu principal d'aquest projecte és ampliar la llibreria BinaryCodes, iniciada al 2007, que ens permet construir i manipular codis binaris lineals i no lineals. Per aquest motiu, s'han desenvolupat una sèrie de funcions, amb els seus corresponents tests i exemples, en l'entorn de programació matemàtica Magma. Aquestes funcions consisteixen bàsicament en la construcció de nous codis a partir d'altres ja existents.

Generalized descriptive set theory and classification theory

Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.

Predictors of nonresponse in a questionnaire-based outcome study of vocational rehabilitation patients.

OBJECTIVE: To identify predictors of nonresponse to a self-report study of patients with orthopedic trauma hospitalized for vocational rehabilitation between November 15, 2003, and December 31, 2005. The role of biopsychosocial complexity, assessed using the INTERMED, was of particular interest. DESIGN: Cohort study. Questionnaires with quality of life, sociodemographic, and job-related questions were given to patients at hospitalization and 1 year after discharge. Sociodemographic data, biopsychosocial complexity, and presence of comorbidity were available at hospitalization (baseline) for all eligible patients. Logistic regression models were used to test a number of baseline variables as potential predictors of nonresponse to the questionnaires at each of the 2 time points. SETTING: Rehabilitation clinic. PARTICIPANTS: Patients (N=990) hospitalized for vocational rehabilitation over a period of 2 years. INTERVENTIONS: Not applicable. MAIN OUTCOME MEASURE: Nonresponse to the questionnaires was the binary dependent variable. RESULTS: Patients with high biopsychosocial complexity, foreign native language, or low educational level were less likely to respond at both time points. Younger patients were less likely to respond at 1 year. Those living in a stable partnership were less likely than singles to respond at hospitalization. Sex, psychiatric, and somatic comorbidity and alcoholism were never associated with nonresponse. CONCLUSIONS: We stress the importance of assessing biopsychosocial complexity to predict nonresponse. Furthermore, the factors we found to be predictive of nonresponse are also known to influence treatment outcome and vocational rehabilitation. Therefore, it is important to increase the response rate of the groups of concern in order to reduce selection bias in epidemiologic investigations.

Synchronous versus asynchronous modeling of gene regulatory networks.

MOTIVATION: In silico modeling of gene regulatory networks has gained some momentum recently due to increased interest in analyzing the dynamics of biological systems. This has been further facilitated by the increasing availability of experimental data on gene-gene, protein-protein and gene-protein interactions. The two dynamical properties that are often experimentally testable are perturbations and stable steady states. Although a lot of work has been done on the identification of steady states, not much work has been reported on in silico modeling of cellular differentiation processes. RESULTS: In this manuscript, we provide algorithms based on reduced ordered binary decision diagrams (ROBDDs) for Boolean modeling of gene regulatory networks. Algorithms for synchronous and asynchronous transition models have been proposed and their corresponding computational properties have been analyzed. These algorithms allow users to compute cyclic attractors of large networks that are currently not feasible using existing software. Hereby we provide a framework to analyze the effect of multiple gene perturbation protocols, and their effect on cell differentiation processes. These algorithms were validated on the T-helper model showing the correct steady state identification and Th1-Th2 cellular differentiation process. AVAILABILITY: The software binaries for Windows and Linux platforms can be downloaded from http://si2.epfl.ch/~garg/genysis.html.

Dynamic simulation of regulatory networks using SQUAD.

BACKGROUND: The ambition of most molecular biologists is the understanding of the intricate network of molecular interactions that control biological systems. As scientists uncover the components and the connectivity of these networks, it becomes possible to study their dynamical behavior as a whole and discover what is the specific role of each of their components. Since the behavior of a network is by no means intuitive, it becomes necessary to use computational models to understand its behavior and to be able to make predictions about it. Unfortunately, most current computational models describe small networks due to the scarcity of kinetic data available. To overcome this problem, we previously published a methodology to convert a signaling network into a dynamical system, even in the total absence of kinetic information. In this paper we present a software implementation of such methodology. RESULTS: We developed SQUAD, a software for the dynamic simulation of signaling networks using the standardized qualitative dynamical systems approach. SQUAD converts the network into a discrete dynamical system, and it uses a binary decision diagram algorithm to identify all the steady states of the system. Then, the software creates a continuous dynamical system and localizes its steady states which are located near the steady states of the discrete system. The software permits to make simulations on the continuous system, allowing for the modification of several parameters. Importantly, SQUAD includes a framework for perturbing networks in a manner similar to what is performed in experimental laboratory protocols, for example by activating receptors or knocking out molecular components. Using this software we have been able to successfully reproduce the behavior of the regulatory network implicated in T-helper cell differentiation. CONCLUSION: The simulation of regulatory networks aims at predicting the behavior of a whole system when subject to stimuli, such as drugs, or determine the role of specific components within the network. The predictions can then be used to interpret and/or drive laboratory experiments. SQUAD provides a user-friendly graphical interface, accessible to both computational and experimental biologists for the fast qualitative simulation of large regulatory networks for which kinetic data is not necessarily available.

Renal Services Review 2002 - Consultation Covering Letter (PDF 55 KB)

Automatically imported binary.

Expression of mosquito active toxin genes by a Colombian native strain of the gram-negative bacterium Asticcacaulis excentricus

Mosquito control with biological insecticides, such as Bacillus sp. toxins, has been used widely in many countries. However, rapid sedimentation away from the mosquito larvae feeding zone causes a low residual effect. In order to overcome this problem, it has been proposed to clone the Bacillus toxin genes in aquatic bacteria which are able to live in the upper part of the water column. Two strains of Asticcacaulis excentricus were chosen to introduce the B. sphaericus binary toxin gene and B. thuringiensis subsp. medellin cry11Bb gene cloned in suitable vectors. In feeding experiments with these aquatic bacteria, it was shown that Culex quinquefasciatus, Aedes aegypti, and Anopheles albimanus larvae were able to survive on a diet based on this wild bacterium. A. excentricus recombinant strains were able to express both genes, but the recombinant strain expressing the B. sphaericus binary toxin was toxic to mosquito larvae. Crude protease A. excentricus extracts did not degrade the Cry11Bb toxin. The flotability studies indicated that the recombinant A. excentricus strains remained in the upper part of the water column longer than the wild type Bacillus strains.

Emissió ràdio a baixa freqüència en fenòmens eruptius i en fonts esteses de raigs gamma d'alta i molt alta energia

La tasca investigadora presentada en aquesta memòria s'ha centrat en les fonts galàctiques de raigs gamma de molt alta energia LS I +61 303, HESS J1708-410 i HESS J1858+020. La primera és una binària de raigs gamma molt estudiada, formada per una estrella massiva i un objecte compacte. S'ha proposat un escenari on l'objecte compacte seria un púlsar jove, i la interacció del seu vent amb el vent de l'estrella generaria els raigs gamma. De totes formes, no s'ha detectat polsos procedents d'aquest putatiu púlsar. L'investigador va realitzar observacions en fase a 1280 MHz amb el radiotelescopi GMRT, sense trobar-hi polsos, cosa que implica un estricte límit superior de 0,38 mJy a la densitat mitjana de flux polsat en un putatiu púlsar amb un període major que 2 mil•lisegons en el sistema binari LS I +61 303. Per altra banda, HESS J1708-410 i HESS J1858+020 són dues fonts esteses de raigs gamma de molt alta energia de les quals no es coneix cap contrapart a d'altres longituds d'ona. L'investigador les va observar amb el GMRT, quatre vegades HESS J1708-410 (dues a 610 MHz i dues a 1400 MHz) i dues vegades HESS J1858+020 (una a cada freqüència). En les imatges realitzades amb aquestes dades no hi ha emissió estesa coincident amb les regions d'emissió de raigs gamma. HESS J1858+020 se solapa parcialment amb una font estesa que podria ser un SNR. De confirmar-se la falta de contrapartida ràdio de HESS J1708-410, estaríem parlant d'un accelerador hadrònic extraordinàriament eficient, d'una classe desconeguda fins ara.

Basic biology of Pneumocystis carinii: a mini review

Basic aspects of cell biology of Pneumocystis carinii are reviewed with major emphasis on its life cycle and the structural organization of the trophozoites and cyst forms. Initially considered as a protozoan it is now established that Pneumocystis belongs to the Fungi Kingdom. Its life cycle includes two basic forms: (a) trophozoites, which are haploid cells that divide by binary fission and may conjugate with each other forming an early procyst and (b) cysts where division takes place through a meiotic process with the formation of eight nuclei followed by cytoplasmic delimitation and formation of intracystic bodies which are subsequently released and transformed into trophozoites. Basic aspects of the structure of the two developmental stages of P. carinii are reviewed.

Estructura de datos avanzadas : clases disjuntas, montículos, árboles de búsqueda

En aquest treball s'amplia la implementació en Java de les estructures de dades iniciada per Esteve Mariné, utilitzant el seu disseny bàsic. Concretament, s'ha fet la programació de les estructures de a) classes disjuntes, utilitzant els algorismes de llistes encadenades i amb estructura d'arbre, b) monticles, amb els algorismes binari, binomial i de Fibonacci, i c) arbres de recerca basats en l'algorisme d'arbre binari vermell-negre, el qual complementa els dos ja existents amb algorismes d'encadenaments i AVL. Per a examinar l'evolució de les estructures, s'ha preparat un visualitzador gràfic interactiu amb l'usuari que permet fer les operacions bàsiques de l'estructura. Amb aquest entorn és possible desar les estructures, tornar a reproduir-les i desfer i tornar a repetir les operacions fetes sobre l'estructura. Finalment, aporta una metodologia, amb visualització mitjançant gràfics, de l'avaluació comparativa dels algorismes implementats, que permet modificar els paràmetres d'avaluació com ara nombre d'elements que s'han de tractar, algorismes que s'han de comparar i nombre de repeticions. Les dades obtingudes es poden exportar per a analitzar-les posteriorment.

Measuring an effect size from dichotomized data : contrasted results whether using a correlation or an odds-ratio

It is well known that dichotomizing continuous data has the effect to decrease statistical power when the goal is to test for a statistical association between two variables. Modern researchers however are focusing not only on statistical significance but also on an estimation of the "effect size" (i.e., the strength of association between the variables) to judge whether a significant association is also clinically relevant. In this article, we are interested in the consequences of dichotomizing continuous data on the value of an effect size in some classical settings. It turns out that the conclusions will not be the same whether using a correlation or an odds ratio to summarize the strength of association between the variables: Whereas the value of a correlation is typically decreased by a factor pi/2 after each dichotomization, the value of an odds ratio is at the same time raised to the power 2. From a descriptive statistical point of view, it is thus not clear whether dichotomizing continuous data leads to a decrease or to an increase in the effect size, as illustrated using a data set to investigate the relationship between motor and intellectual functions in children and adolescents