Multiple regulatory inputs including cell envelope stress orchestrate expression of the Escherichia coli rpoN operon.

The rpoN operon, an important regulatory hub in Enterobacteriaceae, includes rpoN encoding sigma factor σ54, hpf involved in ribosome hibernation, rapZ regulating glucosamine-6-phosphate levels, and two genes encoding proteins of the nitrogen-related phosphotransferase system. Little is known about regulatory mechanisms controlling the abundance of these proteins. This study employs transposon mutagenesis and chemical screens to dissect the complex expression of the rpoN operon. We find that envelope stress conditions trigger read-through transcription into the rpoN operon from a promoter located upstream of the preceding lptA-lptB locus. This promoter is controlled by the envelope stress sigma factor E and response regulator PhoP is required for its full response to a subset of stress signals. σE also stimulates ptsN-rapZ-npr expression using an element downstream of rpoN, presumably by interfering with mRNA processing by RNase E. Additionally, we identify a novel promoter in the 3' end of rpoN that directs transcription of the distal genes in response to ethanol. Finally, we show that translation of hpf and ptsN is individually regulated by the RNA chaperone Hfq, perhaps involving small RNAs. Collectively, our work demonstrates that the rpoN operon is subject to complex regulation, integrating signals related to envelope stress and carbon source quality.

Designing RNA Secondary Structures Is Hard.

A ribonucleic acid (RNA) sequence is a word over an alphabet on four elements [Formula: see text] called bases. RNA sequences fold into secondary structures where some bases pair with one another, while others remain unpaired. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some models of energy and to design sequences of bases that will fold into targeted secondary structures. Predicting how a given RNA sequence folds into a pseudoknot-free secondary structure is known to be solvable in cubic time since the eighties and in truly subcubic time by a recent result of Bringmann et al. (FOCS, 2016), whereas Lyngsø has shown it is computationally hard if pseudoknots are allowed (ICALP, 2004). As a stark contrast, it is unknown whether or not designing a given RNA secondary structure is a tractable task; this has been raised as a challenging open question by Condon (ICALP, 2003). Because of its crucial importance in a number of fields such as pharmaceutical research and biochemistry, there are dozens of heuristics and software libraries dedicated to the RNA secondary structure design. It is therefore rather surprising that the computational complexity of this central problem in bioinformatics has been unsettled for decades. In this article, we show that in the simplest model of energy, which is the Watson-Crick model, the design of secondary structures is computationally hard if one adds natural constraints of the form: indexiof the sequence has to be labeled by baseb. This negative result suggests that the same lower bound holds for more realistic models of energy. It is noteworthy that the additional constraints are by no means artificial: they are provided by all the RNA design pieces of software and they do correspond to the actual practice (e.g., the instances of the EteRNA project).

Querying graphs in protein-protein interactions networks using feedback vertex set.

Recent techniques increase rapidly the amount of our knowledge on interactions between proteins. The interpretation of these new information depends on our ability to retrieve known substructures in the data, the Protein-Protein Interactions (PPIs) networks. In an algorithmic point of view, it is an hard task since it often leads to NP-hard problems. To overcome this difficulty, many authors have provided tools for querying patterns with a restricted topology, i.e., paths or trees in PPI networks. Such restriction leads to the development of fixed parameter tractable (FPT) algorithms, which can be practicable for restricted sizes of queries. Unfortunately, Graph Homomorphism is a W[1]-hard problem, and hence, no FPT algorithm can be found when patterns are in the shape of general graphs. However, Dost et al. gave an algorithm (which is not implemented) to query graphs with a bounded treewidth in PPI networks (the treewidth of the query being involved in the time complexity). In this paper, we propose another algorithm for querying pattern in the shape of graphs, also based on dynamic programming and the color-coding technique. To transform graphs queries into trees without loss of informations, we use feedback vertex set coupled to a node duplication mechanism. Hence, our algorithm is FPT for querying graphs with a bounded size of their feedback vertex set. It gives an alternative to the treewidth parameter, which can be better or worst for a given query. We provide a python implementation which allows us to validate our implementation on real data. Especially, we retrieve some human queries in the shape of graphs into the fly PPI network.