Dynamic graphs, community detection, and Riemannian geometry.
Ontology highlight
ABSTRACT:
SUBMITTER: Bakker C
PROVIDER: S-EPMC6214282 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Inter-temporal decisions involves assigning values to various payoffs occurring at different temporal distances. Past research has used different approaches to study these decisions made by humans and animals. For instance, considering that people discount future payoffs at a constant rate (e.g., exponential discounting) or at variable rate (e.g., hyperbolic discounting). In this research, we question the widely assumed, but seldom questioned, notion across many of the existing approaches that the decision space, where the decision-maker perceives time and monetary payoffs, is a Euclidean space. By relaxing the rigid assumption of Euclidean space, we propose that the decision space is a more flexible Riemannian space of Constant Negative Curvature. We test our proposal by deriving a discount function, which uses the distance in the Negative Curvature space instead of Euclidean temporal distance. The distance function includes both perceived values of time as well as money, unlike past work which has considered just time. By doing so we are able to explain many of the empirical findings in inter-temporal decision-making literature. We provide converging evidence for our proposal by estimating the curvature of the decision space utilizing manifold learning algorithm and showing that the characteristics (i.e., metric properties) of the decision space resembles those of the Negative Curvature space rather than the Euclidean space. We conclude by presenting new theoretical predictions derived from our proposal and implications for how non-normative behavior is defined.
| S-EPMC4809573 | biostudies-literature
Project description:When non-linear models are fitted to experimental data, parameter estimates can be poorly constrained albeit being identifiable in principle. This means that along certain paths in parameter space, the log-likelihood does not exceed a given statistical threshold but remains bounded. This situation, denoted as practical non-identifiability, can be detected by Monte Carlo sampling or by systematic scanning using the profile likelihood method. In contrast, any method based on a Taylor expansion of the log-likelihood around the optimum, e.g., parameter uncertainty estimation by the Fisher Information Matrix, reveals no information about the boundedness at all. In this work, we present a geometric approach, approximating the original log-likelihood by geodesic coordinates of the model manifold. The Christoffel Symbols in the geodesic equation are fixed to those obtained from second order model sensitivities at the optimum. Based on three exemplary non-linear models we show that the information about the log-likelihood bounds and flat parameter directions can already be contained in this local information. Whereas the unbounded case represented by the Fisher Information Matrix is embedded in the geometric framework as vanishing Christoffel Symbols, non-vanishing constant Christoffel Symbols prove to define prototype non-linear models featuring boundedness and flat parameter directions of the log-likelihood. Finally, we investigate if those models could allow to approximate and replace computationally expensive objective functions originating from non-linear models by a surrogate objective function in parameter estimation problems.
| S-EPMC6546239 | biostudies-literature
Project description:BackgroundIdentification of transcription factor binding sites (also called 'motif discovery') in DNA sequences is a basic step in understanding genetic regulation. Although many successful programs have been developed, the problem is far from being solved on account of diversity in gene expression/regulation and the low specificity of binding sites. State-of-the-art algorithms have their own constraints (e.g., high time or space complexity for finding long motifs, low precision in identification of weak motifs, or the OOPS constraint: one occurrence of the motif instance per sequence) which limit their scope of application.ResultsIn this paper, we present a novel and fast algorithm we call TFBSGroup. It is based on community detection from a graph and is used to discover long and weak (l,d) motifs under the ZOMOPS constraint (zero, one or multiple occurrence(s) of the motif instance(s) per sequence), where l is the length of a motif and d is the maximum number of mutations between a motif instance and the motif itself. Firstly, TFBSGroup transforms the (l, d) motif search in sequences to focus on the discovery of dense subgraphs within a graph. It identifies these subgraphs using a fast community detection method for obtaining coarse-grained candidate motifs. Next, it greedily refines these candidate motifs towards the true motif within their own communities. Empirical studies on synthetic (l, d) samples have shown that TFBSGroup is very efficient (e.g., it can find true (18, 6), (24, 8) motifs within 30 seconds). More importantly, the algorithm has succeeded in rapidly identifying motifs in a large data set of prokaryotic promoters generated from the Escherichia coli database RegulonDB. The algorithm has also accurately identified motifs in ChIP-seq data sets for 12 mouse transcription factors involved in ES cell pluripotency and self-renewal.ConclusionsOur novel heuristic algorithm, TFBSGroup, is able to quickly identify nearly exact matches for long and weak (l, d) motifs in DNA sequences under the ZOMOPS constraint. It is also capable of finding motifs in real applications. The source code for TFBSGroup can be obtained from http://bioinformatics.bioengr.uic.edu/TFBSGroup/.
| S-EPMC3726413 | biostudies-literature
Project description:Riemannian geometry-based classification (RGBC) gained popularity in the field of brain-computer interfaces (BCIs) lately, due to its ability to deal with non-stationarities arising in electroencephalography (EEG) data. Domain adaptation, however, is most often performed on sample covariance matrices (SCMs) obtained from EEG data, and thus might not fully account for components affecting covariance estimation itself, such as regional trends. Detrended cross-correlation analysis (DCCA) can be utilized to estimate the covariance structure of such signals, yet it is computationally expensive in its original form. A recently proposed online implementation of DCCA, however, allows for its fast computation and thus makes it possible to employ DCCA in real-time applications. In this study we propose to replace the SCM with the DCCA matrix as input to RGBC and assess its effect on offline and online BCI performance. First we evaluated the proposed decoding pipeline offline on previously recorded EEG data from 18 individuals performing left and right hand motor imagery (MI), and benchmarked it against vanilla RGBC and popular MI-detection approaches. Subsequently, we recruited eight participants (with previous BCI experience) who operated an MI-based BCI (MI-BCI) online using the DCCA-enhanced Riemannian decoder. Finally, we tested the proposed method on a public, multi-class MI-BCI dataset. During offline evaluations the DCCA-based decoder consistently and significantly outperformed the other approaches. Online evaluation confirmed that the DCCA matrix could be computed in real-time even for 22-channel EEG, as well as subjects could control the MI-BCI with high command delivery (normalized Cohen's κ: 0.7409 ± 0.1515) and sample-wise MI detection (normalized Cohen's κ: 0.5200 ± 0.1610). Post-hoc analysis indicated characteristic connectivity patterns under both MI conditions, with stronger connectivity in the hemisphere contralateral to the MI task. Additionally, fractal scaling exponent of neural activity was found increased in the contralateral compared to the ipsilateral motor cortices (C4 and C3 for left and right MI, respectively) in both classes. Combining DCCA with Riemannian geometry-based decoding yields a robust and effective decoder, that not only improves upon the SCM-based approach but can also provide relevant information on the neurophysiological processes behind MI.
| S-EPMC10973000 | biostudies-literature
Project description:Many systems exhibit complex temporal dynamics due to the presence of different processes taking place simultaneously. An important task in these systems is to extract a simplified view of their time-dependent network of interactions. Community detection in temporal networks usually relies on aggregation over time windows or consider sequences of different stationary epochs. For dynamics-based methods, attempts to generalize static-network methodologies also face the fundamental difficulty that a stationary state of the dynamics does not always exist. Here, we derive a method based on a dynamical process evolving on the temporal network. Our method allows dynamics that do not reach a steady state and uncovers two sets of communities for a given time interval that accounts for the ordering of edges in forward and backward time. We show that our method provides a natural way to disentangle the different dynamical scales present in a system with synthetic and real-world examples.
| S-EPMC9094665 | biostudies-literature
Project description:We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations ("optimization variance") and over randomizations of network structure ("randomization variance"). Because the modularity quality function typically has a large number of nearly degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.
| S-EPMC3618100 | biostudies-other
Project description:Most high-dimensional datasets are thought to be inherently low-dimensional-that is, data points are constrained to lie on a low-dimensional manifold embedded in a high-dimensional ambient space. Here, we study the viability of two approaches from differential geometry to estimate the Riemannian curvature of these low-dimensional manifolds. The intrinsic approach relates curvature to the Laplace-Beltrami operator using the heat-trace expansion and is agnostic to how a manifold is embedded in a high-dimensional space. The extrinsic approach relates the ambient coordinates of a manifold's embedding to its curvature using the Second Fundamental Form and the Gauss-Codazzi equation. We found that the intrinsic approach fails to accurately estimate the curvature of even a two-dimensional constant-curvature manifold, whereas the extrinsic approach was able to handle more complex toy models, even when confounded by practical constraints like small sample sizes and measurement noise. To test the applicability of the extrinsic approach to real-world data, we computed the curvature of a well-studied manifold of image patches and recapitulated its topological classification as a Klein bottle. Lastly, we applied the extrinsic approach to study single-cell transcriptomic sequencing (scRNAseq) datasets of blood, gastrulation, and brain cells to quantify the Riemannian curvature of scRNAseq manifolds.
| S-EPMC8307776 | biostudies-literature
Project description:We show how quantum many-body systems on hyperbolic lattices with nearest-neighbor hopping and local interactions can be mapped onto quantum field theories in continuous negatively curved space. The underlying lattices have recently been realized experimentally with superconducting resonators and therefore allow for a table-top quantum simulation of quantum physics in curved background. Our mapping provides a computational tool to determine observables of the discrete system even for large lattices, where exact diagonalization fails. As an application and proof of principle we quantitatively reproduce the ground state energy, spectral gap, and correlation functions of the noninteracting lattice system by means of analytic formulas on the Poincaré disk, and show how conformal symmetry emerges for large lattices. This sets the stage for studying interactions and disorder on hyperbolic graphs in the future. Importantly, our analysis reveals that even relatively small discrete hyperbolic lattices emulate the continuous geometry of negatively curved space, and thus can be used to experimentally resolve fundamental open problems at the interface of interacting many-body systems, quantum field theory in curved space, and quantum gravity.
| S-EPMC8204532 | biostudies-literature
Project description:MotivationThe de Bruijn graph has become a ubiquitous graph model for biological data ever since its initial introduction in the late 1990s. It has been used for a variety of purposes including genome assembly (Zerbino and Birney, 2008; Bankevich et al., 2012; Peng et al., 2012), variant detection (Alipanahi et al., 2020b; Iqbal et al., 2012), and storage of assembled genomes (Chikhi et al., 2016). For this reason, there have been over a dozen methods for building and representing the de Bruijn graph and its variants in a space and time efficient manner.ResultsWith the exception of a few data structures (Muggli et al., 2019; Holley and Melsted, 2020; Crawford et al.,2018), compressed and compact de Bruijn graphs do not allow for the graph to be efficiently updated, meaning that data can be added or deleted. The most recent compressed dynamic de Bruijn graph (Alipanahi et al., 2020a), relies on dynamic bit vectors which are slow in theory and practice. To address this shortcoming, we present a compressed dynamic de Bruijn graph that removes the necessity of dynamic bit vectors by buffering data that should be added or removed from the graph. We implement our method, which we refer to as BufBOSS, and compare its performance to Bifrost, DynamicBOSS, and FDBG. Our experiments demonstrate that BufBOSS achieves attractive trade-offs compared to other tools in terms of time, memory and disk, and has the best deletion performance by an order of magnitude.
| S-EPMC8326735 | biostudies-literature
Project description:Many evolving complex real-world systems can be modeled via dynamic networks. An important problem in dynamic network research is community detection, which finds groups of topologically related nodes. Typically, this problem is approached by assuming either that each time point has a distinct community organization or that all time points share a single community organization. The reality likely lies between these two extremes. To find the compromise, we consider community detection in the context of the problem of segment detection, which identifies contiguous time periods with consistent network structure. Consequently, we formulate a combined problem of segment community detection (SCD), which simultaneously partitions the network into contiguous time segments with consistent community organization and finds this community organization for each segment. To solve SCD, we introduce SCOUT, an optimization framework that explicitly considers both segmentation quality and partition quality. SCOUT addresses limitations of existing methods that can be adapted to solve SCD, which consider only one of segmentation quality or partition quality. In a thorough evaluation, SCOUT outperforms the existing methods in terms of both accuracy and computational complexity. We apply SCOUT to biological network data to study human aging.
| S-EPMC5121586 | biostudies-literature