Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available January 1, 2025

Abstract Motivation Intrasample heterogeneity describes the phenomenon where a genomic sample contains a diverse set of genomic sequences. In practice, the true string sets in a sample are often unknown due to limitations in sequencing technology. In order to compare heterogeneous samples, genome graphs can be used to represent such sets of strings. However, a genome graph is generally able to represent a string set universe that contains multiple sets of strings in addition to the true string set. This difference between genome graphs and string sets is not well characterized. As a result, a distance metric between genome graphs may not match the distance between true string sets.
Results We extend a genome graph distance metric, Graph Traversal Edit Distance (GTED) proposed by Ebrahimpour Boroojeny et al., to FGTED to model the distance between heterogeneous string sets and show that GTED and FGTED always underestimate the Earth Mover’s Edit Distance (EMED) between string sets. We introduce the notion of string set universe diameter of a genome graph. Using the diameter, we are able to upperbound the deviation of FGTED from EMED and to improve FGTED so that it reduces the average error in empirically estimating the similarity between true string sets. On simulated Tcell receptor sequences and actual Hepatitis B virus genomes, we show that the diametercorrected FGTED reduces the average deviation of the estimated distance from the true string set distances by more than 250%.
Availability and implementation Data and source code for reproducing the experiments are available at: https://github.com/KingsfordGroup/gtedemedtest/.
Supplementary information Supplementary data are available at Bioinformatics online.

Motivation: Intrasample heterogeneity describes the phenomenon where a genomic sample contains a diverse set of genomic sequences. In practice, the true string sets in a sample are often unknown due to limitations in sequencing technology. In order to compare heterogeneous samples, genome graphs can be used to represent such sets of strings. However, a genome graph is generally able to represent a string set universe that contains multiple sets of strings in addition to the true string set. This difference between genome graphs and string sets is not well characterized. As a result, a distance metric between genome graphs may not match the distance between true string sets. Results: We extend a genome graph distance metric, Graph Traversal Edit Distance (GTED) proposed by Ebrahimpour Boroojeny et al., to FGTED to model the distance between heterogeneous string sets and show that GTED and FGTED always underestimate the Earth Mover’s Edit Distance (EMED) between string sets. We introduce the notion of string set universe diameter of a genome graph. Using the diameter, we are able to upperbound the deviation of FGTED from EMED and to improve FGTED so that it reduces the average error in empirically estimating the similarity between true string sets. On simulated Tcell receptor sequences and actual Hepatitis B virus genomes, we show that the diametercorrected FGTED reduces the average deviation of the estimated distance from the true string set distances by more than 250%. Availability and implementation: Data and source code for reproducing the experiments are available at: https:// github.com/KingsfordGroup/gtedemedtest/.more » « less

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 spaceefficient 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 lineartime algorithms that transform between genome graphs and EPMcompressed 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 proofofconcept, we introduce RLZGraph, a genome graph constructed based on the relative Lempel–Ziv algorithm. Using RLZGraph, 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 RLZGraph 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 RLZGraph software is available at: https://github.com/KingsfordGroup/rlzgraph.
Supplementary information Supplementary data are available at Bioinformatics online.

Abstract Motivation Despite numerous RNAseq samples available at large databases, most RNAseq analysis tools are evaluated on a limited number of RNAseq samples. This drives a need for methods to select a representative subset from all available RNAseq samples to facilitate comprehensive, unbiased evaluation of bioinformatics tools. In sequencebased approaches for representative set selection (e.g. a kmer counting approach that selects a subset based on kmer similarities between RNAseq samples), because of the large numbers of available RNAseq samples and of kmers/sequences in each sample, computing the full similarity matrix using kmers/sequences for the entire set of RNAseq samples in a large database (e.g. the SRA) has memory and runtime challenges; this makes direct representative set selection infeasible with limited computing resources. Results We developed a novel computational method called ‘hierarchical representative set selection’ to handle this challenge. Hierarchical representative set selection is a divideandconquerlike algorithm that breaks representative set selection into subselections and hierarchically selects representative samples through multiple levels. We demonstrate that hierarchical representative set selection can achieve summarization quality close to that of direct representative set selection, while largely reducing runtime and memory requirements of computing the full similarity matrix (up to 8.4× runtime reduction and 5.35× memory reduction for 10 000 and 12 000 samples respectively that could be practically run with direct subset selection). We show that hierarchical representative set selection substantially outperforms random sampling on the entire SRA set of RNAseq samples, making it a practical solution to representative set selection on large databases like the SRA. Availability and implementation The code is available at https://github.com/KingsfordGroup/hierrepsetselection and https://github.com/KingsfordGroup/jellyfishsim. Supplementary information Supplementary data are available at Bioinformatics online.more » « less

Abstract Motivation Minimizers are efficient methods to sample kmers from genomic sequences that unconditionally preserve sufficiently long matches between sequences. Wellestablished methods to construct efficient minimizers focus on sampling fewer kmers on a random sequence and use universal hitting sets (sets of kmers that appear frequently enough) to upper bound the sketch size. In contrast, the problem of sequencespecific minimizers, which is to construct efficient minimizers to sample fewer kmers on a specific sequence such as the reference genome, is less studied. Currently, the theoretical understanding of this problem is lacking, and existing methods do not specialize well to sketch specific sequences. Results We propose the concept of polar sets, complementary to the existing idea of universal hitting sets. Polar sets are kmer sets that are spread out enough on the reference, and provably specialize well to specific sequences. Link energy measures how well spread out a polar set is, and with it, the sketch size can be bounded from above and below in a theoretically sound way. This allows for direct optimization of sketch size. We propose efficient heuristics to construct polar sets, and via experiments on the human reference genome, show their practical superiority in designing efficient sequencespecific minimizers. Availability and implementation A reference implementation and code for analyses under an opensource license are at https://github.com/kingsfordgroup/polarset. Supplementary information Supplementary data are available at Bioinformatics online.more » « less