1
|
A granularity-level information fusion strategy on hypergraph transformer for predicting synergistic effects of anticancer drugs. Brief Bioinform 2023; 25:bbad522. [PMID: 38243692 PMCID: PMC10796255 DOI: 10.1093/bib/bbad522] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/02/2023] [Revised: 11/08/2023] [Accepted: 12/19/2023] [Indexed: 01/21/2024] Open
Abstract
Combination therapy has exhibited substantial potential compared to monotherapy. However, due to the explosive growth in the number of cancer drugs, the screening of synergistic drug combinations has become both expensive and time-consuming. Synergistic drug combinations refer to the concurrent use of two or more drugs to enhance treatment efficacy. Currently, numerous computational methods have been developed to predict the synergistic effects of anticancer drugs. However, there has been insufficient exploration of how to mine drug and cell line data at different granularity levels for predicting synergistic anticancer drug combinations. Therefore, this study proposes a granularity-level information fusion strategy based on the hypergraph transformer, named HypertranSynergy, to predict synergistic effects of anticancer drugs. HypertranSynergy introduces synergistic connections between cancer cell lines and drug combinations using hypergraph. Then, the Coarse-grained Information Extraction (CIE) module merges the hypergraph with a transformer for node embeddings. In the CIE module, Contranorm is a normalization layer that mitigates over-smoothing, while Gaussian noise addresses local information gaps. Additionally, the Fine-grained Information Extraction (FIE) module assesses fine-grained information's impact on predictions by employing similarity-aware matrices from drug/cell line features. Both CIE and FIE modules are integrated into HypertranSynergy. In addition, HypertranSynergy achieved the AUC of 0.93${\pm }$0.01 and the AUPR of 0.69${\pm }$0.02 in 5-fold cross-validation of classification task, and the RMSE of 13.77${\pm }$0.07 and the PCC of 0.81${\pm }$0.02 in 5-fold cross-validation of regression task. These results are better than most of the state-of-the-art models.
Collapse
|
2
|
Percolation Theories for Quantum Networks. ENTROPY (BASEL, SWITZERLAND) 2023; 25:1564. [PMID: 37998256 PMCID: PMC10670322 DOI: 10.3390/e25111564] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/28/2023] [Revised: 11/13/2023] [Accepted: 11/17/2023] [Indexed: 11/25/2023]
Abstract
Quantum networks have experienced rapid advancements in both theoretical and experimental domains over the last decade, making it increasingly important to understand their large-scale features from the viewpoint of statistical physics. This review paper discusses a fundamental question: how can entanglement be effectively and indirectly (e.g., through intermediate nodes) distributed between distant nodes in an imperfect quantum network, where the connections are only partially entangled and subject to quantum noise? We survey recent studies addressing this issue by drawing exact or approximate mappings to percolation theory, a branch of statistical physics centered on network connectivity. Notably, we show that the classical percolation frameworks do not uniquely define the network's indirect connectivity. This realization leads to the emergence of an alternative theory called "concurrence percolation", which uncovers a previously unrecognized quantum advantage that emerges at large scales, suggesting that quantum networks are more resilient than initially assumed within classical percolation contexts, offering refreshing insights into future quantum network design.
Collapse
|
3
|
Prediction of multi-relational drug-gene interaction via Dynamic hyperGraph Contrastive Learning. Brief Bioinform 2023; 24:bbad371. [PMID: 37864294 DOI: 10.1093/bib/bbad371] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/28/2023] [Revised: 09/11/2023] [Accepted: 09/29/2023] [Indexed: 10/22/2023] Open
Abstract
Drug-gene interaction prediction occupies a crucial position in various areas of drug discovery, such as drug repurposing, lead discovery and off-target detection. Previous studies show good performance, but they are limited to exploring the binding interactions and ignoring the other interaction relationships. Graph neural networks have emerged as promising approaches owing to their powerful capability of modeling correlations under drug-gene bipartite graphs. Despite the widespread adoption of graph neural network-based methods, many of them experience performance degradation in situations where high-quality and sufficient training data are unavailable. Unfortunately, in practical drug discovery scenarios, interaction data are often sparse and noisy, which may lead to unsatisfactory results. To undertake the above challenges, we propose a novel Dynamic hyperGraph Contrastive Learning (DGCL) framework that exploits local and global relationships between drugs and genes. Specifically, graph convolutions are adopted to extract explicit local relations among drugs and genes. Meanwhile, the cooperation of dynamic hypergraph structure learning and hypergraph message passing enables the model to aggregate information in a global region. With flexible global-level messages, a self-augmented contrastive learning component is designed to constrain hypergraph structure learning and enhance the discrimination of drug/gene representations. Experiments conducted on three datasets show that DGCL is superior to eight state-of-the-art methods and notably gains a 7.6% performance improvement on the DGIdb dataset. Further analyses verify the robustness of DGCL for alleviating data sparsity and over-smoothing issues.
Collapse
|
4
|
Beyond fitness: the nature of selection acting through the constructive steps of lifecycles. Evolution 2023; 77:1967-1986. [PMID: 37161529 DOI: 10.1093/evolut/qpad068] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/16/2020] [Revised: 03/27/2023] [Accepted: 04/07/2023] [Indexed: 05/11/2023]
Abstract
We address the problem of defining selection and extracting the adaptive part of evolutionary change, originally formalized by Fisher and Price. Conventionally, selection and adaptation are defined through fitness attributed to genes or genotypes chosen as units of selection. The construction through fitness is known to suffer ambiguities and omissions as a theory of change due to selection. We construct an alternative framing in which units of selection and fitness are replaced as the main abstractions by formal lifecycle models and reproduction rates through genetically distinct lifecycle realizations. Graphical representations of lifecycles express relations among reproductive stages that cannot be assigned to any one unit of selection. The lifecycle partition refines the statistics of overall reproductive success and resolves modes of selection that fitness either excludes or distorts through additive projections. We derive the Price equation in the basis of lifecycle realizations and compare it to the conventional Price equation for additive fitness of organisms. We show how the lifecycle approach recovers fitnesses acting concurrently at multiple levels, or contrasts forms of competition within and between levels that are invisible to additive fitness. Defining selection through lifecycles recasts population genetics from an object-focused to a construction- and process-focused representation.
Collapse
|
5
|
Constructing high-order functional networks based on hypergraph for diagnosis of autism spectrum disorders. Front Neurosci 2023; 17:1257982. [PMID: 37719159 PMCID: PMC10501447 DOI: 10.3389/fnins.2023.1257982] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/13/2023] [Accepted: 08/17/2023] [Indexed: 09/19/2023] Open
Abstract
Introduction High-order functional connectivity networks (FCNs) that reflect the connection relationships among multiple brain regions have become important tools for exploring the deep workings of the brain and revealing the mechanisms of brain diseases. The traditional high-order FCN constructed based on the "correlation of correlations" strategy, is a representative method for conducting whole-brain connectivity analysis and revealing global network characteristics. However, whole-brain connectivity analysis may be affected by noise carried by less important brain regions, resulting in redundant information and affecting the accuracy and reliability of the analysis. Moreover, this type of analysis has a high computational complexity. Methods To address these issues, a new method for constructing high-order FCN based on hypergraphs is proposed in this article, which is used to accurately capture the real interaction relationships among brain regions. Specifically, first, a low-order FCN reflecting the connection relationships between pairs of brain regions based on resting-state functional Magnetic Resonance Imaging (rs-fMRI) time series is constructed, the method first constructs the low-order FCN that reflects the connection relationships between pairs of brain regions based on rs-fMRI time series, and then selects the "good friends" of each brain region from hypergraph perspective, which refers to the local friend circles with closer relationships. Then, the rs-fMRI time series corresponding to the "good friends" in each brain region's friend circle are averaged to obtain a sequence that reflects the intimacy between brain regions in each friend circle. Finally, hypergraph high-order FCN, which reflects the interaction relationships among multiple brain regions, is obtained by calculating the correlations based on the sequence of friend circles. Results The experimental results demonstrate that the proposed method outperforms traditional high-order FCN construction methods. Furthermore, integrating the high-order FCN constructed based on hypergraphs and the low-order FCN through feature fusion to achieve complementary information improves the accuracy of assisting in the diagnosis of brain diseases. Discussion In addition, the effectiveness of our method has only been validated in the diagnosis of ASD. For future work, we plan to extend this method to other brain connectivity patterns.
Collapse
|
6
|
Identifying Vital Nodes in Hypergraphs Based on Von Neumann Entropy. ENTROPY (BASEL, SWITZERLAND) 2023; 25:1263. [PMID: 37761562 PMCID: PMC10528012 DOI: 10.3390/e25091263] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/24/2023] [Revised: 08/01/2023] [Accepted: 08/05/2023] [Indexed: 09/29/2023]
Abstract
Hypergraphs have become an accurate and natural expression of high-order coupling relationships in complex systems. However, applying high-order information from networks to vital node identification tasks still poses significant challenges. This paper proposes a von Neumann entropy-based hypergraph vital node identification method (HVC) that integrates high-order information as well as its optimized version (semi-SAVC). HVC is based on the high-order line graph structure of hypergraphs and measures changes in network complexity using von Neumann entropy. It integrates s-line graph information to quantify node importance in the hypergraph by mapping hyperedges to nodes. In contrast, semi-SAVC uses a quadratic approximation of von Neumann entropy to measure network complexity and considers only half of the maximum order of the hypergraph's s-line graph to balance accuracy and efficiency. Compared to the baseline methods of hyperdegree centrality, closeness centrality, vector centrality, and sub-hypergraph centrality, the new methods demonstrated superior identification of vital nodes that promote the maximum influence and maintain network connectivity in empirical hypergraph data, considering the influence and robustness factors. The correlation and monotonicity of the identification results were quantitatively analyzed and comprehensive experimental results demonstrate the superiority of the new methods. At the same time, a key non-trivial phenomenon was discovered: influence does not increase linearly as the s-line graph orders increase. We call this the saturation effect of high-order line graph information in hypergraph node identification. When the order reaches its saturation value, the addition of high-order information often acts as noise and affects propagation.
Collapse
|
7
|
Multimodal Classification Framework Based on Hypergraph Latent Relation for End-Stage Renal Disease Associated with Mild Cognitive Impairment. Bioengineering (Basel) 2023; 10:958. [PMID: 37627843 PMCID: PMC10451373 DOI: 10.3390/bioengineering10080958] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/06/2023] [Revised: 08/09/2023] [Accepted: 08/10/2023] [Indexed: 08/27/2023] Open
Abstract
Combined arterial spin labeling (ASL) and functional magnetic resonance imaging (fMRI) can reveal more comprehensive properties of the spatiotemporal and quantitative properties of brain networks. Imaging markers of end-stage renal disease associated with mild cognitive impairment (ESRDaMCI) will be sought from these properties. The current multimodal classification methods often neglect to collect high-order relationships of brain regions and remove noise from the feature matrix. A multimodal classification framework is proposed to address this issue using hypergraph latent relation (HLR). A brain functional network with hypergraph structural information is constructed by fMRI data. The feature matrix is obtained through graph theory (GT). The cerebral blood flow (CBF) from ASL is selected as the second modal feature matrix. Then, the adaptive similarity matrix is constructed by learning the latent relation between feature matrices. Latent relation adaptive similarity learning (LRAS) is introduced to multi-task feature learning to construct a multimodal feature selection method based on latent relation (LRMFS). The experimental results show that the best classification accuracy (ACC) reaches 88.67%, at least 2.84% better than the state-of-the-art methods. The proposed framework preserves more valuable information between brain regions and reduces noise among feature matrixes. It provides an essential reference value for ESRDaMCI recognition.
Collapse
|
8
|
Dynamical Analysis of Hyper-ILSR Rumor Propagation Model with Saturation Incidence Rate. ENTROPY (BASEL, SWITZERLAND) 2023; 25:e25050805. [PMID: 37238560 DOI: 10.3390/e25050805] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/19/2023] [Revised: 04/29/2023] [Accepted: 05/15/2023] [Indexed: 05/28/2023]
Abstract
With the development of the Internet, it is more convenient for people to obtain information, which also facilitates the spread of rumors. It is imperative to study the mechanisms of rumor transmission to control the spread of rumors. The process of rumor propagation is often affected by the interaction of multiple nodes. To reflect higher-order interactions in rumor-spreading, hypergraph theories are introduced in a Hyper-ILSR (Hyper-Ignorant-Lurker-Spreader-Recover) rumor-spreading model with saturation incidence rate in this study. Firstly, the definition of hypergraph and hyperdegree is introduced to explain the construction of the model. Secondly, the existence of the threshold and equilibrium of the Hyper-ILSR model is revealed by discussing the model, which is used to judge the final state of rumor propagation. Next, the stability of equilibrium is studied by Lyapunov functions. Moreover, optimal control is put forward to suppress rumor propagation. Finally, the differences between the Hyper-ILSR model and the general ILSR model are shown in numerical simulations.
Collapse
|
9
|
A Novel Longitudinal Phenotype-Genotype Association Study Based on Deep Feature Extraction and Hypergraph Models for Alzheimer's Disease. Biomolecules 2023; 13:biom13050728. [PMID: 37238598 DOI: 10.3390/biom13050728] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/20/2023] [Revised: 03/30/2023] [Accepted: 04/18/2023] [Indexed: 05/28/2023] Open
Abstract
Traditional image genetics primarily uses linear models to investigate the relationship between brain image data and genetic data for Alzheimer's disease (AD) and does not take into account the dynamic changes in brain phenotype and connectivity data across time between different brain areas. In this work, we proposed a novel method that combined Deep Subspace reconstruction with Hypergraph-Based Temporally-constrained Group Sparse Canonical Correlation Analysis (DS-HBTGSCCA) to discover the deep association between longitudinal phenotypes and genotypes. The proposed method made full use of dynamic high-order correlation between brain regions. In this method, the deep subspace reconstruction technique was applied to retrieve the nonlinear properties of the original data, and hypergraphs were used to mine the high-order correlation between two types of rebuilt data. The molecular biological analysis of the experimental findings demonstrated that our algorithm was capable of extracting more valuable time series correlation from the real data obtained by the AD neuroimaging program and finding AD biomarkers across multiple time points. Additionally, we used regression analysis to verify the close relationship between the extracted top brain areas and top genes and found the deep subspace reconstruction approach with a multi-layer neural network was helpful in enhancing clustering performance.
Collapse
|
10
|
Classify patients with Moyamoya disease according to their cognitive performance might be helpful in clinical and practical with support vector machine based on hypergraph. Hum Brain Mapp 2023; 44:2407-2417. [PMID: 36799621 PMCID: PMC10028655 DOI: 10.1002/hbm.26218] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/15/2022] [Revised: 01/10/2023] [Accepted: 01/12/2023] [Indexed: 02/18/2023] Open
Abstract
Moyamoya disease (MMD) patients were now classified according to their cerebrovascular manifestations, with cognition and emotion ignored, which attenuated the therapy. The present study tried to classify them based on their cognitive and emotional performance and explored the neural basis underlying this classification using resting-state fMRI (rs-fMRI). Thirty-nine MMD patients were recruited, assessed mental function and MRI scanned. We adopted hierarchical analysis of their mental performance for new subtypes. Next, a three-step analysis, with each step consisting of 10 random cross validation, was conducted for robust brain regions in classifying the three subtypes of patients in a support vector machine (SVM) model with hypergraph of rs-fMRI. We found three new subtypes including high depression-high anxiety-low cognition (HE-LC, 50%), low depression-low anxiety-high cognition (LE-HC, 14%), and low depression-low anxiety-low cognition (LE-LC, 36%), and no hemorrhagic MMD patients fell into the LE-HC group. The temporal and the bilateral superior frontal cortex, and so forth were included in all 10 randomized SVM modeling. The classification accuracy of the final three-way classification model was 67.5% in average of 10 random cross validation. In addition, the S value between the frontal cortex and the angular cortex was positively correlated with the anxiety score and backward digit span (p < .05). Our results might provide a new perspective for MMD classification concerning patients' mental status, guide timely surgery and suggest angular cortex, and so forth should be protected in surgery for cognitive consideration.
Collapse
|
11
|
AMHMDA: attention aware multi-view similarity networks and hypergraph learning for miRNA-disease associations identification. Brief Bioinform 2023; 24:7076121. [PMID: 36907654 DOI: 10.1093/bib/bbad094] [Citation(s) in RCA: 8] [Impact Index Per Article: 8.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/07/2022] [Revised: 01/29/2023] [Accepted: 02/27/2023] [Indexed: 03/14/2023] Open
Abstract
In recent years, many experiments have proved that microRNAs (miRNAs) play a variety of important regulatory roles in cells, and their abnormal expression can lead to the emergence of specific diseases. Therefore, it is greatly valuable to do research on the association between miRNAs and diseases, which can effectively help prevent and treat miRNA-related diseases. At present, effective computational methods still need to be developed to better identify potential miRNA-disease associations. Inspired by graph convolutional networks, in this study, we propose a new method based on Attention aware Multi-view similarity networks and Hypergraph learning for MiRNA-Disease Associations identification (AMHMDA). First, we construct multiple similarity networks for miRNAs and diseases, and exploit the graph convolutional networks fusion attention mechanism to obtain the important information from different views. Then, in order to obtain high-quality links and richer nodes information, we introduce a kind of virtual nodes called hypernodes to construct heterogeneous hypergraph of miRNAs and diseases. Finally, we employ the attention mechanism to fuse the outputs of graph convolutional networks, predicting miRNA-disease associations. To verify the effectiveness of this method, we carry out a series of experiments on the Human MicroRNA Disease Database (HMDD v3.2). The experimental results show that AMHMDA has good performance compared with other methods. In addition, the case study results also fully demonstrate the reliable predictive performance of AMHMDA.
Collapse
|
12
|
Multi-Modal Imaging Genetics Data Fusion via a Hypergraph-Based Manifold Regularization: Application to Schizophrenia Study. IEEE TRANSACTIONS ON MEDICAL IMAGING 2022; 41:2263-2272. [PMID: 35320094 PMCID: PMC9661879 DOI: 10.1109/tmi.2022.3161828] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/14/2023]
Abstract
Recent studies show that multi-modal data fusion techniques combine information from diverse sources for comprehensive diagnosis and prognosis of complex brain disorder, often resulting in improved accuracy compared to single-modality approaches. However, many existing data fusion methods extract features from homogeneous networs, ignoring heterogeneous structural information among multiple modalities. To this end, we propose a Hypergraph-based Multi-modal data Fusion algorithm, namely HMF. Specifically, we first generate a hypergraph similarity matrix to represent the high-order relationships among subjects, and then enforce the regularization term based upon both the inter- and intra-modality relationships of the subjects. Finally, we apply HMF to integrate imaging and genetics datasets. Validation of the proposed method is performed on both synthetic data and real samples from schizophrenia study. Results show that our algorithm outperforms several competing methods, and reveals significant interactions among risk genes, environmental factors and abnormal brain regions.
Collapse
|
13
|
Capturing complex interactions in disease ecology with simplicial sets. Ecol Lett 2022; 25:2217-2231. [PMID: 36001469 DOI: 10.1111/ele.14079] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/03/2022] [Revised: 04/21/2022] [Accepted: 06/29/2022] [Indexed: 11/28/2022]
Abstract
Network approaches have revolutionized the study of ecological interactions. Social, movement and ecological networks have all been integral to studying infectious disease ecology. However, conventional (dyadic) network approaches are limited in their ability to capture higher-order interactions. We present simplicial sets as a tool that addresses this limitation. First, we explain what simplicial sets are. Second, we explain why their use would be beneficial in different subject areas. Third, we detail where these areas are: social, transmission, movement/spatial and ecological networks and when using them would help most in each context. To demonstrate their application, we develop a novel approach to identify how pathogens persist within a host population. Fourth, we provide an overview of how to use simplicial sets, highlighting specific metrics, generative models and software. Finally, we synthesize key research questions simplicial sets will help us answer and draw attention to methodological developments that will facilitate this.
Collapse
|
14
|
Abstract
This study aimed to identify systemic multimorbidity clusters in people with periodontitis via a novel artificial intelligence-based network analysis and to explore the effect of associated factors. This study utilized cross-sectional data of 3,736 participants across 3 cycles of the National Health and Nutrition Examination Survey (2009 to 2014). Periodontal examination was carried out by trained dentists for participants aged ≥30 y. The extent of periodontitis was represented by the proportion of sites with clinical attachment loss (CAL)≥ 3 mm, split into 4 equal quartiles. A range of systemic diseases reported during the survey were also extracted. Hypergraph network analysis with eigenvector centralities was applied to identify systemic multimorbidity clusters and single-disease influence in the overall population and when stratified by CAL quartile. Individual factors that could affect the systemic multimorbidity clusters were also explored by CAL quartile. In the study population, the top 3 prevalent diseases were hypertension (63.9%), arthritis (47.6%), and obesity (45.9%). A total of 106 unique systemic multimorbidity clusters were identified across the study population. Hypertension was the most centralized disease in the overall population (centrality [C]: 0.50), followed closely by arthritis (C: 0.45) and obesity (C: 0.42). Diabetes had higher centrality in the highest CAL quartile (C: 0.31) than the lowest (C: 0.26). "Hypertension, obesity" was the largest weighted multimorbidity cluster across CAL quartiles. This study has revealed a range of common systemic multimorbidity clusters in people with periodontitis. People with periodontitis are more likely to present with hypertension and obesity together, and diabetes is more influential to multimorbidity clusters in people with severe periodontitis. Factors such as ethnicity, deprivation, and smoking status may also influence the pattern of multimorbidity clusters.
Collapse
|
15
|
ASPECTS OF TOPOLOGICAL APPROACHES FOR DATA SCIENCE. FOUNDATIONS OF DATA SCIENCE (SPRINGFIELD, MO.) 2022; 4:165-216. [PMID: 36712596 PMCID: PMC9881677 DOI: 10.3934/fods.2022002] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/18/2023]
Abstract
We establish a new theory which unifies various aspects of topological approaches for data science, by being applicable both to point cloud data and to graph data, including networks beyond pairwise interactions. We generalize simplicial complexes and hypergraphs to super-hypergraphs and establish super-hypergraph homology as an extension of simplicial homology. Driven by applications, we also introduce super-persistent homology.
Collapse
|
16
|
The Genomic Physics of COVID-19 Pathogenesis and Spread. Cells 2021; 11:cells11010080. [PMID: 35011641 PMCID: PMC8750765 DOI: 10.3390/cells11010080] [Citation(s) in RCA: 7] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/16/2021] [Revised: 12/19/2021] [Accepted: 12/23/2021] [Indexed: 12/11/2022] Open
Abstract
Coronavirus disease (COVID-19) spreads mainly through close contact of infected persons, but the molecular mechanisms underlying its pathogenesis and transmission remain unknown. Here, we propose a statistical physics model to coalesce all molecular entities into a cohesive network in which the roadmap of how each entity mediates the disease can be characterized. We argue that the process of how a transmitter transforms the virus into a recipient constitutes a triad unit that propagates COVID-19 along reticulate paths. Intrinsically, person-to-person transmissibility may be mediated by how genes interact transversely across transmitter, recipient, and viral genomes. We integrate quantitative genetic theory into hypergraph theory to code the main effects of the three genomes as nodes, pairwise cross-genome epistasis as edges, and high-order cross-genome epistasis as hyperedges in a series of mobile hypergraphs. Charting a genome-wide atlas of horizontally epistatic hypergraphs can facilitate the systematic characterization of the community genetic mechanisms underlying COVID-19 spread. This atlas can typically help design effective containment and mitigation strategies and screen and triage those more susceptible persons and those asymptomatic carriers who are incubation virus transmitters.
Collapse
|
17
|
Graphical Models in Reconstructability Analysis and Bayesian Networks. ENTROPY (BASEL, SWITZERLAND) 2021; 23:986. [PMID: 34441126 PMCID: PMC8393825 DOI: 10.3390/e23080986] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 06/05/2021] [Revised: 07/22/2021] [Accepted: 07/26/2021] [Indexed: 11/16/2022]
Abstract
Reconstructability Analysis (RA) and Bayesian Networks (BN) are both probabilistic graphical modeling methodologies used in machine learning and artificial intelligence. There are RA models that are statistically equivalent to BN models and there are also models unique to RA and models unique to BN. The primary goal of this paper is to unify these two methodologies via a lattice of structures that offers an expanded set of models to represent complex systems more accurately or more simply. The conceptualization of this lattice also offers a framework for additional innovations beyond what is presented here. Specifically, this paper integrates RA and BN by developing and visualizing: (1) a BN neutral system lattice of general and specific graphs, (2) a joint RA-BN neutral system lattice of general and specific graphs, (3) an augmented RA directed system lattice of prediction graphs, and (4) a BN directed system lattice of prediction graphs. Additionally, it (5) extends RA notation to encompass BN graphs and (6) offers an algorithm to search the joint RA-BN neutral system lattice to find the best representation of system structure from underlying system variables. All lattices shown in this paper are for four variables, but the theory and methodology presented in this paper are general and apply to any number of variables. These methodological innovations are contributions to machine learning and artificial intelligence and more generally to complex systems analysis. The paper also reviews some relevant prior work of others so that the innovations offered here can be understood in a self-contained way within the context of this paper.
Collapse
|
18
|
Graph fractal dimension and the structure of fractal networks. JOURNAL OF COMPLEX NETWORKS 2020; 8:cnaa037. [PMID: 33251012 PMCID: PMC7673317 DOI: 10.1093/comnet/cnaa037] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/11/2020] [Accepted: 09/28/2020] [Indexed: 06/12/2023]
Abstract
Fractals are geometric objects that are self-similar at different scales and whose geometric dimensions differ from so-called fractal dimensions. Fractals describe complex continuous structures in nature. Although indications of self-similarity and fractality of complex networks has been previously observed, it is challenging to adapt the machinery from the theory of fractality of continuous objects to discrete objects such as networks. In this article, we identify and study fractal networks using the innate methods of graph theory and combinatorics. We establish analogues of topological (Lebesgue) and fractal (Hausdorff) dimensions for graphs and demonstrate that they are naturally related to known graph-theoretical characteristics: rank dimension and product dimension. Our approach reveals how self-similarity and fractality of a network are defined by a pattern of overlaps between densely connected network communities. It allows us to identify fractal graphs, explore the relations between graph fractality, graph colourings and graph descriptive complexity, and analyse the fractality of several classes of graphs and network models, as well as of a number of real-life networks. We demonstrate the application of our framework in evolutionary biology and virology by analysing networks of viral strains sampled at different stages of evolution inside their hosts. Our methodology revealed gradual self-organization of intra-host viral populations over the course of infection and their adaptation to the host environment. The obtained results lay a foundation for studying fractal properties of complex networks using combinatorial methods and algorithms.
Collapse
|
19
|
Multi- Hypergraph Learning-Based Brain Functional Connectivity Analysis in fMRI Data. IEEE TRANSACTIONS ON MEDICAL IMAGING 2020; 39:1746-1758. [PMID: 31796393 PMCID: PMC7376954 DOI: 10.1109/tmi.2019.2957097] [Citation(s) in RCA: 10] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/10/2023]
Abstract
Recently, a hypergraph constructed from functional magnetic resonance imaging (fMRI) was utilized to explore brain functional connectivity networks (FCNs) for the classification of neurodegenerative diseases. Each edge of a hypergraph (called hyperedge) can connect any number of brain regions-of-interest (ROIs) instead of only two ROIs, and thus characterizes high-order relations among multiple ROIs that cannot be uncovered by a simple graph in the traditional graph based FCN construction methods. Unlike the existing hypergraph based methods where all hyperedges are assumed to have equal weights and only certain topological features are extracted from the hypergraphs, we propose a hypergraph learning based method for FCN construction in this paper. Specifically, we first generate hyperedges from fMRI time series based on sparse representation, then employ hypergraph learning to adaptively learn hyperedge weights, and finally define a hypergraph similarity matrix to represent the FCN. In our proposed method, weighting hyperedges results in better discriminative FCNs across subjects, and the defined hypergraph similarity matrix can better reveal the overall structure of brain network than using those hypergraph topological features. Moreover, we propose a multi-hypergraph learning based method by integrating multi-paradigm fMRI data, where the hyperedge weights associated with each fMRI paradigm are jointly learned and then a unified hypergraph similarity matrix is computed to represent the FCN. We validate the effectiveness of the proposed method on the Philadelphia Neurodevelopmental Cohort dataset for the classification of individuals' learning ability from three paradigms of fMRI data. Experimental results demonstrate that our proposed approach outperforms the traditional graph based methods (i.e., Pearson's correlation and partial correlation with the graphical Lasso) and the existing unweighted hypergraph based methods, which sheds light on how to optimize estimation of FCNs for cognitive and behavioral study.
Collapse
|
20
|
A framework for second-order eigenvector centralities and clustering coefficients. Proc Math Phys Eng Sci 2020; 476:20190724. [PMID: 32398932 PMCID: PMC7209141 DOI: 10.1098/rspa.2019.0724] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/28/2019] [Accepted: 03/10/2020] [Indexed: 11/12/2022] Open
Abstract
We propose and analyse a general tensor-based framework for incorporating second-order features into network measures. This approach allows us to combine traditional pairwise links with information that records whether triples of nodes are involved in wedges or triangles. Our treatment covers classical spectral methods and recently proposed cases from the literature, but we also identify many interesting extensions. In particular, we define a mutually reinforcing (spectral) version of the classical clustering coefficient. The underlying object of study is a constrained nonlinear eigenvalue problem associated with a cubic tensor. Using recent results from nonlinear Perron-Frobenius theory, we establish existence and uniqueness under appropriate conditions, and show that the new spectral measures can be computed efficiently with a nonlinear power method. To illustrate the added value of the new formulation, we analyse the measures on a class of synthetic networks. We also give computational results on centrality and link prediction for real-world networks.
Collapse
|
21
|
RWHMDA: Random Walk on Hypergraph for Microbe-Disease Association Prediction. Front Microbiol 2019; 10:1578. [PMID: 31354672 PMCID: PMC6635699 DOI: 10.3389/fmicb.2019.01578] [Citation(s) in RCA: 13] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Key Words] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/16/2019] [Accepted: 06/25/2019] [Indexed: 12/12/2022] Open
Abstract
Based on advancements in deep sequencing technology and microbiology, increasing evidence indicates that microbes inhabiting humans modulate various host physiological phenomena, thus participating in various disease pathogeneses. Owing to increasing availability of biological data, further studies on the establishment of efficient computational models for predicting potential associations are required. In particular, computational approaches can also reduce the discovery cycle of novel microbe-disease associations and further facilitate disease treatment, drug design, and other scientific activities. This study aimed to develop a model based on the random walk on hypergraph for microbe-disease association prediction (RWHMDA). As a class of higher-order data representation, hypergraph could effectively recover information loss occurring in the normal graph methodology, thus exclusively illustrating multiple pair-wise associations. Integrating known microbe-disease associations in the Human Microbe-Disease Association Database (HMDAD) and the Gaussian interaction profile kernel similarity for microbes, random walk was then implemented for the constructed hypergraph. Consequently, RWHMDA performed optimally in predicting the underlying disease-associated microbes. More specifically, our model displayed AUC values of 0.8898 and 0.8524 in global and local leave-one-out cross-validation (LOOCV), respectively. Furthermore, three human diseases (asthma, Crohn's disease, and type 2 diabetes) were studied to further illustrate prediction performance. Moreover, 8, 10, and 8 of the 10 highest ranked microbes were confirmed through recent experimental or clinical studies. In conclusion, RWHMDA is expected to display promising potential to predict disease-microbe associations for follow-up experimental studies and facilitate the prevention, diagnosis, treatment, and prognosis of complex human diseases.
Collapse
|
22
|
A Hypergraph-Based Blockchain Model and Application in Internet of Things-Enabled Smart Homes. SENSORS 2018; 18:s18092784. [PMID: 30149523 PMCID: PMC6164253 DOI: 10.3390/s18092784] [Citation(s) in RCA: 52] [Impact Index Per Article: 8.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 07/11/2018] [Revised: 08/20/2018] [Accepted: 08/21/2018] [Indexed: 11/27/2022]
Abstract
With the fast development and expansion of the Internet of Things (IoT), billions of smart devices are being continuously connected, and smart homes, as a typical IoT application, are providing people with various convenient applications, but face security and privacy issues. The idea of Blockchain (BC) theory has brought about a potential solution to the IoT security problem. The emergence of blockchain technology has brought about a change of decentralized management, providing an effective solution for the protection of network security and privacy. On the other hand, the smart devices in IoT are always lightweight and have less energy and memory. This makes the application of blockchain difficult. Against this background, this paper proposes a blockchain model based on hypergraphs. The aims of this model are to reduce the storage consumption and to solve the additional security issues. In the model, we use the hyperedge as the organization of storage nodes and convert the entire networked data storage into part network storage. We discuss the design of the model and security strategy in detail, introducing some use cases in a smart home network and evaluating the storage performance of the model through simulation experiments and an evaluation of the network.
Collapse
|
23
|
Abstract
Multi-modality data convey complementary information that can be used to improve the accuracy of prediction models in disease diagnosis. However, effectively integrating multi-modality data remains a challenging problem, especially when the data are incomplete. For instance, more than half of the subjects in the Alzheimer's disease neuroimaging initiative (ADNI) database have no fluorodeoxyglucose positron emission tomography and cerebrospinal fluid data. Currently, there are two commonly used strategies to handle the problem of incomplete data: 1) discard samples having missing features; and 2) impute those missing values via specific techniques. In the first case, a significant amount of useful information is lost and, in the second case, additional noise and artifacts might be introduced into the data. Also, previous studies generally focus on the pairwise relationships among subjects, without considering their underlying complex (e.g., high-order) relationships. To address these issues, in this paper, we propose a multi-hypergraph learning method for dealing with incomplete multimodality data. Specifically, we first construct multiple hypergraphs to represent the high-order relationships among subjects by dividing them into several groups according to the availability of their data modalities. A hypergraph regularized transductive learning method is then applied to these groups for automatic diagnosis of brain diseases. Extensive evaluation of the proposed method using all subjects in the baseline ADNI database indicates that our method achieves promising results in AD/MCI classification, compared with the state-of-the-art methods.
Collapse
|
24
|
Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs. PROCEEDINGS. ACM-SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA 2017; 2017:391-402. [PMID: 38425568 PMCID: PMC10902833 DOI: 10.1145/3035918.3035936] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 03/02/2024]
Abstract
In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it.
Collapse
|
25
|
Abstract
A hypergraph H = ( X , E ) is called a Menger System if the maximum cardinality of a family of pairwise disjoint edges (v 1(H)) is equal to the minimum cardinality of a subset of vertices which meets every edge (τ 0(H)). A set S ⊆ X is defined to be enclaveless if each vertex in S is adjacent to at least one vertex in X - S. A parameter π 0 related to the formation of maximal enclaveless sets is defined, and it is shown that if H has no singleton edges then v 1(H) ≤ π 0(H). MK-Systems are defined to be those hypergraphs H without singleton edges for which v 1(H) = π 0(H); simple graphs which are Menger Systems are shown also to be MK-Systems.
Collapse
|