An efficient algorithm for maximizing range sum queries in a road network.
Ontology highlight
ABSTRACT:
SUBMITTER: Phan TK
PROVIDER: S-EPMC4135146 | biostudies-other | 2014
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Efficient large-scale annotation of genomic intervals is essential for personal genome interpretation in the realm of precision medicine. There are 13 possible relations between two intervals according to Allen's interval algebra. Conventional interval trees are routinely used to identify the genomic intervals satisfying a coarse relation with a query interval, but cannot support efficient query for more refined relations such as all Allen's relations. We design and implement a novel approach to address this unmet need. Through rewriting Allen's interval relations, we transform an interval query to a range query, then adapt and utilize the range trees for querying. We implement two types of range trees: a basic 2-dimensional range tree (2D-RT) and an augmented range tree with fractional cascading (RTFC) and compare them with the conventional interval tree (IT). Theoretical analysis shows that RTFC can achieve the best time complexity for interval queries regarding all Allen's relations among the three trees. We also perform comparative experiments on the efficiency of RTFC, 2D-RT and IT in querying noncoding element annotations in a large collection of personal genomes. Our experimental results show that 2D-RT is more efficient than IT for interval queries regarding most of Allen's relations, RTFC is even more efficient than 2D-RT. The results demonstrate that RTFC is an efficient data structure for querying large-scale datasets regarding Allen's relations between genomic intervals, such as those required by interpreting genome-wide variation in large populations.
| S-EPMC6434014 | biostudies-literature
Project description:Effective video monitoring systems require optimization of camera and road network coverage, to exploit fully the hardware and software solutions in smart city traffic applications. Monitoring requirements have grown increasingly diverse as scenes are becoming increasingly complex, thereby transforming the camera and road network coverage optimization issue into a nonlinear, high-dimension, and multi-objective problem. Previous research on this topic however, has focused on a single, specific optimization objective, which may result in invalid optimization results in actual applications. To extend this research, we propose a multi-objective scheduling optimization algorithm for a camera network that addresses the problem of directional road network coverage. In this solution, we incorporate an expanding parameter of main optical axes into particle swarm optimization algorithm. Our new strategy divides the range of main optical axes of all the cameras to control the scheduling number, achieving collaborative optimization of multiple objectives. In a simulated camera and road network, an experiment was designed for evaluating the effectiveness of the proposed method, comparing the distribution of optimization results with the global and local optimal solutions of the true value. A second experiment compared the distribution, performance and running time of the optimization results with different values of expanding parameter of main optical axes. A third experiment compared the performance of the optimization solutions with different values of camera parameters. The results showed that the proposed method can adapt to user application preference, and is effective and robust to schedule and allocate monitoring resources in different scenarios.
| S-EPMC6209222 | biostudies-literature
Project description:Outsourcing data and computation to cloud server provides a cost-effective way to support large scale data storage and query processing. However, due to security and privacy concerns, sensitive data (e.g., medical records) need to be protected from the cloud server and other unauthorized users. One approach is to outsource encrypted data to the cloud server and have the cloud server perform query processing on the encrypted data only. It remains a challenging task to support various queries over encrypted data in a secure and efficient way such that the cloud server does not gain any knowledge about the data, query, and query result. In this paper, we study the problem of secure skyline queries over encrypted data. The skyline query is particularly important for multi-criteria decision making but also presents significant challenges due to its complex computations. We propose a fully secure skyline query protocol on data encrypted using semantically-secure encryption. As a key subroutine, we present a new secure dominance protocol, which can be also used as a building block for other queries. Furthermore, we demonstrate two optimizations, data partitioning and lazy merging, to further reduce the computation load. Finally, we provide both serial and parallelized implementations and empirically study the protocols in terms of efficiency and scalability under different parameter settings, verifying the feasibility of our proposed solutions.
| S-EPMC6764829 | biostudies-literature
Project description:We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.
| S-EPMC3117351 | biostudies-literature
Project description:Most of the digital data transmitted are carried by optical fibres, forming the great part of the national and international communication infrastructure. The information-carrying capacity of these networks has increased vastly over the past decades through the introduction of wavelength division multiplexing, advanced modulation formats, digital signal processing and improved optical fibre and amplifier technology. These developments sparked the communication revolution and the growth of the Internet, and have created an illusion of infinite capacity being available. But as the volume of data continues to increase, is there a limit to the capacity of an optical fibre communication channel? The optical fibre channel is nonlinear, and the intensity-dependent Kerr nonlinearity limit has been suggested as a fundamental limit to optical fibre capacity. Current research is focused on whether this is the case, and on linear and nonlinear techniques, both optical and electronic, to understand, unlock and maximize the capacity of optical communications in the nonlinear regime. This paper describes some of them and discusses future prospects for success in the quest for capacity.
| S-EPMC4733919 | biostudies-literature
Project description:The threat of a malicious attack is one of the major security problems in complex networks. Resilience is the system-level self-adjusting ability of a complex network to retain its basic functionality and recover rapidly from major disruptions. Despite numerous heuristic enhancement methods, there is a research gap in maximizing network resilience: current heuristic methods are designed to immunize vital nodes or modify a network to a specific onion-like structure and cannot maximize resilience theoretically via network structure. Here we map complex networks onto a physical elastic system to introduce indices of network resilience, and propose a unified theoretical framework and general approach, which can address the optimal problem of network resilience by slightly modifying network structures (i.e., by adding a set of structural edges). We demonstrate the high efficiency of this approach on three realistic networks as well as two artificial random networks. Case studies show that the proposed approach can maximize the resilience of complex networks while maintaining their topological functionality. This approach helps to unveil hitherto hidden functions of some inconspicuous components, which in turn, can be used to guide the design of resilient systems, offer an effective and efficient approach for mitigating malicious attacks, and furnish self-healing to reconstruct failed infrastructure systems.
| S-EPMC6381220 | biostudies-literature
Project description:We have investigated the variables that influence DNA coverage on gold nanoparticles. The effects of salt concentration, spacer composition, nanoparticle size, and degree of sonication have been evaluated. Maximum loading was obtained by salt aging the nanoparticles to approximately 0.7 M NaCl in the presence of DNA containing a poly(ethylene glycol) spacer. In addition, DNA loading was substantially increased by sonicating the nanoparticles during the surface loading process. Last, nanoparticles up to 250 nm in diameter were found have approximately 2 orders of magnitude higher DNA loading than smaller (13-30 nm) nanoparticles, a consequence of their larger surface area. Stable large particles are attractive for a variety of biodiagnostic assays.
| S-EPMC2525614 | biostudies-literature
Project description:Modulation of interactions among neurons can manifest as dramatic changes in the state of population dynamics in cerebral cortex. How such transitions in cortical state impact the information processing performed by cortical circuits is not clear. Here we performed experiments and computational modeling to determine how somatosensory dynamic range depends on cortical state. We used microelectrode arrays to record ongoing and whisker stimulus-evoked population spiking activity in somatosensory cortex of urethane anesthetized rats. We observed a continuum of different cortical states; at one extreme population activity exhibited small scale variability and was weakly correlated, the other extreme had large scale fluctuations and strong correlations. In experiments, shifts along the continuum often occurred naturally, without direct manipulation. In addition, in both the experiment and the model we directly tuned the cortical state by manipulating inhibitory synaptic interactions. Our principal finding was that somatosensory dynamic range was maximized in a specific cortical state, called criticality, near the tipping point midway between the ends of the continuum. The optimal cortical state was uniquely characterized by scale-free ongoing population dynamics and moderate correlations, in line with theoretical predictions about criticality. However, to reproduce our experimental findings, we found that existing theory required modifications which account for activity-dependent depression. In conclusion, our experiments indicate that in vivo sensory dynamic range is maximized near criticality and our model revealed an unanticipated role for activity-dependent depression in this basic principle of cortical function.
| S-EPMC4666488 | biostudies-literature
Project description:In vitro transcription using T7 bacteriophage polymerase is widely used in molecular biology. Here, we use 5'RACE-Seq to screen a randomized initially transcribed region of the T7 promoter for cross-talk with transcriptional activity. We reveal that sequences from position +4 to +8 downstream of the transcription start site affect T7 promoter activity over a 5-fold range, and identify promoter variants with significantly enhanced transcriptional output that increase the yield of in vitro transcription reactions across a wide range of template concentrations. We furthermore introduce CEL-Seq+ , which uses an optimized T7 promoter to amplify cDNA for single-cell RNA-Sequencing. CEL-Seq+ facilitates scRNA-Seq library preparation, and substantially increases library complexity and the number of expressed genes detected per cell, highlighting a particular value of optimized T7 promoters in bioanalytical applications.
| S-EPMC7429497 | biostudies-literature
Project description:BackgroundReal-time air pollution monitoring is a valuable tool for public health and environmental surveillance. In recent years, there has been a dramatic increase in air pollution forecasting and monitoring research using artificial neural networks. Most prior work relied on modeling pollutant concentrations collected from ground-based monitors and meteorological data for long-term forecasting of outdoor ozone (O3), oxides of nitrogen, and fine particulate matter (PM2.5). Given that traditional, highly sophisticated air quality monitors are expensive and not universally available, these models cannot adequately serve those not living near pollutant monitoring sites. Furthermore, because prior models were built based on physical measurement data collected from sensors, they may not be suitable for predicting the public health effects of pollution exposure.ObjectiveThis study aimed to develop and validate models to nowcast the observed pollution levels using web search data, which are publicly available in near real time from major search engines.MethodsWe developed novel machine learning-based models using both traditional supervised classification methods and state-of-the-art deep learning methods to detect elevated air pollution levels at the US city level by using generally available meteorological data and aggregate web-based search volume data derived from Google Trends. We validated the performance of these methods by predicting 3 critical air pollutants (O3, nitrogen dioxide, and PM2.5) across 10 major US metropolitan statistical areas in 2017 and 2018. We also explore different variations of the long short-term memory model and propose a novel search term dictionary learner-long short-term memory model to learn sequential patterns across multiple search terms for prediction.ResultsThe top-performing model was a deep neural sequence model long short-term memory, using meteorological and web search data, and reached an accuracy of 0.82 (F1-score 0.51) for O3, 0.74 (F1-score 0.41) for nitrogen dioxide, and 0.85 (F1-score 0.27) for PM2.5, when used for detecting elevated pollution levels. Compared with using only meteorological data, the proposed method achieved superior accuracy by incorporating web search data.ConclusionsThe results show that incorporating web search data with meteorological data improves the nowcasting performance for all 3 pollutants and suggest promising novel applications for tracking global physical phenomena using web search data.
| S-EPMC9808603 | biostudies-literature