3-way networks: application of hypergraphs for modelling increased complexity in comparative genomics.
Ontology highlight
ABSTRACT:
SUBMITTER: Weighill DA
PROVIDER: S-EPMC4376783 | biostudies-literature | 2015 Mar
REPOSITORIES: biostudies-literature
Publications
3-way networks: application of hypergraphs for modelling increased complexity in comparative genomics.
Weighill Deborah A DA Jacobson Daniel A DA
PLoS computational biology 20150327 3
We present and develop the theory of 3-way networks, a type of hypergraph in which each edge models relationships between triplets of objects as opposed to pairs of objects as done by standard network models. We explore approaches of how to prune these 3-way networks, illustrate their utility in comparative genomics and demonstrate how they find relationships which would be missed by standard 2-way network models using a phylogenomic dataset of 211 bacterial genomes. ...[more]
Similar Datasets
Project description:BackgroundComparative genomics methods enable the reconstruction of bacterial regulatory networks using available experimental data. In spite of their potential for accelerating research into the composition and evolution of bacterial regulons, few comparative genomics suites have been developed for the automated analysis of these regulatory systems. Available solutions typically rely on precomputed databases for operon and ortholog predictions, limiting the scope of analyses to processed complete genomes, and several key issues such as the transfer of experimental information or the integration of regulatory information in a probabilistic setting remain largely unaddressed.ResultsHere we introduce CGB, a flexible platform for comparative genomics of prokaryotic regulons. CGB has few external dependencies and enables fully customized analyses of newly available genome data. The platform automates the merging of experimental information and uses a gene-centered, Bayesian framework to generate and integrate easily interpretable results. We demonstrate its flexibility and power by analyzing the evolution of type III secretion system regulation in pathogenic Proteobacteria and by characterizing the SOS regulon of a new bacterial phylum, the Balneolaeota.ConclusionsOur results demonstrate the applicability of the CGB pipeline in multiple settings. CGB's ability to automatically integrate experimental information from multiple sources and use complete and draft genomic data, coupled with its non-reliance on precomputed databases and its easily interpretable display of gene-centered posterior probabilities of regulation provide users with an unprecedented level of flexibility in launching comparative genomics analyses of prokaryotic transcriptional regulatory networks. The analyses of type III secretion and SOS response regulatory networks illustrate instances of convergent and divergent evolution of these regulatory systems, showcasing the power of formal ancestral state reconstruction at inferring the evolutionary history of regulatory networks.
| S-EPMC7739468 | biostudies-literature
Project description:The assumption of basic properties, like self-regulation, in simple transcriptional regulatory networks can be exploited to infer regulatory motifs from the growing amounts of genomic and meta-genomic data. These motifs can in principle be used to elucidate the nature and scope of transcriptional networks through comparative genomics. Here we assess the feasibility of this approach using the SOS regulatory network of Gram-positive bacteria as a test case. Using experimentally validated data, we show that the known regulatory motif can be inferred through the assumption of self-regulation. Furthermore, the inferred motif provides a more robust search pattern for comparative genomics than the experimental motifs defined in reference organisms. We take advantage of this robustness to generate a functional map of the SOS response in Gram-positive bacteria. Our results reveal definite differences in the composition of the LexA regulon between Firmicutes and Actinobacteria, and confirm that regulation of cell-division inhibition is a widespread characteristic of this network among Gram-positive bacteria.
| S-EPMC3422134 | biostudies-literature
Project description:Members of the genus Bifidobacterium are common inhabitants of the human gastrointestinal tract. Previously it was shown that arabino-oligosaccharides (AOS) might act as prebiotics and stimulate the bifidobacterial growth in the gut. However, despite the rapid accumulation of genomic data, the precise mechanisms by which these sugars are utilized and associated transcription control still remain unclear. In the current study, we used a comparative genomic approach to reconstruct arabinose and AOS utilization pathways in over 40 bacterial species belonging to the Bifidobacteriaceae family. The results indicate that the gene repertoire involved in the catabolism of these sugars is highly diverse, and even phylogenetically close species may differ in their utilization capabilities. Using bioinformatics analysis we identified potential DNA-binding motifs and reconstructed putative regulons for the arabinose and AOS utilization genes in the Bifidobacteriaceae genomes. Six LacI-family transcriptional factors (named AbfR, AauR, AauU1, AauU2, BauR1 and BauR2) and a TetR-family regulator (XsaR) presumably act as local repressors for AOS utilization genes encoding various α- or β-L-arabinofuranosidases and predicted AOS transporters. The ROK-family regulator AraU and the LacI-family regulator AraQ control adjacent operons encoding putative arabinose transporters and catabolic enzymes, respectively. However, the AraQ regulator is universally present in all Bifidobacterium species including those lacking the arabinose catabolic genes araBDA, suggesting its control of other genes. Comparative genomic analyses of prospective AraQ-binding sites allowed the reconstruction of AraQ regulons and a proposed binary repression/activation mechanism. The conserved core of reconstructed AraQ regulons in bifidobacteria includes araBDA, as well as genes from the central glycolytic and fermentation pathways (pyk, eno, gap, tkt, tal, galM, ldh). The current study expands the range of genes involved in bifidobacterial arabinose/AOS utilization and demonstrates considerable variations in associated metabolic pathways and regulons. Detailed comparative and phylogenetic analyses allowed us to hypothesize how the identified reconstructed regulons evolved in bifidobacteria. Our findings may help to improve carbohydrate catabolic phenotype prediction and metabolic modeling, while it may also facilitate rational development of novel prebiotics.
| S-EPMC5928203 | biostudies-literature
Project description:Parasitism is a major ecological niche for a variety of nematodes. Multiple nematode lineages have specialized as pathogens, including deadly parasites of insects that are used in biological control. We have sequenced and analyzed the draft genomes and transcriptomes of the entomopathogenic nematode Steinernema carpocapsae and four congeners (S. scapterisci, S. monticolum, S. feltiae, and S. glaseri).We used these genomes to establish phylogenetic relationships, explore gene conservation across species, and identify genes uniquely expanded in insect parasites. Protein domain analysis in Steinernema revealed a striking expansion of numerous putative parasitism genes, including certain protease and protease inhibitor families, as well as fatty acid- and retinol-binding proteins. Stage-specific gene expression of some of these expanded families further supports the notion that they are involved in insect parasitism by Steinernema. We show that sets of novel conserved non-coding regulatory motifs are associated with orthologous genes in Steinernema and Caenorhabditis.We have identified a set of expanded gene families that are likely to be involved in parasitism. We have also identified a set of non-coding motifs associated with groups of orthologous genes in Steinernema and Caenorhabditis involved in neurogenesis and embryonic development that are likely part of conserved protein-DNA relationships shared between these two genera.
| S-EPMC4578762 | biostudies-literature
Project description:BackgroundObligate endoparasites often lack particular metabolic pathways as compared to free-living organisms. This phenomenon comprises anabolic as well as catabolic reactions. Presumably, the corresponding enzymes were lost in adaptation to parasitism. Here we compare the predicted core metabolic graphs of obligate endoparasites and non-parasites (free living organisms and facultative parasites) in order to analyze how the parasites' metabolic networks shrunk in the course of evolution.ResultsCore metabolic graphs comprising biochemical reactions present in the presumed ancestor of parasites and non-parasites were reconstructed from the Kyoto Encyclopedia of Genes and Genomes. While the parasites' networks had fewer nodes (metabolites) and edges (reactions), other parameters such as average connectivity, network diameter and number of isolated edges were similar in parasites and non-parasites. The parasites' networks contained a higher percentage of ATP-consuming reactions and a lower percentage of NAD-requiring reactions. Control networks, shrunk to the size of the parasites' by random deletion of edges, were scale-free but exhibited smaller diameters and more isolated edges.ConclusionsThe parasites' networks were smaller than those of the non-parasites regarding number of nodes or edges, but not regarding network diameters. Network integrity but not scale-freeness has acted as a selective principle during the evolutionary reduction of parasite metabolism. ATP-requiring reactions in particular have been retained in the parasites' core metabolism while NADH- or NADPH-requiring reactions were lost preferentially.
| S-EPMC2858753 | biostudies-literature
Project description:ObjectiveTo end the AIDS epidemic by 2030, despite the increasing poverty and inequalities, policies should be designed to deal with population heterogeneity and environmental changes. Bottom-up designs, such as the Agent-Based Model (ABM), can model these features, dealing with such complexity. HIV/AIDS has a complex dynamic of structural factors, risk behaviors, biomedical characteristics and interventions. All embedded in unequal, stigmatized and heterogeneous social structure. To understand how ABMs can model this complexity, we performed a scoping review of HIV applications, highlighting their potentialities.MethodsWe searched on PubMed, Web of Science, and Scopus repositories following the PRISMA extension for scoping reviews. Our inclusion criteria were HIV/AIDS studies with an ABM application. We identified the main articles using a local co-citation analysis and categorized the overall literature aims, (sub)populations, regions, and if the papers declared the use of ODD protocol and limitations.ResultsWe found 154 articles. We identified eleven main papers, and discussed them using the overall category results. Most studies model Transmission Dynamics (37/154), about Men who have sex with Men (MSM) (41/154), or individuals living in the US or South Africa (84/154). Recent studies applied ABM to model PrEP interventions (17/154) and Racial Disparities (12/154). Only six papers declared the use of ODD Protocol (6/154), and 34/154 didn't mention the study limitations.ConclusionsWhile ABM is among the most sophisticated techniques available to model HIV/AIDS complexity. Their applications are still restricted to some realities. However, researchers are challenged to think about social structure due model characteristics, the inclusion of these features is still restricted to case-specific. Data and computational power availability can enhance this feature providing insightful results.
| S-EPMC10836677 | biostudies-literature
Project description:Analysis of molecular interaction networks is pervasive in systems biology. This research relies almost entirely on graphs for modeling interactions. However, edges in graphs cannot represent multiway interactions among molecules, which occur very often within cells. Hypergraphs may be better representations for networks having such interactions, since hyperedges can naturally represent relationships among multiple molecules. Here, we propose using hypergraphs to capture the uncertainty inherent in reverse engineering gene-gene networks. Some subsets of nodes may induce highly varying subgraphs across an ensemble of networks inferred by a reverse engineering algorithm. We provide a novel formulation of hyperedges to capture this uncertainty in network topology. We propose a clustering-based approach to discover hyperedges. We show that our approach can recover hyperedges planted in synthetic data sets with high precision and recall, even for moderate amount of noise. We apply our techniques to a data set of pathways inferred from genetic interaction data in S. cerevisiae related to the unfolded protein response. Our approach discovers several hyperedges that capture the uncertain connectivity of genes in relevant protein complexes, suggesting that further experiments may be required to precisely discern their interaction patterns. We also show that these complexes are not discovered by an algorithm that computes frequent and dense subgraphs.
| S-EPMC4051496 | biostudies-literature
Project description:Hypergraphs have been a useful tool for analyzing population dynamics such as opinion formation and the public goods game occurring in overlapping groups of individuals. In the present study, we propose and analyze evolutionary dynamics on hypergraphs, in which each node takes one of the two types of different but constant fitness values. For the corresponding dynamics on conventional networks, under the birth-death process and uniform initial conditions, most networks are known to be amplifiers of natural selection; amplifiers by definition enhance the difference in the strength of the two competing types in terms of the probability that the mutant type fixates in the population. In contrast, we provide strong computational evidence that a majority of hypergraphs are suppressors of selection under the same conditions by combining theoretical and numerical analyses. We also show that this suppressing effect is not explained by one-mode projection, which is a standard method for expressing hypergraph data as a conventional network. Our results suggest that the modeling framework for structured populations in addition to the specific network structure is an important determinant of evolutionary dynamics, paving a way to studying fixation dynamics on higher-order networks including hypergraphs.
| S-EPMC10558078 | biostudies-literature
Project description:Parasitism is a major ecological niche for a variety of nematodes. Multiple nematode lineages have specialized as pathogens, including deadly parasites of insects that are used in biological control. We have sequenced and analyzed the draft genomes and transcriptomes of the entomopathogenic nematode Steinernema carpocapsae and four congeners (S. scapterisci, S. monticolum, S. feltiae, and S. glaseri). We used these genomes to establish phylogenetic relationships, explore gene conservation across species, and identify genes uniquely expanded in insect parasites. Protein domain analysis in Steinernema revealed a striking expansion of numerous putative parasitism genes, including certain protease and protease inhibitor families, as well as fatty acid- and retinol-binding proteins. Stage-specific gene expression of some of these expanded families further supports the notion that they are involved in insect parasitism by Steinernema. We show that sets of novel conserved non-coding regulatory motifs are associated with orthologous genes in Steinernema and Caenorhabditis. We have identified a set of expanded gene families that are likely to be involved in parasitism. We have also identified a set of non-coding motifs associated with groups of orthologous genes in Steinernema and Caenorhabditis involved in neurogenesis and embryonic development that are likely part of conserved protein–DNA relationships shared between these two genera.
2015-06-05 | GSE68588 | GEO
Project description:Retroelements (REs) are mobile DNA sequences that multiply and spread throughout genomes by a copy-and-paste mechanism. These parasitic elements are active in diverse genomes, from yeast to humans, where they promote diversity, cause disease, and accelerate evolution. Because of their high copy number and sequence similarity, studying their activity and tracking their proliferation dynamics is a challenge. It is particularly difficult to pinpoint the few REs in a genome that are still active in the haystack of degenerate and suppressed elements. We develop a computational framework based on network theory that tracks the path of RE proliferation throughout evolution. We analyze SVA (SINE-VNTR-Alu), the youngest RE family in human genomes, to understand RE dynamics across hominids. Integrating comparative genomics and network tools enables us to track the course of SVA proliferation, identify yet unknown active communities, and detect tentative "master REs" that played key roles in SVA propagation, providing strong support for the fundamental "master gene" model of RE proliferation. The method is generic and thus can be applied to REs of any of the thousands of available genomes to identify active RE communities and master REs that were pivotal in the evolution of their host genomes.
| S-EPMC5640379 | biostudies-literature