| 1. |
- Arrighi, Emmanuel, et al.
(författare)
-
Order Reconfiguration under Width Constraints
- 2023
-
Ingår i: Journal of Graph Algorithms and Applications. - 1526-1719. ; 27:6, s. 409-431
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω′ of the vertices of G, can one transform ω into ω′ by a sequence of swaps of adjacent elements in such a way that, at each time step, the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω′ have cutwidth (pathwidth) of at most k/2. This result also holds in a weighted setting. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.
|
|
| 2. |
- Arrighi, Emmanuel, et al.
(författare)
-
Synchronization and Diversity of Solutions
- 2023
-
Ingår i: Thirty-Seventh AAAI Conference on Artificial Intelligence. - 9781577358800 ; , s. 11516-11524
-
Konferensbidrag (refereegranskat)abstract
- A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.
|
|
| 3. |
- Beelen, Rob, et al.
(författare)
-
Effects of long-term exposure to air pollution on natural-cause mortality : an analysis of 22 European cohorts within the multicentre ESCAPE project
- 2014
-
Ingår i: The Lancet. - : Elsevier. - 0140-6736 .- 1474-547X. ; 383:9919, s. 785-795
-
Tidskriftsartikel (refereegranskat)abstract
- Background Few studies on long-term exposure to air pollution and mortality have been reported from Europe. Within the multicentre European Study of Cohorts for Air Pollution Effects (ESCAPE), we aimed to investigate the association between natural-cause mortality and long-term exposure to several air pollutants. Methods We used data from 22 European cohort studies, which created a total study population of 367 251 participants. All cohorts were general population samples, although some were restricted to one sex only. With a strictly standardised protocol, we assessed residential exposure to air pollutants as annual average concentrations of particulate matter (PM) with diameters of less than 2.5 mu m (PM2.5), less than 10 mu m (PM10), and between 10 mu m and 2.5 mu m (PMcoarse), PM2.5 absorbance, and annual average concentrations of nitrogen oxides (NO2 and NOx), with land use regression models. We also investigated two traffic intensity variables-traffic intensity on the nearest road (vehicles per day) and total traffic load on all major roads within a 100 m buff er. We did cohort-specific statistical analyses using confounder models with increasing adjustment for confounder variables, and Cox proportional hazards models with a common protocol. We obtained pooled effect estimates through a random-effects meta-analysis. Findings The total study population consisted of 367 251 participants who contributed 5 118 039 person-years at risk (average follow-up 13.9 years), of whom 29 076 died from a natural cause during follow-up. A significantly increased hazard ratio (HR) for PM2.5 of 1.07 (95% CI 1.02-1.13) per 5 mu g/m(3) was recorded. No heterogeneity was noted between individual cohort effect estimates (I-2 p value=0.95). HRs for PM2.5 remained significantly raised even when we included only participants exposed to pollutant concentrations lower than the European annual mean limit value of 25 mu g/m(3) (HR 1.06, 95% CI 1.00-1.12) or below 20 mu g/m(3) (1.07, 1.01-1.13). Interpretation Long-term exposure to fine particulate air pollution was associated with natural-cause mortality, even within concentration ranges well below the present European annual mean limit value.
|
|
| 4. |
- Beelen, Rob, et al.
(författare)
-
Natural-Cause Mortality and Long-Term Exposure to Particle Components : An Analysis of 19 European Cohorts within the Multi-Center ESCAPE Project
- 2015
-
Ingår i: Journal of Environmental Health Perspectives. - : Environmental Health Perspectives. - 0091-6765 .- 1552-9924. ; 123:6, s. 525-533
-
Forskningsöversikt (refereegranskat)abstract
- Background: Studies have shown associations between mortality and long-term exposure to particulate matter air pollution. Few cohort studies have estimated the effects of the elemental composition of particulate matter on mortality. Objectives: Our aim was to study the association between natural-cause mortality and long-term exposure to elemental components of particulate matter. Methods: Mortality and confounder data from 19 European cohort studies were used. Residential exposure to eight a priori-selected components of particulate matter ( PM) was characterized following a strictly standardized protocol. Annual average concentrations of copper, iron, potassium, nickel, sulfur, silicon, vanadium, and zinc within PM size fractions <= 2.5 mu m (PM2.5) and <= 10 mu m (PM10) were estimated using land-use regression models. Cohort-specific statistical analyses of the associations between mortality and air pollution were conducted using Cox proportional hazards models using a common protocol followed by meta-analysis. Results: The total study population consisted of 291,816 participants, of whom 25,466 died from a natural cause during follow-up (average time of follow-up, 14.3 years). Hazard ratios were positive for almost all elements and statistically significant for PM2.5 sulfur (1.14; 95% CI: 1.06, 1.23 per 200ng/m(3)). In a two-pollutant model, the association with PM2.5 sulfur was robust to adjustment for PM2.5 mass, whereas the association with PM2.5 mass was reduced. Conclusions: Long-term exposure to PM2.5 sulfur was associated with natural-cause mortality. This association was robust to adjustment for other pollutants and PM2.5.
|
|
| 5. |
- Boehme, Katja, et al.
(författare)
-
Concerted Actions of a Thermo-labile Regulator and a Unique Intergenic RNA Thermosensor Control Yersinia Virulence
- 2012
-
Ingår i: PLOS PATHOGENS. - : Public Library of Science (PLoS). - 1553-7366 .- 1553-7374. ; 8:2, s. e1002518-
-
Tidskriftsartikel (refereegranskat)abstract
- Expression of all Yersinia pathogenicity factors encoded on the virulence plasmid, including the yop effector and the ysc type III secretion genes, is controlled by the transcriptional activator LcrF in response to temperature. Here, we show that a protein-and RNA-dependent hierarchy of thermosensors induce LcrF synthesis at body temperature. Thermally regulated transcription of lcrF is modest and mediated by the thermo-sensitive modulator YmoA, which represses transcription from a single promoter located far upstream of the yscW-lcrF operon at moderate temperatures. The transcriptional response is complemented by a second layer of temperature-control induced by a unique cis-acting RNA element located within the intergenic region of the yscW-lcrF transcript. Structure probing demonstrated that this region forms a secondary structure composed of two stemloops at 25 degrees C. The second hairpin sequesters the lcrF ribosomal binding site by a stretch of four uracils. Opening of this structure was favored at 37 degrees C and permitted ribosome binding at host body temperature. Our study further provides experimental evidence for the biological relevance of an RNA thermometer in an animal model. Following oral infections in mice, we found that two different Y. pseudotuberculosis patient isolates expressing a stabilized thermometer variant were strongly reduced in their ability to disseminate into the Peyer's patches, liver and spleen and have fully lost their lethality. Intriguingly, Yersinia strains with a destabilized version of the thermosensor were attenuated or exhibited a similar, but not a higher mortality. This illustrates that the RNA thermometer is the decisive control element providing just the appropriate amounts of LcrF protein for optimal infection efficiency.
|
|
| 6. |
|
|
| 7. |
- Edqvist, Petra, et al.
(författare)
-
YscP and YscU Regulate Substrate Specificity of the Yersinia Type III Secretion System
- 2003
-
Ingår i: Journal of Bacteriology. - : American Society for Microbiology. - 0021-9193 .- 1098-5530. ; 185:7, s. 2259-2266
-
Tidskriftsartikel (refereegranskat)abstract
- Pathogenic Yersinia species use a type III secretion system to inhibit phagocytosis by eukaryotic cells. At 37 degrees C, the secretion system is assembled, forming a needle-like structure on the bacterial cell surface. Upon eukaryotic cell contact, six effector proteins, called Yops, are translocated into the eukaryotic cell cytosol. Here, we show that a yscP mutant exports an increased amount of the needle component YscF to the bacterial cell surface but is unable to efficiently secrete effector Yops. Mutations in the cytoplasmic domain of the inner membrane protein YscU suppress the yscP phenotype by reducing the level of YscF secretion and increasing the level of Yop secretion. These results suggest that YscP and YscU coordinately regulate the substrate specificity of the Yersinia type III secretion system. Furthermore, we show that YscP and YscU act upstream of the cell contact sensor YopN as well as the inner gatekeeper LcrG in the pathway of substrate export regulation. These results further strengthen the strong evolutionary link between flagellar biosynthesis and type III synthesis.
|
|
| 8. |
- Fattinger, Stefan A., et al.
(författare)
-
Epithelium-autonomous NAIP/NLRC4 prevents TNF-driven inflammatory destruction of the gut epithelial barrier in Salmonella-infected mice
- 2021
-
Ingår i: Mucosal Immunology. - : Springer Nature. - 1933-0219 .- 1935-3456. ; 14:3, s. 615-629
-
Tidskriftsartikel (refereegranskat)abstract
- The gut epithelium is a critical protective barrier. Its NAIP/NLRC4 inflammasome senses infection by Gram-negative bacteria, including Salmonella Typhimurium (S.Tm) and promotes expulsion of infected enterocytes. During the first ~12–24 h, this reduces mucosal S.Tm loads at the price of moderate enteropathy. It remained unknown how this NAIP/NLRC4-dependent tradeoff would develop during subsequent infection stages. In NAIP/NLRC4-deficient mice, S.Tm elicited severe enteropathy within 72 h, characterized by elevated mucosal TNF (>20 pg/mg) production from bone marrow-derived cells, reduced regeneration, excessive enterocyte loss, and a collapse of the epithelial barrier. TNF-depleting antibodies prevented this destructive pathology. In hosts proficient for epithelial NAIP/NLRC4, a heterogeneous enterocyte death response with both apoptotic and pyroptotic features kept S.Tm loads persistently in check, thereby preventing this dire outcome altogether. Our results demonstrate that immediate and selective removal of infected enterocytes, by locally acting epithelium-autonomous NAIP/NLRC4, is required to avoid a TNF-driven inflammatory hyper-reaction that otherwise destroys the epithelial barrier.
|
|
| 9. |
- Fattinger, Stefan A., et al.
(författare)
-
Gasdermin D is the only Gasdermin that provides protection against acute Salmonella gut infection in mice
- 2023
-
Ingår i: Proceedings of the National Academy of Sciences of the United States of America. - : Proceedings of the National Academy of Sciences (PNAS). - 0027-8424 .- 1091-6490. ; 120:48
-
Tidskriftsartikel (refereegranskat)abstract
- Gasdermins (GSDMs) share a common functional domain structure and are best known for their capacity to form membrane pores. These pores are hallmarks of a specific form of cell death called pyroptosis and mediate the secretion of pro-inflammatory cytokines such as interleukin 1 ss (IL1 ss) and interleukin 18 (IL18). Thereby, Gasdermins have been implicated in various immune responses against cancer and infectious diseases such as acute Salmonella Typhimurium (S.Tm) gut infection. However, to date, we lack a comprehensive functional assessment of the different Gasdermins (GSDMA-E) during S.Tm infection in vivo. Here, we used epithelium-specific ablation, bone marrow chimeras, and mouse lines lacking individual Gasdermins, combinations of Gasdermins or even all Gasdermins (GSDMA1-3C1- 4DE) at once and performed littermate-controlled oral S.Tm infections in streptomycin-pretreated mice to investigate the impact of all murine Gasdermins. While GSDMA, C, and E appear dispensable, we show that GSDMD i) restricts S.Tm loads in the gut tissue and systemic organs, ii) controls gut inflammation kinetics, and iii) prevents epithelium disruption by 72 h of the infection. Full protection requires GSDMD expression by both bone-marrow- derived lamina propria cells and intestinal epithelial cells (IECs). In vivo experiments as well as 3D-, 2D-, and chimeric enteroid infections further show that infected IEC extrusion proceeds also without GSDMD, but that GSDMD controls the permeabilization and morphology of the extruding IECs, affects extrusion kinetics, and promotes overall mucosal barrier capacity. As such, this work identifies a unique multipronged role of GSDMD among the Gasdermins for mucosal tissue defense against a common enteric pathogen.
|
|
| 10. |
|
|
