Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Accurate and fast path computation on large urban road networks: A general approach.

ABSTRACT: Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing. While a number of heuristic algorithms have been developed in the past few years for faster path queries, the accuracy of them are always far below satisfying. In this paper, we first develop an agglomerative graph partitioning method for generating high balanced traverse distance partitions, and we constitute a three-level graph model based on the graph partition scheme for structuring the urban road network. Then, we propose a new hierarchical path computation algorithm, which benefits from the hierarchical graph model and utilizes a region pruning strategy to significantly reduce the search space without compromising the accuracy. Finally, we present a detailed experimental evaluation on the real urban road network of New York City, and the experimental results demonstrate the effectiveness of the proposed approach to generate optimal fast paths and to facilitate real-time routing applications.

SUBMITTER: Song Q

PROVIDER: S-EPMC5812589 | biostudies-literature | 2018

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Accurate and fast path computation on large urban road networks: A general approach.

Song Qing Q Li Meng M Li Xiaolei X

PloS one 20180214 2

Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing. While a number of heuristic algorithms have been developed in the past few years for faster path queries, the accuracy of them are always far below satisfying. In this paper, we first develop an agglomerative graph partitioning method for generating high balanced traverse distance partitions, and we constitute a three-level graph model based on the graph partition sche ...[more]

PMID: 29444119

Similar Datasets

Fast and accurate detection of spread source in large complex networks.

Project description:Spread over complex networks is a ubiquitous process with increasingly wide applications. Locating spread sources is often important, e.g. finding the patient one in epidemics, or source of rumor spreading in social network. Pinto, Thiran and Vetterli introduced an algorithm (PTVA) to solve the important case of this problem in which a limited set of nodes act as observers and report times at which the spread reached them. PTVA uses all observers to find a solution. Here we propose a new approach in which observers with low quality information (i.e. with large spread encounter times) are ignored and potential sources are selected based on the likelihood gradient from high quality observers. The original complexity of PTVA is O(N ? ), where ? ? (3,4) depends on the network topology and number of observers (N denotes the number of nodes in the network). Our Gradient Maximum Likelihood Algorithm (GMLA) reduces this complexity to O (N2log (N)). Extensive numerical tests performed on synthetic networks and real Gnutella network with limitation that id's of spreaders are unknown to observers demonstrate that for scale-free networks with such limitation GMLA yields higher quality localization results than PTVA does.

| S-EPMC5802743 | biostudies-literature

Encapsulating urban traffic rhythms into road networks.

Project description:Using road GIS (geographical information systems) data and travel demand data for two U.S. urban areas, the dynamical driver sources of each road segment were located. A method to target road clusters closely related to urban traffic congestion was then developed to improve road network efficiency. The targeted road clusters show different spatial distributions at different times of a day, indicating that our method can encapsulate dynamical travel demand information into the road networks. As a proof of concept, when we lowered the speed limit or increased the capacity of road segments in the targeted road clusters, we found that both the number of congested roads and extra travel time were effectively reduced. In addition, the proposed modeling framework provided new insights on the optimization of transport efficiency in any infrastructure network with a specific supply and demand distribution.

| S-EPMC3929915 | biostudies-literature

Local floods induce large-scale abrupt failures of road networks.

Project description:The adverse effect of climate change continues to expand, and the risks of flooding are increasing. Despite advances in network science and risk analysis, we lack a systematic mathematical framework for road network percolation under the disturbance of flooding. The difficulty is rooted in the unique three-dimensional nature of a flood, where altitude plays a critical role as the third dimension, and the current network-based framework is unsuitable for it. Here we develop a failure model to study the effect of floods on road networks; the result covers 90.6% of road closures and 94.1% of flooded streets resulting from Hurricane Harvey. We study the effects of floods on road networks in China and the United States, showing a discontinuous phase transition, indicating that a small local disturbance may lead to a large-scale systematic malfunction of the entire road network at a critical point. Our integrated approach opens avenues for understanding the resilience of critical infrastructure networks against floods.

| S-EPMC6520386 | biostudies-literature

A fast and accurate computational approach to protein ionization.

Project description:We report a very fast and accurate physics-based method to calculate pH-dependent electrostatic effects in protein molecules and to predict the pK values of individual sites of titration. In addition, a CHARMm-based algorithm is included to construct and refine the spatial coordinates of all hydrogen atoms at a given pH. The present method combines electrostatic energy calculations based on the Generalized Born approximation with an iterative mobile clustering approach to calculate the equilibria of proton binding to multiple titration sites in protein molecules. The use of the GBIM (Generalized Born with Implicit Membrane) CHARMm module makes it possible to model not only water-soluble proteins but membrane proteins as well. The method includes a novel algorithm for preliminary refinement of hydrogen coordinates. Another difference from existing approaches is that, instead of monopeptides, a set of relaxed pentapeptide structures are used as model compounds. Tests on a set of 24 proteins demonstrate the high accuracy of the method. On average, the RMSD between predicted and experimental pK values is close to 0.5 pK units on this data set, and the accuracy is achieved at very low computational cost. The pH-dependent assignment of hydrogen atoms also shows very good agreement with protonation states and hydrogen-bond network observed in neutron-diffraction structures. The method is implemented as a computational protocol in Accelrys Discovery Studio and provides a fast and easy way to study the effect of pH on many important mechanisms such as enzyme catalysis, ligand binding, protein-protein interactions, and protein stability.

| S-EPMC2578799 | biostudies-literature

Fast and accurate annotation of acoustic signals with deep neural networks

Project description:Acoustic signals serve communication within and across species throughout the animal kingdom. Studying the genetics, evolution, and neurobiology of acoustic communication requires annotating acoustic signals: segmenting and identifying individual acoustic elements like syllables or sound pulses. To be useful, annotations need to be accurate, robust to noise, and fast. We here introduce DeepAudioSegmenter (DAS), a method that annotates acoustic signals across species based on a deep-learning derived hierarchical presentation of sound. We demonstrate the accuracy, robustness, and speed of DAS using acoustic signals with diverse characteristics from insects, birds, and mammals. DAS comes with a graphical user interface for annotating song, training the network, and for generating and proofreading annotations. The method can be trained to annotate signals from new species with little manual annotation and can be combined with unsupervised methods to discover novel signal types. DAS annotates song with high throughput and low latency for experimental interventions in realtime. Overall, DAS is a universal, versatile, and accessible tool for annotating acoustic communication signals.

| S-EPMC8560090 | biostudies-literature

FASIMU: flexible software for flux-balance computation series in large metabolic networks.

Project description:BackgroundFlux-balance analysis based on linear optimization is widely used to compute metabolic fluxes in large metabolic networks and gains increasingly importance in network curation and structural analysis. Thus, a computational tool flexible enough to realize a wide variety of FBA algorithms and able to handle batch series of flux-balance optimizations is of great benefit.ResultsWe present FASIMU, a command line oriented software for the computation of flux distributions using a variety of the most common FBA algorithms, including the first available implementation of (i) weighted flux minimization, (ii) fitness maximization for partially inhibited enzymes, and (iii) of the concentration-based thermodynamic feasibility constraint. It allows batch computation with varying objectives and constraints suited for network pruning, leak analysis, flux-variability analysis, and systematic probing of metabolic objectives for network curation. Input and output supports SBML. FASIMU can work with free (lp_solve and GLPK) or commercial solvers (CPLEX, LINDO). A new plugin (faBiNA) for BiNA allows to conveniently visualize calculated flux distributions. The platform-independent program is an open-source project, freely available under GNU public license at http://www.bioinformatics.org/fasimu including manual, tutorial, and plugins.ConclusionsWe present a flux-balance optimization program whose main merits are the implementation of thermodynamics as a constraint, batch series of computations, free availability of sources, choice on various external solvers, and the flexibility on metabolic objectives and constraints.

| S-EPMC3038154 | biostudies-literature

Fast and accurate average genome size and 16S rRNA gene average copy number computation in metagenomic data.

Project description:BACKGROUND:Metagenomics caused a quantum leap in microbial ecology. However, the inherent size and complexity of metagenomic data limit its interpretation. The quantification of metagenomic traits in metagenomic analysis workflows has the potential to improve the exploitation of metagenomic data. Metagenomic traits are organisms' characteristics linked to their performance. They are measured at the genomic level taking a random sample of individuals in a community. As such, these traits provide valuable information to uncover microorganisms' ecological patterns. The Average Genome Size (AGS) and the 16S rRNA gene Average Copy Number (ACN) are two highly informative metagenomic traits that reflect microorganisms' ecological strategies as well as the environmental conditions they inhabit. RESULTS:Here, we present the ags.sh and acn.sh tools, which analytically derive the AGS and ACN metagenomic traits. These tools represent an advance on previous approaches to compute the AGS and ACN traits. Benchmarking shows that ags.sh is up to 11 times faster than state-of-the-art tools dedicated to the estimation AGS. Both ags.sh and acn.sh show comparable or higher accuracy than existing tools used to estimate these traits. To exemplify the applicability of both tools, we analyzed the 139 prokaryotic metagenomes of TARA Oceans and revealed the ecological strategies associated with different water layers. CONCLUSION:We took advantage of recent advances in gene annotation to develop the ags.sh and acn.sh tools to combine easy tool usage with fast and accurate performance. Our tools compute the AGS and ACN metagenomic traits on unassembled metagenomes and allow researchers to improve their metagenomic data analysis to gain deeper insights into microorganisms' ecology. The ags.sh and acn.sh tools are publicly available using Docker container technology at https://github.com/pereiramemo/AGS-and-ACN-tools .

| S-EPMC6727555 | biostudies-literature

A Bayesian approach for fast and accurate gene tree reconstruction.

Project description:Recent sequencing and computing advances have enabled phylogenetic analyses to expand to both entire genomes and large clades, thus requiring more efficient and accurate methods designed specifically for the phylogenomic context. Here, we present SPIMAP, an efficient Bayesian method for reconstructing gene trees in the presence of a known species tree. We observe many improvements in reconstruction accuracy, achieved by modeling multiple aspects of evolution, including gene duplication and loss (DL) rates, speciation times, and correlated substitution rate variation across both species and loci. We have implemented and applied this method on two clades of fully sequenced species, 12 Drosophila and 16 fungal genomes as well as simulated phylogenies and find dramatic improvements in reconstruction accuracy as compared with the most popular existing methods, including those that take the species tree into account. We find that reconstruction inaccuracies of traditional phylogenetic methods overestimate the number of DL events by as much as 2-3-fold, whereas our method achieves significantly higher accuracy. We feel that the results and methods presented here will have many important implications for future investigations of gene evolution.

| S-EPMC3002250 | biostudies-literature

QuartetS: a fast and accurate algorithm for large-scale orthology detection.

Project description:The unparalleled growth in the availability of genomic data offers both a challenge to develop orthology detection methods that are simultaneously accurate and high throughput and an opportunity to improve orthology detection by leveraging evolutionary evidence in the accumulated sequenced genomes. Here, we report a novel orthology detection method, termed QuartetS, that exploits evolutionary evidence in a computationally efficient manner. Based on the well-established evolutionary concept that gene duplication events can be used to discriminate homologous genes, QuartetS uses an approximate phylogenetic analysis of quartet gene trees to infer the occurrence of duplication events and discriminate paralogous from orthologous genes. We used function- and phylogeny-based metrics to perform a large-scale, systematic comparison of the orthology predictions of QuartetS with those of four other methods [bi-directional best hit (BBH), outgroup, OMA and QuartetS-C (QuartetS followed by clustering)], involving 624 bacterial genomes and >2 million genes. We found that QuartetS slightly, but consistently, outperformed the highly specific OMA method and that, while consuming only 0.5% additional computational time, QuartetS predicted 50% more orthologs with a 50% lower false positive rate than the widely used BBH method. We conclude that, for large-scale phylogenetic and functional analysis, QuartetS and QuartetS-C should be preferred, respectively, in applications where high accuracy and high throughput are required.

| S-EPMC3141274 | biostudies-literature

Spectral consensus strategy for accurate reconstruction of large biological networks.

Project description:The last decades witnessed an explosion of large-scale biological datasets whose analyses require the continuous development of innovative algorithms. Many of these high-dimensional datasets are related to large biological networks with few or no experimentally proven interactions. A striking example lies in the recent gut bacterial studies that provided researchers with a plethora of information sources. Despite a deeper knowledge of microbiome composition, inferring bacterial interactions remains a critical step that encounters significant issues, due in particular to high-dimensional settings, unknown gut bacterial taxa and unavoidable noise in sparse datasets. Such data type make any a priori choice of a learning method particularly difficult and urge the need for the development of new scalable approaches.We propose a consensus method based on spectral decomposition, named Spectral Consensus Strategy, to reconstruct large networks from high-dimensional datasets. This novel unsupervised approach can be applied to a broad range of biological networks and the associated spectral framework provides scalability to diverse reconstruction methods. The results obtained on benchmark datasets demonstrate the interest of our approach for high-dimensional cases. As a suitable example, we considered the human gut microbiome co-presence network. For this application, our method successfully retrieves biologically relevant relationships and gives new insights into the topology of this complex ecosystem.The Spectral Consensus Strategy improves prediction precision and allows scalability of various reconstruction methods to large networks. The integration of multiple reconstruction algorithms turns our approach into a robust learning method. All together, this strategy increases the confidence of predicted interactions from high-dimensional datasets without demanding computations.

| S-EPMC5249011 | biostudies-other

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data