Efficient and Exact Local Search for Random Walk Based Top-K Proximity Query in Large Graphs.
Ontology highlight
ABSTRACT:
SUBMITTER: Wu Y
PROVIDER: S-EPMC6411071 | biostudies-literature | 2016 May
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Branching processes are used to model diverse social and physical scenarios, from extinction of family names to nuclear fission. However, for a better description of natural phenomena, such as viral epidemics in cellular tissues, animal populations and social networks, a spatial embedding-the branching random walk (BRW)-is required. Despite its wide range of applications, the properties of the volume explored by the BRW so far remained elusive, with exact results limited to one dimension. Here we present analytical results, supported by numerical simulations, on the scaling of the volume explored by a BRW in the critical regime, the onset of epidemics, in general environments. Our results characterise the spreading dynamics on regular lattices and general graphs, such as fractals, random trees and scale-free networks, revealing the direct relation between the graphs' dimensionality and the rate of propagation of the viral process. Furthermore, we use the BRW to determine the spectral properties of real social and metabolic networks, where we observe that a lack of information of the network structure can lead to differences in the observed behaviour of the spreading process. Our results provide observables of broad interest for the characterisation of real world lattices, tissues, and networks.
| S-EPMC6821755 | biostudies-literature
Project description:Pharmacophore search is a key component of many drug discovery efforts. Pharmer is a new computational approach to pharmacophore search that scales with the breadth and complexity of the query, not the size of the compound library being screened. Two novel methods for organizing pharmacophore data, the Pharmer KDB-tree and Bloom fingerprints, enable Pharmer to perform an exact pharmacophore search of almost two million structures in less than a minute. In general, Pharmer is more than an order of magnitude faster than existing technologies. The complete source code is available under an open-source license at http://pharmer.sourceforge.net .
| S-EPMC3124593 | biostudies-literature
Project description:BACKGROUND:Functional modules in biological networks consist of numerous biomolecules and their complicated interactions. Recent studies have shown that biomolecules in a functional module tend to have similar interaction patterns and that such modules are often conserved across biological networks of different species. As a result, such conserved functional modules can be identified through comparative analysis of biological networks. RESULTS:In this work, we propose a novel network querying algorithm based on the CUFID (Comparative network analysis Using the steady-state network Flow to IDentify orthologous proteins) framework combined with an efficient seed-and-extension approach. The proposed algorithm, CUFID-query, can accurately detect conserved functional modules as small subnetworks in the target network that are expected to perform similar functions to the given query functional module. The CUFID framework was recently developed for probabilistic pairwise global comparison of biological networks, and it has been applied to pairwise global network alignment, where the framework was shown to yield accurate network alignment results. In the proposed CUFID-query algorithm, we adopt the CUFID framework and extend it for local network alignment, specifically to solve network querying problems. First, in the seed selection phase, the proposed method utilizes the CUFID framework to compare the query and the target networks and to predict the probabilistic node-to-node correspondence between the networks. Next, the algorithm selects and greedily extends the seed in the target network by iteratively adding nodes that have frequent interactions with other nodes in the seed network, in a way that the conductance of the extended network is maximally reduced. Finally, CUFID-query removes irrelevant nodes from the querying results based on the personalized PageRank vector for the induced network that includes the fully extended network and its neighboring nodes. CONCLUSIONS:Through extensive performance evaluation based on biological networks with known functional modules, we show that CUFID-query outperforms the existing state-of-the-art algorithms in terms of prediction accuracy and biological significance of the predictions.
| S-EPMC5751815 | biostudies-literature
Project description:MOTIVATION:With the wide availability of whole-genome genotype data, there is an increasing need for conducting genetic genealogical searches efficiently. Computationally, this task amounts to identifying shared DNA segments between a query individual and a very large panel containing millions of haplotypes. The celebrated Positional Burrows-Wheeler Transform (PBWT) data structure is a pre-computed index of the panel that enables constant time matching at each position between one haplotype and an arbitrarily large panel. However, the existing algorithm (Durbin's Algorithm 5) can only identify set-maximal matches, the longest matches ending at any location in a panel, while in real genealogical search scenarios, multiple 'good enough' matches are desired. RESULTS:In this work, we developed two algorithmic extensions of Durbin's Algorithm 5, that can find all L-long matches, matches longer than or equal to a given length L, between a query and a panel. In the first algorithm, PBWT-Query, we introduce 'virtual insertion' of the query into the PBWT matrix of the panel, and then scanning up and down for the PBWT match blocks with length greater than L. In our second algorithm, L-PBWT-Query, we further speed up PBWT-Query by introducing additional data structures that allow us to avoid iterating through blocks of incomplete matches. The efficiency of PBWT-Query and L-PBWT-Query is demonstrated using the simulated data and the UK Biobank data. Our results show that our proposed algorithms can detect related individuals for a given query efficiently in very large cohorts which enables a fast on-line query search. AVAILABILITY AND IMPLEMENTATION:genome.ucf.edu/pbwt-query. SUPPLEMENTARY INFORMATION:Supplementary data are available at Bioinformatics online.
| S-EPMC6612857 | biostudies-other
Project description:BackgroundThe probability of sequencing a set of RNA-seq reads can be directly modeled using the abundances of splice junctions in splice graphs instead of the abundances of a list of transcripts. We call this model graph quantification, which was first proposed by Bernard et al. (Bioinformatics 30:2447-55, 2014). The model can be viewed as a generalization of transcript expression quantification where every full path in the splice graph is a possible transcript. However, the previous graph quantification model assumes the length of single-end reads or paired-end fragments is fixed.ResultsWe provide an improvement of this model to handle variable-length reads or fragments and incorporate bias correction. We prove that our model is equivalent to running a transcript quantifier with exactly the set of all compatible transcripts. The key to our method is constructing an extension of the splice graph based on Aho-Corasick automata. The proof of equivalence is based on a novel reparameterization of the read generation model of a state-of-art transcript quantification method.ConclusionWe propose a new approach for graph quantification, which is useful for modeling scenarios where reference transcriptome is incomplete or not available and can be further used in transcriptome assembly or alternative splicing analysis.
| S-EPMC8112020 | biostudies-literature
Project description:In the past few decades, many ingenious efforts have been made in the development of free-energy simulation methods. Because complex systems often undergo nontrivial structural transition during state switching, achieving efficient free-energy calculation can be challenging. As identified earlier, the "Hamiltonian" lagging, which reveals the fact that necessary structural relaxation falls behind the order parameter move, has been a primary problem for generally low free-energy simulation efficiency. Here, we propose an algorithm by achieving a random walk in both the order parameter space and its generalized force space; thereby, the order parameter move and the required conformational relaxation can be efficiently synchronized. As demonstrated in both the alchemical transition and the conformational transition, a leapfrog improvement in free-energy simulation efficiency can be obtained; for instance, (i) it allows us to solve a notoriously challenging problem: accurately predicting the pK(a) value of a buried titratable residue, Asp-66, in the interior of the V66E staphylococcal nuclease mutant, and (ii) it allows us to gain superior efficiency over the metadynamics algorithm.
| S-EPMC2629259 | biostudies-literature
Project description:Restrictions to molecular motion by barriers (membranes) are ubiquitous in porous media, composite materials and biological tissues. A major challenge is to characterize the microstructure of a material or an organism nondestructively using a bulk transport measurement. Here we demonstrate how the long-range structural correlations introduced by permeable membranes give rise to distinct features of transport. We consider Brownian motion restricted by randomly placed and oriented membranes (d - 1 dimensional planes in d dimensions) and focus on the disorder-averaged diffusion propagator using a scattering approach. The renormalization group solution reveals a scaling behavior of the diffusion coefficient for large times, with a characteristically slow inverse square root time dependence for any d. Its origin lies in the strong structural fluctuations introduced by the spatially extended random restrictions, representing a novel universality class of the structural disorder. Our results agree well with Monte Carlo simulations in two dimensions. They can be used to identify permeable barriers as restrictions to transport, and to quantify their permeability and surface area.
| S-EPMC3114643 | biostudies-other
Project description:In quantum computing, the quantum walk search algorithm is designed for locating fixed marked nodes within a graph. However, when multiple marked nodes exist, the conventional search algorithm lacks the capacity to simultaneously amplify the marked nodes as well as identify the correct chronological ordering between the marked nodes, if any. To address this limitation, we explore a potential extension of the algorithm by introducing additional quantum states to label the marked nodes. The labels resolve the ambiguity of simultaneous amplification of the marked nodes. Additionally, by associating the label states with a chronological ordering, we can extend the algorithm to track a moving particle on a two-dimensional surface. Our algorithm efficiently searches for the trajectory of the particle and is supported by a proposed quantum circuit. This concept holds promise for a range of applications, from real-time object tracking to network management and routing.
| S-EPMC10837460 | biostudies-literature
Project description:Random walkers on a two-dimensional square lattice are used to explore the spatio-temporal growth of an epidemic. We have found that a simple random-walk system generates non-trivial dynamics compared with traditional well-mixed models. Phase diagrams characterizing the long-term behaviors of the epidemics are calculated numerically. The functional dependence of the basic reproductive number [Formula: see text] on the model's defining parameters reveals the role of spatial fluctuations and leads to a novel expression for [Formula: see text]. Special attention is given to simulations of inter-regional transmission of the contagion. The scaling of the epidemic with respect to space and time scales is studied in detail in the critical region, which is shown to be compatible with the directed-percolation universality class.
| S-EPMC8481482 | biostudies-literature
Project description:BackgroundThe use of internet search data has been demonstrated to be effective at predicting influenza incidence. This approach may be more successful for dengue which has large variation in annual incidence and a more distinctive clinical presentation and mode of transmission.MethodsWe gathered freely-available dengue incidence data from Singapore (weekly incidence, 2004-2011) and Bangkok (monthly incidence, 2004-2011). Internet search data for the same period were downloaded from Google Insights for Search. Search terms were chosen to reflect three categories of dengue-related search: nomenclature, signs/symptoms, and treatment. We compared three models to predict incidence: a step-down linear regression, generalized boosted regression, and negative binomial regression. Logistic regression and Support Vector Machine (SVM) models were used to predict a binary outcome defined by whether dengue incidence exceeded a chosen threshold. Incidence prediction models were assessed using r² and Pearson correlation between predicted and observed dengue incidence. Logistic and SVM model performance were assessed by the area under the receiver operating characteristic curve. Models were validated using multiple cross-validation techniques.ResultsThe linear model selected by AIC step-down was found to be superior to other models considered. In Bangkok, the model has an r² = 0.943, and a correlation of 0.869 between fitted and observed. In Singapore, the model has an r² = 0.948, and a correlation of 0.931. In both Singapore and Bangkok, SVM models outperformed logistic regression in predicting periods of high incidence. The AUC for the SVM models using the 75th percentile cutoff is 0.906 in Singapore and 0.960 in Bangkok.ConclusionsInternet search terms predict incidence and periods of large incidence of dengue with high accuracy and may prove useful in areas with underdeveloped surveillance systems. The methods presented here use freely available data and analysis tools and can be readily adapted to other settings.
| S-EPMC3149016 | biostudies-literature