Browse
Submit Data
Databases
API
Help

Dataset Information

25 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Constructing small genome graphs via string compression.

ABSTRACT:

Motivation

The size of a genome graph-the space required to store the nodes, node labels and edges-affects the efficiency of operations performed on it. For example, the time complexity to align a sequence to a graph without a graph index depends on the total number of characters in the node labels and the number of edges in the graph. This raises the need for approaches to construct space-efficient genome graphs.

Results

We point out similarities in the string encoding mechanisms of genome graphs and the external pointer macro (EPM) compression model. We present a pair of linear-time algorithms that transform between genome graphs and EPM-compressed forms. The algorithms result in an upper bound on the size of the genome graph constructed in terms of an optimal EPM compression. To further reduce the size of the genome graph, we propose the source assignment problem that optimizes over the equivalent choices during compression and introduce an ILP formulation that solves that problem optimally. As a proof-of-concept, we introduce RLZ-Graph, a genome graph constructed based on the relative Lempel-Ziv algorithm. Using RLZ-Graph, across all human chromosomes, we are able to reduce the disk space to store a genome graph on average by 40.7% compared to colored compacted de Bruijn graphs constructed by Bifrost under the default settings. The RLZ-Graph scales well in terms of running time and graph sizes with an increasing number of human genome sequences compared to Bifrost and variation graphs produced by VGtoolkit.

Availability

The RLZ-Graph software is available at: https://github.com/Kingsford-Group/rlzgraph.

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Qiu Y

PROVIDER: S-EPMC8275343 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Constructing graphs from genetic encodings.

Project description:Our understanding of real-world connected systems has benefited from studying their evolution, from random wirings and rewirings to growth-dependent topologies. Long overlooked in this search has been the role of the innate: networks that connect based on identity-dependent compatibility rules. Inspired by the genetic principles that guide brain connectivity, we derive a network encoding process that can utilize wiring rules to reproducibly generate specific topologies. To illustrate the representational power of this approach, we propose stochastic and deterministic processes for generating a wide range of network topologies. Specifically, we detail network heuristics that generate structured graphs, such as feed-forward and hierarchical networks. In addition, we characterize a Random Genetic (RG) family of networks, which, like Erdős-Rényi graphs, display critical phase transitions, however their modular underpinnings lead to markedly different behaviors under targeted attacks. The proposed framework provides a relevant null-model for social and biological systems, where diverse metrics of identity underpin a node's preferred connectivity.

| S-EPMC8225892 | biostudies-literature

Constructing knowledge graphs and their biomedical applications.

Project description:Knowledge graphs can support many biomedical applications. These graphs represent biomedical concepts and relationships in the form of nodes and edges. In this review, we discuss how these graphs are constructed and applied with a particular focus on how machine learning approaches are changing these processes. Biomedical knowledge graphs have often been constructed by integrating databases that were populated by experts via manual curation, but we are now seeing a more robust use of automated systems. A number of techniques are used to represent knowledge graphs, but often machine learning methods are used to construct a low-dimensional representation that can support many different applications. This representation is designed to preserve a knowledge graph's local and/or global structure. Additional machine learning methods can be applied to this representation to make predictions within genomic, pharmaceutical, and clinical domains. We frame our discussion first around knowledge graph construction and then around unifying representational learning techniques and unifying applications. Advances in machine learning for biomedicine are creating new opportunities across many domains, and we note potential avenues for future work with knowledge graphs that appear particularly promising.

| S-EPMC7327409 | biostudies-literature

gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections.

Project description:BackgroundThe construction of a suffix array for a collection of strings is a fundamental task in Bioinformatics and in many other applications that process strings. Related data structures, as the Longest Common Prefix array, the Burrows-Wheeler transform, and the document array, are often needed to accompany the suffix array to efficiently solve a wide variety of problems. While several algorithms have been proposed to construct the suffix array for a single string, less emphasis has been put on algorithms to construct suffix arrays for string collections.ResultIn this paper we introduce gsufsort, an open source software for constructing the suffix array and related data indexing structures for a string collection with N symbols in O(N) time. Our tool is written in ANSI/C and is based on the algorithm gSACA-K (Louza et al. in Theor Comput Sci 678:22-39, 2017), the fastest algorithm to construct suffix arrays for string collections. The tool supports large fasta, fastq and text files with multiple strings as input. Experiments have shown very good performance on different types of strings.Conclusionsgsufsort is a fast, portable, and lightweight tool for constructing the suffix array and additional data structures for string collections.

| S-EPMC7507297 | biostudies-literature

Evidence synthesis for constructing directed acyclic graphs (ESC-DAGs): a novel and systematic method for building directed acyclic graphs.

Project description:BackgroundDirected acyclic graphs (DAGs) are popular tools for identifying appropriate adjustment strategies for epidemiological analysis. However, a lack of direction on how to build them is problematic. As a solution, we propose using a combination of evidence synthesis strategies and causal inference principles to integrate the DAG-building exercise within the review stages of research projects. We demonstrate this idea by introducing a novel protocol: 'Evidence Synthesis for Constructing Directed Acyclic Graphs' (ESC-DAGs)'.MethodsESC-DAGs operates on empirical studies identified by a literature search, ideally a novel systematic review or review of systematic reviews. It involves three key stages: (i) the conclusions of each study are 'mapped' into a DAG; (ii) the causal structures in these DAGs are systematically assessed using several causal inference principles and are corrected accordingly; (iii) the resulting DAGs are then synthesised into one or more 'integrated DAGs'. This demonstration article didactically applies ESC-DAGs to the literature on parental influences on offspring alcohol use during adolescence.ConclusionsESC-DAGs is a practical, systematic and transparent approach for developing DAGs from background knowledge. These DAGs can then direct primary data analysis and DAG-based sensitivity analysis. ESC-DAGs has a modular design to allow researchers who are experienced DAG users to both use and improve upon the approach. It is also accessible to researchers with limited experience of DAGs or evidence synthesis.

| S-EPMC7124493 | biostudies-literature

TransComb: genome-guided transcriptome assembly via combing junctions in splicing graphs.

Project description:Transcriptome assemblers aim to reconstruct full-length transcripts from RNA-seq data. We present TransComb, a genome-guided assembler developed based on a junction graph, weighted by a bin-packing strategy and paired-end information. A newly designed extension method based on weighted junction graphs can accurately extract paths representing expressed transcripts, whether they have low or high expression levels. Tested on both simulated and real datasets, TransComb demonstrates significant improvements in both recall and precision over leading assemblers, including StringTie, Cufflinks, Bayesembler, and Traph. In addition, it runs much faster and requires less memory on average. TransComb is available at http://sourceforge.net/projects/transcriptomeassembly/files/ .

| S-EPMC5069867 | biostudies-literature

A Pipeline for Constructing Reference Genomes for Large Cohort-Specific Metagenome Compression.

Project description:Metagenomic data compression is very important as metagenomic projects are facing the challenges of larger data volumes per sample and more samples nowadays. Reference-based compression is a promising method to obtain a high compression ratio. However, existing microbial reference genome databases are not suitable to be directly used as references for compression due to their large size and redundancy, and different metagenomic cohorts often have various microbial compositions. We present a novel pipeline that generated simplified and tailored reference genomes for large metagenomic cohorts, enabling the reference-based compression of metagenomic data. We constructed customized reference genomes, ranging from 2.4 to 3.9 GB, for 29 real metagenomic datasets and evaluated their compression performance. Reference-based compression achieved an impressive compression ratio of over 20 for human whole-genome data and up to 33.8 for all samples, demonstrating a remarkable 4.5 times improvement than the standard Gzip compression. Our method provides new insights into reference-based metagenomic data compression and has a broad application potential for faster and cheaper data transfer, storage, and analysis.

| S-EPMC10609127 | biostudies-literature

Integer sequence discovery from small graphs.

Project description:We have exhaustively enumerated all simple, connected graphs of a finite order and have computed a selection of invariants over this set. Integer sequences were constructed from these invariants and checked against the Online Encyclopedia of Integer Sequences (OEIS). 141 new sequences were added and six sequences were extended. From the graph database, we were able to programmatically suggest relationships among the invariants. It will be shown that we can readily visualize any sequence of graphs with a given criteria. The code has been released as an open-source framework for further analysis and the database was constructed to be extensible to invariants not considered in this work.

| S-EPMC4809059 | biostudies-literature

Cactus graphs for genome comparisons.

Project description:We introduce a data structure, analysis, and visualization scheme called a cactus graph for comparing sets of related genomes. In common with multi-break point graphs and A-Bruijn graphs, cactus graphs can represent duplications and general genomic rearrangements, but additionally, they naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as two-dimensional multiple alignments and nets that can be visualized in circular genome plots. Supplementary Material is available at www.liebertonline.com/cmb .

| S-EPMC8884192 | biostudies-literature

Graphlet correlation distance to compare small graphs.

Project description:Graph models are standard for representing mutual relationships between sets of entities. Often, graphs deal with a large number of entities with a small number of connections (e.g. social media relationships, infectious disease spread). The distances or similarities between such large graphs are known to be well established by the Graphlet Correlation Distance (GCD). This paper deals with small graphs (with potentially high densities of connections) that have been somewhat neglected in the literature but that concern important fora like sociology, ecology and fisheries, to mention some examples. First, based on numerical experiments, we study the conditions under which Erdős-Rényi, Fitness Scale-Free, Watts-Strogatz small-world and geometric graphs can be distinguished by a specific GCD measure based on 11 orbits, the GCD11. This is done with respect to the density and the order (i.e. the number of nodes) of the graphs when comparing graphs with the same and different orders. Second, we develop a randomization statistical test based on the GCD11 to compare empirical graphs to the four possible null models used in this analysis and apply it to a fishing case study where graphs represent pairwise proximity between fishing vessels. The statistical test rules out independent pairing within the fleet studied which is a standard assumption in fisheries. It also illustrates the difficulty to identify similarities between real-world small graphs and graph models.

| S-EPMC9931116 | biostudies-literature

Linearization of genome sequence graphs revisited.

Project description:The need to include the genetic variation within a population into a reference genome led to the concept of a genome sequence graph. Nodes of such a graph are labeled with DNA sequences occurring in represented genomes. Due to double-stranded nature of DNA, each node may be oriented in one of two possible ways, resulting in marking one end of the labeling sequence as in-side and the other as out-side. Edges join pairs of sides and reflect adjacency between node sequences in genomes constituting the graph. Linearization of a sequence graph aims at orienting and ordering graph nodes in a way that makes it more efficient for visualization and further analysis, e.g. access and traversal. We propose a new linearization algorithm, called ALIBI - Algorithm for Linearization by Incremental graph BuIlding. The evaluation shows that ALIBI is computationally very efficient and generates high-quality results.

| S-EPMC8264155 | biostudies-literature

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