Browse
Submit Data
Databases
API
Help

Dataset Information

46 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution.

ABSTRACT: The (asymptotic) degree distributions of the best-known "scale-free" network models are all similar and are independent of the seed graph used; hence, it has been tempting to assume that networks generated by these models are generally similar. In this paper, we observe that several key topological features of such networks depend heavily on the specific model and the seed graph used. Furthermore, we show that starting with the "right" seed graph (typically a dense subgraph of the protein-protein interaction network analyzed), the duplication model captures many topological features of publicly available protein-protein interaction networks very well.

SUBMITTER: Hormozdiari F

PROVIDER: S-EPMC1913096 | biostudies-literature | 2007 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution.

Hormozdiari Fereydoun F Berenbrink Petra P Przulj Natasa N Sahinalp S Cenk SC

PLoS computational biology 20070701 7

The (asymptotic) degree distributions of the best-known "scale-free" network models are all similar and are independent of the seed graph used; hence, it has been tempting to assume that networks generated by these models are generally similar. In this paper, we observe that several key topological features of such networks depend heavily on the specific model and the seed graph used. Furthermore, we show that starting with the "right" seed graph (typically a dense subgraph of the protein-protei ...[more]

PMID: 17616981

Similar Datasets

AFTGAN: prediction of multi-type PPI based on attention free transformer and graph attention network.

Project description:MotivationProtein-protein interaction (PPI) networks and transcriptional regulatory networks are critical in regulating cells and their signaling. A thorough understanding of PPIs can provide more insights into cellular physiology at normal and disease states. Although numerous methods have been proposed to predict PPIs, it is still challenging for interaction prediction between unknown proteins. In this study, a novel neural network named AFTGAN was constructed to predict multi-type PPIs. Regarding feature input, ESM-1b embedding containing much biological information for proteins was added as a protein sequence feature besides amino acid co-occurrence similarity and one-hot coding. An ensemble network was also constructed based on a transformer encoder containing an AFT module (performing the weight operation on vital protein sequence feature information) and graph attention network (extracting the relational features of protein pairs) for the part of the network framework.ResultsThe experimental results showed that the Micro-F1 of the AFTGAN based on three partitioning schemes (BFS, DFS and the random mode) on the SHS27K and SHS148K datasets was 0.685, 0.711 and 0.867, as well as 0.745, 0.819 and 0.920, respectively, all higher than that of other popular methods. In addition, the experimental comparisons confirmed the performance superiority of the proposed model for predicting PPIs of unknown proteins on the STRING dataset.Availability and implementationThe source code is publicly available at https://github.com/1075793472/AFTGAN.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC9897180 | biostudies-literature

Dynamic pattern evolution on scale-free networks.

Project description:A general class of dynamic models on scale-free networks is studied by analytical methods and computer simulations. Each network consists of N vertices and is characterized by its degree distribution, P(k), which represents the probability that a randomly chosen vertex is connected to k nearest neighbors. Each vertex can attain two internal states described by binary variables or Ising-like spins that evolve in time according to local majority rules. Scale-free networks, for which the degree distribution has a power law tail P(k) approximately k(-gamma), are shown to exhibit qualitatively different dynamic behavior for gamma < 5/2 and gamma > 5/2, shedding light on the empirical observation that many real-world networks are scale-free with 2 < gamma < 5/2. For 2 < gamma < 5/2, strongly disordered patterns decay within a finite decay time even in the limit of infinite networks. For gamma > 5/2, on the other hand, this decay time diverges as ln(N) with the network size N. An analogous distinction is found for a variety of more complex models including Hopfield models for associative memory networks. In the latter case, the storage capacity is found, within mean field theory, to be independent of N in the limit of large N for gamma > 5/2 but to grow as N(alpha) with alpha = (5 - 2gamma)/(gamma - 1) for 2 < gamma < 5/2.

| S-EPMC1174918 | biostudies-literature

Entropy-Based Graph Clustering of PPI Networks for Predicting Overlapping Functional Modules of Proteins.

Project description:Functional modules can be predicted using genome-wide protein-protein interactions (PPIs) from a systematic perspective. Various graph clustering algorithms have been applied to PPI networks for this task. In particular, the detection of overlapping clusters is necessary because a protein is involved in multiple functions under different conditions. graph entropy (GE) is a novel metric to assess the quality of clusters in a large, complex network. In this study, the unweighted and weighted GE algorithm is evaluated to prove the validity of predicting function modules. To measure clustering accuracy, the clustering results are compared to protein complexes and Gene Ontology (GO) annotations as references. We demonstrate that the GE algorithm is more accurate in overlapping clusters than the other competitive methods. Moreover, we confirm the biological feasibility of the proteins that occur most frequently in the set of identified clusters. Finally, novel proteins for the additional annotation of GO terms are revealed.

| S-EPMC8534328 | biostudies-literature

Equal graph partitioning on estimated infection network as an effective epidemic mitigation measure.

Project description:Controlling severe outbreaks remains the most important problem in infectious disease area. With time, this problem will only become more severe as population density in urban centers grows. Social interactions play a very important role in determining how infectious diseases spread, and organization of people along social lines gives rise to non-spatial networks in which the infections spread. Infection networks are different for diseases with different transmission modes, but are likely to be identical or highly similar for diseases that spread the same way. Hence, infection networks estimated from common infections can be useful to contain epidemics of a more severe disease with the same transmission mode. Here we present a proof-of-concept study demonstrating the effectiveness of epidemic mitigation based on such estimated infection networks. We first generate artificial social networks of different sizes and average degrees, but with roughly the same clustering characteristic. We then start SIR epidemics on these networks, censor the simulated incidences, and use them to reconstruct the infection network. We then efficiently fragment the estimated network by removing the smallest number of nodes identified by a graph partitioning algorithm. Finally, we demonstrate the effectiveness of this targeted strategy, by comparing it against traditional untargeted strategies, in slowing down and reducing the size of advancing epidemics.

| S-EPMC3142118 | biostudies-literature

Subnets of scale-free networks are not scale-free: sampling properties of networks.

Project description:Most studies of networks have only looked at small subsets of the true network. Here, we discuss the sampling properties of a network's degree distribution under the most parsimonious sampling scheme. Only if the degree distributions of the network and randomly sampled subnets belong to the same family of probability distributions is it possible to extrapolate from subnet data to properties of the global network. We show that this condition is indeed satisfied for some important classes of networks, notably classical random graphs and exponential random graphs. For scale-free degree distributions, however, this is not the case. Thus, inferences about the scale-free nature of a network may have to be treated with some caution. The work presented here has important implications for the analysis of molecular networks as well as for graph theory and the theory of networks in general.

| S-EPMC555505 | biostudies-literature

Emergent scale-free networks.

Project description:Many complex systems-from the Internet to social, biological, and communication networks-are thought to exhibit scale-free structure. However, prevailing explanations require that networks grow over time, an assumption that fails in some real-world settings. Here, we explain how scale-free structure can emerge without growth through network self-organization. Beginning with an arbitrary network, we allow connections to detach from random nodes and then reconnect under a mixture of preferential and random attachment. While the numbers of nodes and edges remain fixed, the degree distribution evolves toward a power-law with an exponent γ=1+1p that depends only on the proportion p of preferential (rather than random) attachment. Applying our model to several real networks, we infer p directly from data and predict the relationship between network size and degree heterogeneity. Together, these results establish how scale-free structure can arise in networks of constant size and density, with broad implications for the structure and function of complex systems.

| S-EPMC11223655 | biostudies-literature

Accelerating network layouts using graph neural networks.

Project description:Graph layout algorithms used in network visualization represent the first and the most widely used tool to unveil the inner structure and the behavior of complex networks. Current network visualization software relies on the force-directed layout (FDL) algorithm, whose high computational complexity makes the visualization of large real networks computationally prohibitive and traps large graphs into high energy configurations, resulting in hard-to-interpret "hairball" layouts. Here we use Graph Neural Networks (GNN) to accelerate FDL, showing that deep learning can address both limitations of FDL: it offers a 10 to 100 fold improvement in speed while also yielding layouts which are more informative. We analytically derive the speedup offered by GNN, relating it to the number of outliers in the eigenspectrum of the adjacency matrix, predicting that GNNs are particularly effective for networks with communities and local regularities. Finally, we use GNN to generate a three-dimensional layout of the Internet, and introduce additional measures to assess the layout quality and its interpretability, exploring the algorithm's ability to separate communities and the link-length distribution. The novel use of deep neural networks can help accelerate other network-based optimization problems as well, with applications from reaction-diffusion systems to epidemics.

| S-EPMC10030870 | biostudies-literature

Evolution of the coniferous seed scale.

Project description:BackgroundThe Florin model is the commonly accepted theory of coniferous seed scale evolution. It describes the derivation of extant seed scale morphology from the morphology of fossil conifers via the reduction of complex to simple axillary structures. In this framework the seed scale is composed of a reduced lateral shoot with fertile and sterile appendages which are interpreted as leaf homologues.ScopeThe Florin model has three crucial problems that we address here: (1) the original derivation series does not take the ontogeny of extant conifers into account, (2) it cannot explain the morphology of all extant conifers and (3) Taxaceae were originally excluded. Examination of seed cones of extant conifers shows that ovules occur in three different positions in the cone: in an axillary position, replacing a leaf or terminating the cone axis. By interpreting the fertile appendage or seed-bearing structure as a leaf, not all positions are possible. The exclusion of Taxaceae from conifers is in stark contrast to recent molecular phylogenetic studies, which include Taxaceae in conifers as sister to Cupressaceae. Therefore, the Florin model does not offer an adequate explanation for taxaceous morphology.ConclusionWe conclude that the seed-bearing structure of conifers cannot be interpreted as homologous to a leaf. In the interpretation we present here, the seed-bearing structure is the modified funiculus of the ovule, multiples of which laterally fuse to form the seed scale. The seed scales of all extant conifers can be derived from a Cunninghamia-like morphology via fusion and reduction of individual funiculi.

| S-EPMC9292595 | biostudies-literature

Protein Function Prediction Based on PPI Networks: Network Reconstruction vs Edge Enrichment.

Project description:Over the past decades, massive amounts of protein-protein interaction (PPI) data have been accumulated due to the advancement of high-throughput technologies, and but data quality issues (noise or incompleteness) of PPI have been still affecting protein function prediction accuracy based on PPI networks. Although two main strategies of network reconstruction and edge enrichment have been reported on the effectiveness of boosting the prediction performance in numerous literature studies, there still lack comparative studies of the performance differences between network reconstruction and edge enrichment. Inspired by the question, this study first uses three protein similarity metrics (local, global and sequence) for network reconstruction and edge enrichment in PPI networks, and then evaluates the performance differences of network reconstruction, edge enrichment and the original networks on two real PPI datasets. The experimental results demonstrate that edge enrichment work better than both network reconstruction and original networks. Moreover, for the edge enrichment of PPI networks, the sequence similarity outperformes both local and global similarity. In summary, our study can help biologists select suitable pre-processing schemes and achieve better protein function prediction for PPI networks.

| S-EPMC8712557 | biostudies-literature

Polymer Informatics at Scale with Multitask Graph Neural Networks

Project description:Artificial intelligence-based methods are becoming increasingly

| S-EPMC9979603 | biostudies-literature