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.

Intrastereomic proteins from the asteroid Asterias rubens. separation, partial characterization ,and interactions with growing calcite crystals

info:eu-repo/semantics/published

Immunological Signatures Identifying Different Stages of Latent Mycobacterium tuberculosis Infection and Discriminating Latent from Active Tuberculosis in Humans

Objectives: One third of the world population is considered latently infected with Mycobacterium tuberculosis(LTBI) and sterilizing this reservoir of bacteria that may reactivate is required for tuberculosis (TB) elimination. Thegroup of individuals with LTBI is heterogeneous with some of them being more at risk to develop TB disease thanothers. Improved diagnosis of subjects with LTBI is needed, allowing to differentiate subjects with LTBI from thosewith active TB, and to select among LTBI subjects those who are more at risk to develop active TB. We havecharacterized at the cellular level both the quantitative and qualitative T cell responses to different mycobacterialantigens in selected populations of infected subjects in order to identify new biomarkers that could help to identify M.tuberculosis-infected subjects and to stratify them in risk groups for reactivation of the infection.Methods: Lymphoblast frequencies and cytokine production (IFN-γ, TNF-α, IL-2) among CD4+ and CD8+ T cellswere analyzed by flow cytometry after in vitro stimulation with the latency antigen heparin-binding haemagglutinin(HBHA) or early-secreted antigen Target-6 (ESAT-6) of peripheral blood mononuclear cells from clinically wellcharacterized M. tuberculosis-infected humans (28 LTBI, 22 TB disease,12 controls). The LTBI group definedaccording to the Center for Disease Control guidelines was subdivided into QuantiFERON-TB Gold in-Tube (QFT)positive and negative subgroups.Results: Similar to TB patients, QFT+ LTBI subjects had higher proportions of HBHA-induced TNF-αsingle+ CD4+lymphocytes than QFT- LTBI subjects (p<0.05). Compared to LTBI subjects, TB patients had higher frequencies ofESAT-6-induced CD8+ lymphoblasts (p<0.001), higher proportions of ESAT-6-induced IFN-γ+TNF-α+ CD4+ Tlymphocytes (p<0.05), and lower proportions of HBHA-induced IFN-γ+TNF-α+IL-2+ (p<0.05) CD4+ T lymphocytes.Conclusions: These data provide new biomarkers to discriminate active TB from LTBI, and more interestingly,help to identify LTBI subjects with increased likelihood to develop TB disease.

Covering Partial Cubes with Zones

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p31