Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

Physiological levels of PTEN control the size of the cellular Ins(1,3,4,5,6)P5 pool

To understand how a signaling molecule's activities are regulated, we need insight into the processes controlling the dynamic balance between its synthesis and degradation. For the Ins(1,3,4,5,6)P5 signal, this information is woefully inadequate. For example, the only known cytosolic enzyme with the capacity to degrade Ins(1,3,4,5,6)P5 is the tumour-suppressor PTEN [J.J. Caffrey, T. Darden, M.R. Wenk, S.B. Shears, FEBS Lett. 499 (2001) 6 ], but the biological relevance has been questioned by others [E.A. Orchiston, D. Bennett, N.R. Leslie, R.G. Clarke, L. Winward, C.P. Downes, S.T. Safrany, J. Biol. Chem. 279 (2004) 1116 ]. The current study emphasizes the role of physiological levels of PTEN in Ins(1,3,4,5,6)P5 homeostasis. We employed two cell models. First, we used a human U87MG glioblastoma PTEN-null cell line that hosts an ecdysone-inducible PTEN expression system. Second, the human H1299 bronchial cell line, in which PTEN is hypomorphic due to promoter methylation, has been stably transfected with physiologically relevant levels of PTEN. In both models, a novel consequence of PTEN expression was to increase Ins(1,3,4,5,6)P5 pool size by 30-40% (p<0.01); this response was wortmannin-insensitive and, therefore, independent of the PtdIns 3-kinase pathway. In U87MG cells, induction of the G129R catalytically inactive PTEN mutant did not affect Ins(1,3,4,5,6)P(5) levels. PTEN induction did not alter the expression of enzymes participating in Ins(1,3,4,5,6)P5 synthesis. Another effect of PTEN expression in U87MG cells was to decrease InsP6 levels by 13% (p<0.02). The InsP6-phosphatase, MIPP, may be responsible for the latter effect; we show that recombinant human MIPP dephosphorylates InsP6 to D/L-Ins(1,2,4,5,6)P5, levels of which increased 60% (p<0.05) following PTEN expression in U87MG cells. Overall, our data add higher inositol phosphates to the list of important cellular regulators [Y. Huang, R.P. Wernyj, D.D. Norton, P. Precht, M.C. Seminario, R.L. Wange, Oncogene, 24 (2005) 3819 ] the levels of which are modulated by expression of the highly pleiotropic PTEN protein.

Pathogenicity of Salmonella: SopE-mediated membrane ruffling is independent of inositol phosphate signals

Studies [Zhou, D. Chen, L.-M. Hernandez, L. Shears, S.B. and Galán, J.E. (2001) A Salmonella inositol polyphosphatase acts in conjunction with other bacterial effectors to promote host-cell actin cytoskeleton rearrangements and bacterial internalization. Mol. Microbiol. 39, 248-259] with engineered Salmonella mutants showed that deletion of SopE attenuated the pathogen's ability to deplete host-cell InsP5 and remodel the cytoskeleton. We pursued these observations: In SopE-transfected host-cells, membrane ruffling was induced, but SopE did not dephosphorylate InsP5, nor did it recruit PTEN (a cytosolic InsP5 phosphatase) for this task. However, PTEN strengthened SopE-mediated membrane ruffling. We conclude SopE promotes host-cell InsP5 hydrolysis only with the assistance of other Salmonella proteins. Our demonstration that Salmonella-mediated cytoskeletal modifications are independent of inositolphosphates will focus future studies on elucidating alternate pathogenic consequences of InsP5 metabolism, including ion channel conductance and apoptosis.

Monitoring SO2 emission at the Soufriere Hills Volcano: implications for changes in eruptive conditions

info:eu-repo/semantics/published