ABSTRACT
Minimum spanning trees and forests are powerful sparsification techniques that remove cycles from weighted graphs to minimize total edge weight while preserving node reachability, with applications in computer science, network science, and graph theory. Despite their utility and ubiquity, they have several limitations, including that they are only defined for undirected networks, they significantly alter dynamics on networks, and they do not generally preserve important network features such as shortest distances, shortest path distribution, and community structure. In contrast, distance backbones, which are subgraphs formed by all edges that obey a generalized triangle inequality, are well defined in directed and undirected graphs and preserve those and other important network features. The backbone of a graph is defined with respect to a specified path-length operator that aggregates weights along a path to define its length, thereby associating a cost to indirect connections. The backbone is the union of all shortest paths between each pair of nodes according to the specified operator. One such operator, the max function, computes the length of a path as the largest weight of the edges that compose it (a weakest link criterion). It is the only operator that yields an algebraic structure for computing shortest paths that is consistent with De Morgan's laws. Applying this operator yields the ultrametric backbone of a graph in that (semi-triangular) edges whose weights are larger than the length of an indirect path connecting the same nodes (i.e. those that break the generalized triangle inequality based on max as a path-length operator) are removed. We show that the ultrametric backbone is the union of minimum spanning forests in undirected graphs and provides a new generalization of minimum spanning trees to directed graphs that, unlike minimum equivalent graphs and minimum spanning arborescences, preserves all max - min shortest paths and De Morgan's law consistency.
ABSTRACT
BACKGROUND: The co-administration of drugs known to interact greatly impacts morbidity, mortality, and health economics. This study aims to examine the drug-drug interaction (DDI) phenomenon with a large-scale longitudinal analysis of age and gender differences found in drug administration data from three distinct healthcare systems. METHODS: This study analyzes drug administrations from population-wide electronic health records in Blumenau (Brazil; 133 K individuals), Catalonia (Spain; 5.5 M individuals), and Indianapolis (USA; 264 K individuals). The stratified prevalences of DDI for multiple severity levels per patient gender and age at the time of administration are computed, and null models are used to estimate the expected impact of polypharmacy on DDI prevalence. Finally, to study actionable strategies to reduce DDI prevalence, alternative polypharmacy regimens using drugs with fewer known interactions are simulated. RESULTS: A large prevalence of co-administration of drugs known to interact is found in all populations, affecting 12.51%, 12.12%, and 10.06% of individuals in Blumenau, Indianapolis, and Catalonia, respectively. Despite very different healthcare systems and drug availability, the increasing prevalence of DDI as patients age is very similar across all three populations and is not explained solely by higher co-administration rates in the elderly. In general, the prevalence of DDI is significantly higher in women - with the exception of men over 50 years old in Indianapolis. Finally, we show that using proton pump inhibitor alternatives to omeprazole (the drug involved in more co-administrations in Catalonia and Blumenau), the proportion of patients that are administered known DDI can be reduced by up to 21% in both Blumenau and Catalonia and 2% in Indianapolis. CONCLUSIONS: DDI administration has a high incidence in society, regardless of geographic, population, and healthcare management differences. Although DDI prevalence increases with age, our analysis points to a complex phenomenon that is much more prevalent than expected, suggesting comorbidities as key drivers of the increase. Furthermore, the gender differences observed in most age groups across populations are concerning in regard to gender equity in healthcare. Finally, our study exemplifies how electronic health records' analysis can lead to actionable interventions that significantly reduce the administration of known DDI and its associated human and economic costs.
Subject(s)
Polypharmacy , Male , Humans , Female , Aged , Middle Aged , Pharmaceutical Preparations , Prevalence , Drug Interactions , ComorbidityABSTRACT
In weighted graphs the shortest path between two nodes is often reached through an indirect path, out of all possible connections, leading to structural redundancies which play key roles in the dynamics and evolution of complex networks. We have previously developed a parameter-free, algebraically-principled methodology to uncover such redundancy and reveal the distance backbone of weighted graphs, which has been shown to be important in transmission dynamics, inference of important paths, and quantifying the robustness of networks. However, the method was developed for undirected graphs. Here we expand this methodology to weighted directed graphs and study the redundancy and robustness found in nine networks ranging from social, biomedical, and technical systems. We found that similarly to undirected graphs, directed graphs in general also contain a large amount of redundancy, as measured by the size of their (directed) distance backbone. Our methodology adds an additional tool to the principled sparsification of complex networks and the measure of their robustness.
ABSTRACT
Epilepsy is a common chronic neurological disease. People with epilepsy (PWE) and their caregivers face several challenges related to their epilepsy management, including quality of care, care coordination, side effects, and stigma management. The sociotechnical issues of the information management contexts and challenges for epilepsy care may be mitigated through effective information management. We conducted 4 focus groups with 5 PWE and 7 caregivers to explore how they manage epilepsy-related information and the challenges they encountered. Primary issues include challenges of finding the right information, complexities of tracking and monitoring data, and limited information sharing. We provide a framework that encompasses three attributes - individual epilepsy symptoms and health conditions, information complexity, and circumstantial constraints. We suggest future design implications to mitigate these challenges and improve epilepsy information management and care coordination.
ABSTRACT
Given the large size and complexity of most biochemical regulation and signaling networks, there is a non-trivial relationship between the micro-level logic of component interactions and the observed macro-dynamics. Here we address this issue by formalizing the concept of pathway modules developed by Marques-Pita and Rocha [1], which are sequences of state updates that are guaranteed to occur (barring outside interference) in the causal dynamics of automata networks after the perturbation of a subset of driver nodes. We present a novel algorithm to automatically extract pathway modules from networks and characterize the interactions that may take place between the modules. This methodology uses only the causal logic of individual node variables (micro-dynamics) without the need to compute the dynamical landscape of the networks (macro-dynamics). Specifically, we identify complex modules, which maximize pathway length and require synergy between their components. This allows us to propose a new take on dynamical modularity that partitions complex networks into causal pathways of variables that are guaranteed to transition to specific dynamical states given a perturbation to a set of driver nodes. Thus, the same node variable can take part in distinct modules depending on the state it takes. Our measure of dynamical modularity of a network is then inversely proportional to the overlap among complex modules and maximal when complex modules are completely decouplable from one another in the network dynamics. We estimate dynamical modularity for several genetic regulatory networks, including the full Drosophila melanogaster segment-polarity network. We discuss how identifying complex modules and the dynamical modularity portrait of networks explains the macro-dynamics of biological networks, such as uncovering the (more or less) decouplable building blocks of emergent computation (or collective behavior) in biochemical regulation and signaling.
ABSTRACT
The structure of social networks strongly affects how different phenomena spread in human society, from the transmission of information to the propagation of contagious diseases. It is well-known that heterogeneous connectivity strongly favors spread, but a precise characterization of the redundancy present in social networks and its effect on the robustness of transmission is still lacking. This gap is addressed by the metric backbone, a weight- and connectivity-preserving subgraph that is sufficient to compute all shortest paths of weighted graphs. This subgraph is obtained via algebraically-principled axioms and does not require statistical sampling based on null-models. We show that the metric backbones of nine contact networks obtained from proximity sensors in a variety of social contexts are generally very small, 49% of the original graph for one and ranging from about 6% to 20% for the others. This reflects a surprising amount of redundancy and reveals that shortest paths on these networks are very robust to random attacks and failures. We also show that the metric backbone preserves the full distribution of shortest paths of the original contact networks-which must include the shortest inter- and intra-community distances that define any community structure-and is a primary subgraph for epidemic transmission based on pure diffusion processes. This suggests that the organization of social contact networks is based on large amounts of shortest-path redundancy which shapes epidemic spread in human populations. Thus, the metric backbone is an important subgraph with regard to epidemic spread, the robustness of social networks, and any communication dynamics that depend on complex network shortest paths.
Subject(s)
Communicable Diseases , Epidemics , Humans , Communicable Diseases/epidemiology , Social Networking , CommunicationABSTRACT
The co-administration of drugs known to interact has a high impact on morbidity, mortality, and health economics. We study the drug-drug interaction (DDI) phenomenon by analyzing drug administrations from population-wide Electronic Health Records (EHR) in Blumenau (Brazil), Catalonia (Spain), and Indianapolis (USA). Despite very different health care systems and drug availability, we find a common large risk of DDI administration that affected 13 to 20% of patients in these populations. In addition, the increasing risk of DDI as patients age is very similar across all three populations but is not explained solely by higher co-administration rates in the elderly. We also find that women are at higher risk of DDI overall- except for men over 50 years old in Indianapolis. Finally, we show that PPI alternatives to Omeprazole can reduce the number of patients affected by known DDIs by up to 21% in both Blumenau and Catalonia, and 2% in Indianapolis, exemplifying how analysis of EHR data can lead to a significant reduction of DDI and its associated human and economic costs. Although the risk of DDIs increases with age, administration patterns point to a complex phenomenon that cannot be solely explained by polypharmacy and multimorbidity. The lack of safer drug alternatives, particularly for chronic conditions, further overburdens health systems, thus highlighting the need for disruptive drug research.
ABSTRACT
Biomolecular network dynamics are thought to operate near the critical boundary between ordered and disordered regimes, where large perturbations to a small set of elements neither die out nor spread on average. A biomolecular automaton (e.g., gene, protein) typically has high regulatory redundancy, where small subsets of regulators determine activation via collective canalization. Previous work has shown that effective connectivity, a measure of collective canalization, leads to improved dynamical regime prediction for homogeneous automata networks. We expand this by (i) studying random Boolean networks (RBNs) with heterogeneous in-degree distributions, (ii) considering additional experimentally validated automata network models of biomolecular processes, and (iii) considering new measures of heterogeneity in automata network logic. We found that effective connectivity improves dynamical regime prediction in the models considered; in RBNs, combining effective connectivity with bias entropy further improves the prediction. Our work yields a new understanding of criticality in biomolecular networks that accounts for collective canalization, redundancy, and heterogeneity in the connectivity and logic of their automata models. The strong link we demonstrate between criticality and regulatory redundancy provides a means to modulate the dynamical regime of biochemical networks.
ABSTRACT
Complex living systems are thought to exist at the "edge of chaos" separating the ordered dynamics of robust function from the disordered dynamics of rapid environmental adaptation. Here, a deeper inspection of 72 experimentally supported discrete dynamical models of cell processes reveals previously unobserved order on long time scales, suggesting greater rigidity in these systems than was previously conjectured. We find that propagation of internal perturbations is transient in most cases, and that even when large perturbation cascades persist, their phenotypic effects are often minimal. Moreover, we find evidence that stochasticity and desynchronization can lead to increased recovery from regulatory perturbation cascades. Our analysis relies on new measures that quantify the tendency of perturbations to spread through a discrete dynamical system. Computing these measures was not feasible using current methodology; thus, we developed a multipurpose CUDA-based simulation tool, which we have made available as the open-source Python library cubewalkers. Based on novel measures and simulations, our results suggest that-contrary to current theory-cell processes are ordered and far from the edge of chaos.
ABSTRACT
The optimization problem aiming at the identification of minimal sets of nodes able to drive the dynamics of Boolean networks toward desired long-term behaviors is central for some applications, as for example the detection of key therapeutic targets to control pathways in models of biological signaling and regulatory networks. Here, we develop a method to solve such an optimization problem taking inspiration from the well-studied problem of influence maximization for spreading processes in social networks. We validate the method on small gene regulatory networks whose dynamical landscapes are known by means of brute-force analysis. We then systematically study a large collection of gene regulatory networks. We find that for about 65% of the analyzed networks, the minimal driver sets contain less than 20% of their nodes.
Subject(s)
Algorithms , Gene Regulatory Networks , Social NetworkingABSTRACT
The discovery of drug-drug interactions (DDIs) that have a translational impact among in vitro pharmacokinetics (PK), in vivo PK and clinical outcomes depends largely on the quality of the annotated corpus available for text mining. We have developed a new DDI corpus based on an annotation scheme that builds upon and extends previous ones, where an abstract is fragmented and each fragment is then annotated along eight dimensions, namely, focus, polarity, certainty, evidence, directionality, study type, interaction type and mechanism. The guideline for defining these dimensions has undergone refinement during the annotation process. Our DDI corpus comprises 900 positive DDI abstracts and 750 that are not directly relevant to DDI. The abstracts in corpus are separated into eight categories of DDI or non-DDI evidence: DDI with pharmacokinetic (PK) mechanism, in vivo DDI PK, DDI clinical, drug-nutrition interaction, single drug, not drug related, in vitro pharmacodynamic (PD) and case report. Seven annotators, three annotators with drug-interaction research experience and four annotators with less drug-interaction research experience independently annotated the DDI corpus, where two researchers independently annotated each abstract. After two rounds of annotations with additional training in between, agreement improved from (0.79, 0.96, 0.86, 0.70, 0.91, 0.65, 0.78, 0.90) to (0.93, 0.99, 0.96, 0.94, 0.95, 0.93, 0.96, 0.97) for focus, certainty, evidence, study type, interaction type, mechanisms, polarity and direction, respectively. The novice-level annotators improved from 0.83 to 0.96, while the expert-level annotators stayed in high performance with some improvement, from 0.90 to 0.96. In summary, we achieved 96% agreement among each pair of annotators with regard to the eight dimensions. The annotated corpus is now available to the community for inclusion in their text-mining pipelines. Database URL https://github.com/zha204/DDI-Corpus-Database/tree/master/DDI%20corpus.
Subject(s)
Data Mining , Data Mining/methods , Databases, Factual , Drug Interactions , HumansABSTRACT
Sudden Unexpected Death in Epilepsy (SUDEP) remains a leading cause of death in people with epilepsy. Despite the constant risk for patients and bereavement to family members, to date the physiological mechanisms of SUDEP remain unknown. Here we explore the potential to identify putative predictive signals of SUDEP from online digital behavioral data using text and sentiment analysis tools. Specifically, we analyze Facebook timelines of six patients with epilepsy deceased due to SUDEP, donated by surviving family members. We find preliminary evidence for behavioral changes detectable by text and sentiment analysis tools. Namely, in the months preceding their SUDEP event patient social media timelines show: i) increase in verbosity; ii) increased use of functional words; and iii) sentiment shifts as measured by different sentiment analysis tools. Combined, these results suggest that social media engagement, as well as its sentiment, may serve as possible early-warning signals for SUDEP in people with epilepsy. While the small sample of patient timelines analyzed in this study prevents generalization, our preliminary investigation demonstrates the potential of social media data as complementary data in larger studies of SUDEP and epilepsy.
Subject(s)
Epilepsy , Social Media , Sudden Unexpected Death in Epilepsy , Cohort Studies , Death, Sudden/etiology , Death, Sudden/prevention & control , Epilepsy/complications , Humans , Risk FactorsABSTRACT
Living systems comprise interacting biochemical components in very large networks. Given their high connectivity, biochemical dynamics are surprisingly not chaotic but quite robust to perturbations-a feature C.H. Waddington named canalization. Because organisms are also flexible enough to evolve, they arguably operate in a critical dynamical regime between order and chaos. The established theory of criticality is based on networks of interacting automata where Boolean truth values model presence/absence of biochemical molecules. The dynamical regime is predicted using network connectivity and node bias (to be on/off) as tuning parameters. Revising this to account for canalization leads to a significant improvement in dynamical regime prediction. The revision is based on effective connectivity, a measure of dynamical redundancy that buffers automata response to some inputs. In both random and experimentally validated systems biology networks, reducing effective connectivity makes living systems operate in stable or critical regimes even though the structure of their biochemical interaction networks predicts them to be chaotic. This suggests that dynamical redundancy may be naturally selected to maintain living systems near critical dynamics, providing both robustness and evolvability. By identifying how dynamics propagates preferably via effective pathways, our approach helps to identify precise ways to design and control network models of biochemical regulation and signalling.
Subject(s)
Systems BiologyABSTRACT
There are over three million people living with epilepsy in the U.S. People with epilepsy experience multiple daily challenges such as seizures, social isolation, social stigma, experience of physical and emotional symptoms, medication side effects, cognitive and memory deficits, care coordination difficulties, and risks of sudden unexpected death. In this work, we report findings collected from 3 focus groups of 11 people with epilepsy and caregivers and 10 follow-up questionnaires. We found that these participants feel that most people do not know how to deal with seizures. To improve others' abilities to respond safely and appropriately to someone having seizures, people with epilepsy and caregivers would like to share and educate the public about their epilepsy conditions, reduce common misconceptions about seizures and prevent associated stigma, and get first aid help from the public when needed. Considering social stigma, we propose design implications of future technologies for effective delivery of appropriate first aid care information to bystanders around individuals with epilepsy when they experience a seizure.
ABSTRACT
The ability to map causal interactions underlying genetic control and cellular signaling has led to increasingly accurate models of the complex biochemical networks that regulate cellular function. These network models provide deep insights into the organization, dynamics, and function of biochemical systems: for example, by revealing genetic control pathways involved in disease. However, the traditional representation of biochemical networks as binary interaction graphs fails to accurately represent an important dynamical feature of these multivariate systems: some pathways propagate control signals much more effectively than do others. Such heterogeneity of interactions reflects canalization-the system is robust to dynamical interventions in redundant pathways but responsive to interventions in effective pathways. Here, we introduce the effective graph, a weighted graph that captures the nonlinear logical redundancy present in biochemical network regulation, signaling, and control. Using 78 experimentally validated models derived from systems biology, we demonstrate that 1) redundant pathways are prevalent in biological models of biochemical regulation, 2) the effective graph provides a probabilistic but precise characterization of multivariate dynamics in a causal graph form, and 3) the effective graph provides an accurate explanation of how dynamical perturbation and control signals, such as those induced by cancer drug therapies, propagate in biochemical pathways. Overall, our results indicate that the effective graph provides an enriched description of the structure and dynamics of networked multivariate causal interactions. We demonstrate that it improves explainability, prediction, and control of complex dynamical systems in general and biochemical regulation in particular.
Subject(s)
Biological Phenomena , Models, Biological , Software , Gene Regulatory Networks , Metabolic Networks and Pathways , Signal TransductionABSTRACT
Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges-those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy.
ABSTRACT
Social media data have been increasingly used to study biomedical and health-related phenomena. From cohort-level discussions of a condition to population-level analyses of sentiment, social media have provided scientists with unprecedented amounts of data to study human behavior associated with a variety of health conditions and medical treatments. Here we review recent work in mining social media for biomedical, epidemiological, and social phenomena information relevant to the multilevel complexity of human health. We pay particular attention to topics where social media data analysis has shown the most progress, including pharmacovigilance and sentiment analysis, especially for mental health. We also discuss a variety of innovative uses of social media data for health-related applications as well as important limitations of social media data access and use.
ABSTRACT
Clinical translation of drug-drug interaction (DDI) studies is limited, and knowledge gaps across different types of DDI evidence make it difficult to consolidate and link them to clinical consequences. Consequently, we developed information retrieval (IR) models to retrieve DDI and drug-gene interaction (DGI) evidence from 25 million PubMed abstracts and distinguish DDI evidence into in vitro pharmacokinetic (PK), clinical PK, and clinical pharmacodynamic (PD) studies for US Food and Drug Administration (FDA) approved and withdrawn drugs. Additionally, information extraction models were developed to extract DDI-pairs and DGI-pairs from the IR-retrieved abstracts. An overlapping analysis identified 986 unique DDI-pairs between all 3 types of evidence. Another 2,157 and 13,012 DDI-pairs and 3,173 DGI-pairs were identified from known clinical PK/PD DDI, clinical PD DDI, and DGI evidence, respectively. By integrating DDI and DGI evidence, we discovered 119 and 18 new pharmacogenetic hypotheses associated with CYP3A and CYP2D6, respectively. Some of these DGI evidence can also aid us in understanding DDI mechanisms.
Subject(s)
Data Mining/methods , Drug Interactions/physiology , Knowledge Discovery/methods , Pharmacogenetics/methods , Translational Research, Biomedical/methods , United States Food and Drug Administration , Data Mining/trends , Humans , Pharmacogenetics/trends , Translational Research, Biomedical/trends , United States , United States Food and Drug Administration/trendsABSTRACT
The occurrence of drug-drug-interactions (DDI) from multiple drug dispensations is a serious problem, both for individuals and health-care systems, since patients with complications due to DDI are likely to reenter the system at a costlier level. We present a large-scale longitudinal study (18 months) of the DDI phenomenon at the primary- and secondary-care level using electronic health records (EHR) from the city of Blumenau in Southern Brazil (pop. ≈340,000). We found that 181 distinct drug pairs known to interact were dispensed concomitantly to 12% of the patients in the city's public health-care system. Further, 4% of the patients were dispensed drug pairs that are likely to result in major adverse drug reactions (ADR)-with costs estimated to be much larger than previously reported in smaller studies. The large-scale analysis reveals that women have a 60% increased risk of DDI as compared to men; the increase becomes 90% when considering only DDI known to lead to major ADR. Furthermore, DDI risk increases substantially with age; patients aged 70-79 years have a 34% risk of DDI when they are dispensed two or more drugs concomitantly. Interestingly, a statistical null model demonstrates that age- and female-specific risks from increased polypharmacy fail by far to explain the observed DDI risks in those populations, suggesting unknown social or biological causes. We also provide a network visualization of drugs and demographic factors that characterize the DDI phenomenon and demonstrate that accurate DDI prediction can be included in health care and public-health management, to reduce DDI-related ADR and costs.