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.

Identification of CDH1 germline missense mutations associated with functional inactivation of the E-cadherin protein in young gastric cancer probands

E-cadherin is involved in the formation of cell-junctions and the maintenance of epithelial integrity. Direct evidence of E-cadherin mutations triggering tumorigenesis has come from the finding of inactivating germline mutations of the gene (CDH1) in hereditary diffuse gastric cancer (HDGC). We screened a series of 66 young gastric cancer probands for germline CDH1 mutations, and two novel missense alterations together with an intronic variant were identified. We then analysed the functional significance of the exonic missense variants found here as well as a third germline missense variant that we previously identified in a HGDC family. cDNAs encoding either the wild-type protein or mutant forms of E-cadherin were stably transfected into CHO (Chinese hamster ovary) E-cadherin-negative cells. Transfected cell-lines were characterized in terms of aggregation, motility and invasion. We show that a proportion of apparently sporadic early-onset diffuse gastric carcinomas are associated with germline alterations of the E-cadherin gene. We also demonstrate that a proportion of missense variants are associated with significant functional consequences, suggesting that our cell model can be used as an adjunct in deciding on the potential pathogenic role of identified E-cadherin germline alterations.

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.