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.

ERM transactivation is up-regulated by the repression of DNA binding after the PKA phosphorylation of a consensus site at the edge of the ETS domain

The final step of the transduction pathway is the activation of gene transcription, which is driven by kinase cascades leading to changes in the activity of many transcription factors. Among these latter, PEA3/E1AF, ER81/ETV1, and ERM, members of the well conserved PEA3 group from the Ets family are involved in these processes. We show here that protein kinase A (PKA) increases the transcriptional activity of human ERM and human ETV1, through a Ser residue situated at the edge of the ETS DNA-binding domain. PKA phosphorylation does not directly affect the ERM transactivation domains but does affect DNA binding activity. Unphosphorylated wild-type ERM bound DNA avidly, whereas after PKA phosphorylation it did so very weakly. Interestingly, S367A mutation significantly reduced the ERM-mediated transcription in the presence of the kinase, and the DNA binding of this mutant, although similar to that of unphosphorylated wild-type protein, was insensitive to PKA treatment. Mutations, which may mimic a phosphorylated serine, converted ERM from an efficient DNA-binding protein to a poor DNA binding one, with inefficiency of PKA phosphorylation. The present data clearly demonstrate a close correlation between the capacity of PKA to increase the transactivation of ERM and the drastic down-regulation of the binding of the ETS domain to the targeted DNA. What we thus demonstrate here is a relatively rare transcription activation mechanism through a decrease in DNA binding, probably by the shift of a non-active form of an Ets protein to a PKA-phosphorylated active one, which should be in a conformation permitting a transactivation domain to be active.

15N NMR relaxation data reveal significant chemical exchange broadening in the alpha-domain of human α-lactalbumin

Human alpha-lactalbumin (alpha-LA), a 123-residue calcium-binding protein, has been studied using (15)N NMR relaxation methods in order to characterize backbone dynamics of the native state at the level of individual residues. Relaxation data were collected at three magnetic field strengths and analyzed using the model-free formalism of Lipari and Szabo. The order parameters derived from this analysis are generally high, indicating a rigid backbone. A total of 46 residues required an exchange contribution to T(2); 43 of these residues are located in the alpha-domain of the protein. The largest exchange contributions are observed in the A-, B-, D-, and C-terminal 3(10)-helices of the alpha-domain; these residues have been shown previously to form a highly stable core in the alpha-LA molten globule. The observed exchange broadening, along with previous hydrogen/deuterium amide exchange data, suggests that this part of the alpha-domain may undergo a local structural transition between the well-ordered native structure and a less-ordered molten-globule-like structure.

Toward understanding the essence of post-translational modifications for the Mycobacterium tuberculosis immunoproteome

CD4⁺ T cells are prominent effector cells in controlling Mycobacterium tuberculosis (Mtb) infection but may also contribute to immunopathology. Studies probing the CD4⁺ T cell response from individuals latently infected with Mtb or patients with active tuberculosis using either small or proteome-wide antigen screens so far revealed a multi-antigenic, yet mostly invariable repertoire of immunogenic Mtb proteins. Recent developments in mass spectrometry-based proteomics have highlighted the occurrence of numerous types of post-translational modifications (PTMs) in proteomes of prokaryotes, including Mtb. The well-known PTMs in Mtb are glycosylation, lipidation, or phosphorylation, known regulators of protein function or compartmentalization. Other PTMs include methylation, acetylation, and pupylation, involved in protein stability. While all PTMs add variability to the Mtb proteome, relatively little is understood about their role in the anti-Mtb immune responses. Here,we reviewMtb protein PTMs and methods to assess their role in protective immunity against Mtb. © 2014 van Els, Corbière, Smits, vanGaans-van den Brink, Poelen, Mascart, Meiring and Locht.