Dataset Information

Simplicial closure and higher-order link prediction.

ABSTRACT: Networks provide a powerful formalism for modeling complex systems by using a model of pairwise interactions. But much of the structure within these systems involves interactions that take place among more than two nodes at once-for example, communication within a group rather than person to person, collaboration among a team rather than a pair of coauthors, or biological interaction between a set of molecules rather than just two. Such higher-order interactions are ubiquitous, but their empirical study has received limited attention, and little is known about possible organizational principles of such structures. Here we study the temporal evolution of 19 datasets with explicit accounting for higher-order interactions. We show that there is a rich variety of structure in our datasets but datasets from the same system types have consistent patterns of higher-order structure. Furthermore, we find that tie strength and edge density are competing positive indicators of higher-order organization, and these trends are consistent across interactions involving differing numbers of nodes. To systematically further the study of theories for such higher-order structures, we propose higher-order link prediction as a benchmark problem to assess models and algorithms that predict higher-order structure. We find a fundamental difference from traditional pairwise link prediction, with a greater role for local rather than long-range information in predicting the appearance of new interactions.

SUBMITTER: Benson AR

PROVIDER: S-EPMC6275482 | biostudies-literature | 2018 Nov

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Simplicial closure and higher-order link prediction.

Benson Austin R AR Abebe Rediet R Schaub Michael T MT Jadbabaie Ali A Kleinberg Jon J

Proceedings of the National Academy of Sciences of the United States of America 20181109 48

Networks provide a powerful formalism for modeling complex systems by using a model of pairwise interactions. But much of the structure within these systems involves interactions that take place among more than two nodes at once-for example, communication within a group rather than person to person, collaboration among a team rather than a pair of coauthors, or biological interaction between a set of molecules rather than just two. Such higher-order interactions are ubiquitous, but their empiric ...[more]

PMID: 30413619

Similar Datasets

Project description:It is increasingly being recognized that physical interactions between distant chromosomal loci influence the expressivity of the genome. Thus, multiple enhancers may converge on a single gene promoter 1,2 and a single enhancer can stochastically loop to multiple promoters 3. Regulatory elements from neighboring domains or from other chromosomes may interact to generate chromatin structures poised for transcription4-8 or repression 9-11. However, a broader perspective on the formation and function of such networks remains largely unexplored. Using the high-resolution 4C (Circular Chromosome Conformation Capture) analysis, we identify here a genome-wide physical network between genomically imprinted domains impinging H19 imprinting control region (ICR). Sequences interacting with the H19 ICR constitutively map at or within most of known imprinted domains both in mouse embryonic stem cells and in vitro-derived embryoid bodies, despite distinct differences in chromatin environments. Moreover, all-to-all 3D DNA FISH analyses revealed that imprinted domains from 7 different chromosomes co-localize with each other in pair-wise patterns, highlighting the dynamic nature of these interactions. The observed interaction network is dependent on CTCF binding sites within the maternally inherited H19 ICR allele and delays reprogramming of epigenetic features at imprinted domains during male germline development. As other imprinted regions can interact with each other in an H19 ICR-dependent manner, the H19 ICR emerges as an organizer of chromosomal networks by specifically recognizing and reconfiguring imprinted domains. We propose that an ancient key regulatory region, such as the H19 ICR, gradually impacted epigenetic modifications via long-range interactions in the germline to facilitate the recruitment of imprinted genes and their formation in clusters during mammalian radiation. Furthermore, the perspective of epigenetic lesions de-stabilizing such chromosomal networks may advance our understanding of how quantitative traits influence human diseases, such as cancer.

Dataset Information

Simplicial closure and higher-order link prediction.

Publications

Simplicial closure and higher-order link prediction.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure