Biology subjects

Kahles, A.

Publications and source records attributed to Kahles, A..

At least 19 recordsLinked to original sources

bioRxiv2026

The Ocean Microbiomics Database reveals thermal niches and projected pressure on marine microbes in a warming ocean

Temperature is a key driver of ocean microbial community structure, yet its role in shaping global distributions and their response to warming remains unclear due to fragmented studies, inconsistent methods, and limited environmental context. We present the Ocean Microbiomics Database (OMDB) containing 274,282 genomes forming 31,058 species-level clusters, searchable at https://omdb.microbiomics.io. We show surface temperature is predicted from community composition, driven by thermal niche partitioning among congeneric taxa. Using these thermal niches to model present-day distributions globally, we find that projected warming results in microbial richness declining faster than relative abundance, with losses concentrated at high latitudes and among poorly characterized lineages. Resolving 5,891 species into four thermal clusters reveals ecological structure correlated with genome streamlining, protein thermostability, and marker-gene physicochemistry, enabling prediction of a microorganism's abundance-maximizing temperature directly from its coding sequence. This positions OMDB as a platform spanning molecular traits to global ecology, offering a genome-resolved foundation for understanding how temperature, shown to be a primary driver of ocean microbial life, will continue to shape it as the ocean warms.

microbiology↗

bioRxiv2025

Splicing neoepitope prediction is sensitive to methodological differences

MotivationCancer-specific neoepitopes may arise from abnormal splicing in the transcriptomic landscape (alternative splicing neoepitopes, ASNs), leading to divergent proteins with high potential immunogenicity. Predicting candidate ASNs requires a series of algorithmic and parameter choices, but no previous study has investigated the consistency and interpretability of these choices. ResultsWe apply two ASN prediction methods with 35 matched parameter sets to generate candidate ASNs for five breast and ovarian cancer samples from The Cancer Genome Atlas (TCGA). We find that: 1) junction 9-mer peptides generated by two similarly designed pipelines differed by, on average, 68.9% and 76.6% in the BRCA and OV cohorts, respectively, and putatively cancer-specific junction 9-mers from the two pipelines diverged further, by an average of 81.5 % in OV and 84.6 % in BRCA; 2) the most lenient filters in the BRCA cohort show the highest divergence, at 97 %; 3) the rate of mass spectrometry validation of ASNs protein presence in cells is dominated by the size of the input space; and 4) putatively cancer-specific ASNs found by the intersection of both pipelines can be validated when accounting for false discovery with an average of 1.74 and 284.4 candidates in the BRCA and OV cohorts, respectively. Taken together, these results highlight that ASN identification is fragile and difficult to reproduce across analysis platforms, with limited cross-pipeline overlap and strong dependence on parameter choices. Availability and ImplementationPython research code and scripts are available for download at https://github.com/ratschlab/projects2020_ohsu. Contactthompsre@ohsu.edu, raetsch@inf.ethz.ch

bioinformatics↗

bioRxiv2023

SimReadUntil for Benchmarking Selective Sequencing Algorithms on ONT Devices

MotivationThe Oxford Nanopore Technologies (ONT) ReadUntil API enables selective sequencing, which aims to reduce time spent on sequencing uninteresting reads in favor of more interesting reads, e.g., to deplete or enrich certain genomic regions. The performance gain depends on the selective sequencing decision-making algorithm (SSDA) which decides whether to reject a read, stop receiving a read or wait for more data. Since real runs are time-consuming and costly (at scale), simulating the ONT device with support for the ReadUntil API is highly beneficial to compare and optimize the parameters of SSDAs. Existing software like MinKNOW and UNCALLED only return raw signal data, are memory-intensive, require huge and often unavailable multi-fast5 files ([≥] 100GB) and are not clearly documented. ResultsWe present the ONT device simulator SimReadUntil that takes a set of full (real or simulated) reads as input, distributes them to channels and plays them back in real time including mux scans, channel gaps and blockages, and allows to unblock (reject) reads as well as stop receiving data from them (imitating the ReadUntil API). Our modified ReadUntil API provides the basecalled reads rather than the raw signal to reduce computational load and focus on the SSDA rather than basecalling. Tuning the parameters of tools like ReadFish and ReadBouncer becomes easier because no GPU is required anymore for basecalling. We offer various methods to extract simulation parameters from a sequencing summary file and compare them. SimReadUntil s gRPC interface allows standardized interaction with a wide range of programming languages. AvailabilityThe code is freely available on GitHub (https://github.com/ratschlab/sim_read_until) along with a fully worked use case that combines the simulator with ReadFish (and optionally NanoSim). Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2022

MetaGraph-MLA: Label-guided alignment to variable-order De Bruijn graphs

Exponential growth in sequencing databases has motivated scalable De Bruijn graph-based (DBG) indexing for searching these data, using annotations to label nodes with sample IDs. Low-depth sequencing samples correspond to fragmented subgraphs, complicating finding the long contiguous walks required for alignment queries. Aligners that target single-labelled subgraphs reduce alignment lengths due to fragmentation, leading to low recall for long reads. While some (e.g., label-free) aligners partially overcome fragmentation by combining information from multiple samples, biologically-irrelevant combinations in such approaches can inflate the search space or reduce accuracy. We introduce a new scoring model, multi-label alignment (MLA), for annotated DBGs. MLA leverages two new operations: To promote biologically-relevant sample combinations, Label Change incorporates more informative global sample similarity into local scores. To improve connectivity, Node Length Change dynamically adjusts the DBG node length during traversal. Our fast, approximate, yet accurate MLA implementation has two key steps: a single-label seed-chain-extend aligner (SCA) and a multi-label chainer (MLC). SCA uses a traditional scoring model adapting recent chaining improvements to assembly graphs and provides a curated pool of alignments. MLC extracts seed anchors from SCAs alignments, produces multi-label chains using MLA scoring, then finally forms multi-label alignments. We show via substantial improvements in taxonomic classification accuracy that MLA produces biologically-relevant alignments, decreasing average weighted UniFrac errors by 63.1-66.8% and covering 45.5-47.4% (median) more long-read query characters than state-of-the-art aligners. MLAs runtimes are competitive with label-combining alignment and substantially faster than single-label alignment.

bioinformatics↗

bioRxiv2022

Aligning Distant Sequences to Graphs using Long Seed Sketches

Sequence-to-graph alignment is an important step in applications such as variant genotyping, read error correction and genome assembly. When a query sequence requires a substantial number of edits to align, approximate alignment tools that follow the seed-and-extend approach require shorter seeds to get any matches. However, in large graphs with high variation, relying on a shorter seed length leads to an exponential increase in spurious matches. We propose a novel seeding approach relying on long inexact matches instead of short exact matches. We demonstrate experimentally that our approach achieves a better time-accuracy trade-off in settings with up to a 25% mutation rate. We achieve this by sketching a subset of graph nodes and storing them in a K-nearest neighbor index. While sketches are more robust to indels, finding the nearest neighbor of a sketch in a high-dimensional space is more computationally challenging than finding exact seeds. We demonstrate that if we store sketch vectors in a K-nearest neighbor index, we can circumvent the curse of dimensionality. Our long sketch-based seed scheme contrasts existing approaches and highlights the important role that tensor sketching can play in bioinformatics applications. Our proposed seeding method and implementation have several advantages: i) We empirically show that our method is efficient and scales to graphs with 1 billion nodes, with time and memory requirements for preprocessing growing linearly with graph size and query time growing quasi-logarithmically with query length. ii) For queries with an edit distance of 25% relative to their length, on the 1 billion node graph, longer sketch-based seeds yield a 4x increase in recall compared to exact seeds. iii) Conceptually, our seeder can be incorporated into other aligners, proposing a novel direction for sequence-to-graph alignment. The implementation is available at: https://github.com/ratschlab/tensor-sketch-alignment.

bioinformatics↗

bioRxiv2021

Lossless Indexing with Counting de Bruijn Graphs

Sequencing data is rapidly accumulating in public repositories. Making this resource accessible for interactive analysis at scale requires efficient approaches for its storage and indexing. There have recently been remarkable advances in building compressed representations of annotated (or colored) de Bruijn graphs for efficiently indexing k-mer sets. However, approaches for representing quantitative attributes such as gene expression or genome positions in a general manner have remained underexplored. In this work, we propose Counting de Bruijn graphs (Counting DBGs), a notion generalizing annotated de Bruijn graphs by supplementing each node-label relation with one or many attributes (e.g., a k-mer count or its positions). Counting DBGs index k-mer abundances from 2,652 human RNA-Seq samples in over 8-fold smaller representations compared to state-of-the-art bioinformatics tools and yet faster to construct and query. Furthermore, Counting DBGs with positional annotations losslessly represent entire reads in indexes on average 27% smaller than the input compressed with gzip for human Illumina RNA-Seq and 57% smaller for PacBio HiFi sequencing of viral samples. A complete searchable index of all viral PacBio SMRT reads from NCBIs SRA (152,884 samples, 875 Gbp) comprises only 178 GB. Finally, on the full RefSeq collection, we generate a lossless and fully queryable index that is 4.4-fold smaller than the MegaBLAST index. The techniques proposed in this work naturally complement existing methods and tools employing de Bruijn graphs and significantly broaden their applicability: from indexing k-mer counts and genome positions to implementing novel sequence alignment algorithms on top of highly compressed graph-based sequence indexes.

bioinformatics↗

bioRxiv2021

SECEDO: SNV-based subclone detection using ultra-low coverage single-cell DNA sequencing

MotivationSeveral recently developed single-cell DNA sequencing technologies enable whole-genome sequencing of thousands of cells. However, the ultra-low coverage of the sequenced data (< 0.05x per cell) mostly limits their usage to the identification of copy number alterations in multi-megabase segments. Many tumors are not copy number-driven, and thus single-nucleotide variant (SNV)-based subclone detection may contribute to a more comprehensive view on intra-tumor heterogeneity. Due to the low coverage of the data, the identification of SNVs is only possible when superimposing the sequenced genomes of hundreds of genetically similar cells. Thus, we have developed a new approach to efficiently cluster tumor cells based on a Bayesian filtering approach of relevant loci and exploiting read overlap and phasing. ResultsWe developed Single Cell Data Tumor Clusterer (SECEDO, lat. to separate), a new method to cluster tumor cells based solely on SNVs, inferred on ultra-low coverage single-cell DNA sequencing data. We applied SECEDO to a synthetic dataset simulating 7,250 cells and eight tumor subclones from a single patient, and were able to accurately reconstruct the clonal composition, detecting 92.11% of the somatic SNVs, with the smallest clusters representing only 6.9% of the total population. When applied to four real single-cell sequencing datasets from a breast cancer patient, each consisting of {approx}2,000 cells, SECEDO was able to recover the major clonal composition in each dataset at the original coverage of 0.03x, achieving an ARI score of {approx}0.6. The current state-of-the-art SNV-based clustering method achieved an ARI score of {approx}0, even after increasing the coverage in silico by a factor of 10, and was only able to match SECEDOs performance when pooling data from all four datasets, in addition to artificially increasing the sequencing coverage by a factor of 7. Variant calling on the resulting clusters recovered more than twice as many SNVs as would have been detected if calling on all cells together. Further, the allelic ratio of the called SNVs on each subcluster was more than double relative to the allelic ratio of the SNVs called without clustering, thus demonstrating that calling variants on subclones, in addition to both increasing sensitivity of SNV detection and attaching SNVs to subclones, significantly increases the confidence of the called variants. AvailabilitySECEDO is implemented in C++ and is publicly available at https://github.com/ratschlab/secedo.

bioinformatics↗

bioRxiv2020

Using Genome Graph Topology to Guide Annotation Matrix Sparsification

Since the amount of published biological sequencing data is growing exponentially, efficient methods for storing and indexing this data are more needed than ever to truly benefit from this invaluable resource for biomedical research. Labeled de Bruijn graphs are a frequently-used approach for representing large sets of sequencing data. While significant progress has been made to succinctly represent the graph itself, efficient methods for storing labels on such graphs are still rapidly evolving. In this paper, we present RowDiff, a new technique for compacting graph labels by leveraging expected similarities in annotations of vertices adjacent in the graph. RowDiff can be constructed in linear time relative to the number of vertices and labels in the graph, and in space proportional to the graph size. In addition, construction can be efficiently parallelized and distributed, making the technique applicable to graphs with trillions of nodes. RowDiff can be viewed as an intermediary sparsification step of the original annotation matrix and can thus naturally be combined with existing generic schemes for compressed binary matrices. Experiments on 10,000 RNA-seq datasets show that RowDiff combined with Multi-BRWT results in a 30% reduction in annotation footprint over Mantis-MST, the previously known most compact annotation representation. Experiments on the sparser Fungi subset of the RefSeq collection show that applying RowDiff sparsification reduces the size of individual annotation columns stored as compressed bit vectors by an average factor of 42. When combining RowDiff with a Multi-BRWT representation, the resulting annotation is 26 times smaller than Mantis-MST.

bioinformatics↗

bioRxiv2020

Fast Alignment-Free Similarity Estimation By Tensor Sketching

The sharp increase in next-generation sequencing technologies capacity has created a demand for algorithms capable of quickly searching a large corpus of biological sequences. The complexity of biological variability and the magnitude of existing data sets have impeded finding algorithms with guaranteed accuracy that efficiently run in practice. Our main contribution is the Tensor Sketch method that efficiently and accurately estimates edit distances. In our experiments, Tensor Sketch had 0.956 Spearmans rank correlation with the exact edit distance, improving its best competitor Ordered MinHash by 23%, while running almost 5 times faster. Finally, all sketches can be updated dynamically if the input is a sequence stream, making it appealing for large-scale applications where data cannot fit into memory. Conceptually, our approach has three steps: 1) represent sequences as tensors over their sub-sequences, 2) apply tensor sketching that preserves tensor inner products, 3) implicitly compute the sketch. The sub-sequences, which are not necessarily contiguous pieces of the sequence, allow us to outperform k-mer-based methods, such as min-hash sketching over a set of k-mers. Typically, the number of sub-sequences grows exponentially with the sub-sequence length, introducing both memory and time overheads. We directly address this problem in steps 2 and 3 of our method. While the sketching of rank-1 or super-symmetric tensors is known to admit efficient sketching, the sub-sequence tensor does not satisfy either of these properties. Hence, we propose a new sketching scheme that completely avoids the need for constructing the ambient space. Our tensor-sketching techniques main advantages are three-fold: 1) Tensor Sketch has higher accuracy than any of the other assessed sketching methods used in practice. 2) All sketches can be computed in a streaming fashion, leading to significant time and memory savings when there is overlap between input sequences. 3) It is straightforward to extend tensor sketching to different settings leading to efficient methods for related sequence analysis tasks. We view tensor sketching as a framework to tackle a wide range of relevant bioinformatics problems, and we are confident that it can bring significant improvements for applications based on edit distance estimation.

bioinformatics↗

bioRxiv2020

MetaGraph: Indexing and Analysing Nucleotide Archives at Petabase-scale

The amount of biological sequencing data available in public repositories is growing exponentially, forming an invaluable biomedical research resource. Yet, making it full-text searchable and easily accessible to researchers in life and data science is an unsolved problem. In this work, we take advantage of recently developed, very efficient data structures and algorithms for representing sequence sets. We make Petabases of DNA sequences across all clades of life, including viruses, bacteria, fungi, plants, animals, and humans, fully searchable. Our indexes are freely available to the research community. This highly compressed representation of the input sequences (up to 5800x) fits on a single consumer hard drive ({approx}100 USD), making this valuable resource cost-effective to use and easily transportable. We present the underlying methodological framework, called MetaGraph, that allows us to scalably index very large sets of DNA or protein sequences using annotated De Bruijn graphs. We demonstrate the feasibility of indexing the full extent of existing sequencing data and present new approaches for efficient and cost-effective full-text search at an on-demand cost of $0.10 per queried Mpb. We explore several practical use cases to mine existing archives for interesting associations and demonstrate the utility of our indexes for integrative analyses.

bioinformatics↗

bioRxiv2020

AStarix: Fast and Optimal Sequence-to-Graph Alignment

We present an algorithm for the optimal alignment of sequences to genome graphs. It works by phrasing the edit distance minimization task as finding a shortest path on an implicit alignment graph. To find a shortest path, we instantiate the A[*] paradigm with a novel domain-specific heuristic function that accounts for the upcoming subsequence in the query to be aligned, resulting in a provably optimal alignment algorithm called ASO_SCPLOWTARIXC_SCPLOW. Experimental evaluation of ASO_SCPLOWTARIXC_SCPLOW shows that it is 1-2 orders of magnitude faster than state-of-the-art optimal algorithms on the task of aligning Illumina reads to reference genome graphs. Implementations and evaluations are available at https://github.com/eth-sri/astarix.

bioinformatics↗

bioRxiv2019

Global Genetic Cartography of Urban Metagenomes andAnti-Microbial Resistance

We have created a global atlas of 4,728 metagenomic samples from mass-transit systems in 60 cities across 3 years. This is the first systematic, worldwide study cataloging the urban microbial ecosystem. We identify taxonomically-defined microorganisms collected across three years. This atlas provides an annotated, geospatial profile of microbial strains, functional characteristics AMR markers, and novel genetic elements, including 10,928 viral, 1302 bacteria, and 2 archaea novel species. We identify 4,424 species of urban microorganisms and a consistent "core" of 31 species found in nearly all samples that is largely distinct from any human commensal microbiome. Profiles of AMR genes show geographic variation in type and density. Together, these results constitute a high-resolution, global metagenomic atlas, which enables the discovery of new genetic components, highlights potential forensic applications, and provides an essential first draft of the global AMR burden of the worlds cities.

microbiology↗

bioRxiv2018

Sparse Binary Relation Representations for Genome Graph Annotation

High-throughput DNA sequencing data is accumulating in public repositories, and efficient approaches for storing and indexing such data are in high demand. In recent research, several graph data structures have been proposed to represent large sets of sequencing data and to allow for efficient querying of sequences. In particular, the concept of labeled de Bruijn graphs has been explored by several groups. While there has been good progress towards representing the sequence graph in small space, methods for storing a set of labels on top of such graphs are still not sufficiently explored. It is also currently not clear how characteristics of the input data, such as the sparsity and correlations of labels, can help to inform the choice of method to compress the graph labeling. In this work, we present a new compression approach, Multi-BRWT, which is adaptive to different kinds of input data. We show an up to 29% improvement in compression performance over the basic BRWT method, and up to a 68% improvement over the current state-of-the-art for de Bruijn graph label compression. To put our results into perspective, we present a systematic analysis of five different state-of-the-art annotation compression schemes, evaluate key metrics on both artificial and real-world data and discuss how different data characteristics influence the compression performance. We show that the improvements of our new method can be robustly reproduced for different representative real-world datasets.

bioinformatics↗

bioRxiv2017

Efficient graph-color compression with neighborhood-informed Bloom filters

MotivationTechnological advancements in high-throughput DNA sequencing have led to an exponential growth of sequencing data being produced and stored as a byproduct of biomedical research. Despite its public availability, a majority of this data remains hard to query to the research community due to a lack of efficient data representation and indexing solutions. One of the available techniques to represent read data is a condensed form as an assembly graph. Such a representation contains all sequence information but does not store contextual information and metadata.\n\nResultsWe present two new approaches for a compressed representation of a graph coloring: a lossless compression scheme based on a novel application of wavelet tries as well as a highly accurate lossy compression based on a set of Bloom filters. Both strategies retain a coloring with dynamically changing graph topology. We present construction and merge procedures for both methods and evaluate their performance on a wide range of different datasets. By dropping the requirement of a fully lossless compression and using the topological information of the underlying graph, we can reduce memory requirements by up to three orders of magnitude. Representing individual colors as independently stored modules, our approaches are fully dynamic and can be efficiently parallelized. These properties allow for an easy upscaling to the problem sizes common to the biomedical domain.\n\nAvailabilityWe provide prototype implementations in C++, summaries of our experiments as well as links to all datasets publicly at https://github.com/ratschlab/graph_annotation.\n\nContactandre.kahles@inf.ethz.ch, carsten@brown.edu, Gunnar.Ratsch@ratschlab.org

bioinformatics↗

bioRxiv2017

Metannot: A succinct data structure for compression of colors in dynamic de Bruijn graphs

Much of the DNA and RNA sequencing data available is in the form of high-throughput sequencing (HTS) reads and is currently unindexed by established sequence search databases. Recent succinct data structures for indexing both reference sequences and HTS data, along with associated metadata, have been based on either hashing or graph models, but many of these structures are static in nature, and thus, not well-suited as backends for dynamic databases.\n\nWe propose a parallel construction method for and novel application of the wavelet trie as a dynamic data structure for compressing and indexing graph metadata. By developing an algorithm for merging wavelet tries, we are able to construct large tries in parallel by merging smaller tries constructed concurrently from batches of data.\n\nWhen compared against general compression algorithms and those developed specifically for graph colors (VARI and Rainbowfish), our method achieves compression ratios superior to gzip and VARI, converging to compression ratios of 6.5% to 2% on data sets constructed from over 600 virus genomes.\n\nWhile marginally worse than compression by bzip2 or Rainbowfish, this structure allows for both fast extension and query. We also found that additionally encoding graph topology metadata improved compression ratios, particularly on data sets consisting of several mutually-exclusive reference genomes.\n\nIt was also observed that the compression ratio of wavelet tries grew sublinearly with the density of the annotation matrices.\n\nThis work is a significant step towards implementing a dynamic data structure for indexing large annotated sequence data sets that supports fast query and update operations. At the time of writing, no established standard tool has filled this niche.

bioinformatics↗

bioRxiv2017

Assessing the Gene Regulatory Landscape in 1,188 Human Tumors

Cancer is characterised by somatic genetic variation, but the effect of the majority of non-coding somatic variants and the interface with the germline genome are still unknown. We analysed the whole genome and RNA-Seq data from 1,188 human cancer patients as provided by the Pan-cancer Analysis of Whole Genomes (PCAWG) project to map cis expression quantitative trait loci of somatic and germline variation and to uncover the causes of allele-specific expression patterns in human cancers. The availability of the first large-scale dataset with both whole genome and gene expression data enabled us to uncover the effects of the non-coding variation on cancer. In addition to confirming known regulatory effects, we identified novel associations between somatic variation and expression dysregulation, in particular in distal regulatory elements. Finally, we uncovered links between somatic mutational signatures and gene expression changes, including TERT and LMO2, and we explained the inherited risk factors in APOBEC-related mutational processes. This work represents the first large-scale assessment of the effects of both germline and somatic genetic variation on gene expression in cancer and creates a valuable resource cataloguing these effects.

cancer biology↗

bioRxiv2017

Pan-cancer study of heterogeneous RNA aberrations

We present the most comprehensive catalogue of cancer-associated gene alterations through characterization of tumor transcriptomes from 1,188 donors of the Pan-Cancer Analysis of Whole Genomes project. Using matched whole-genome sequencing data, we attributed RNA alterations to germline and somatic DNA alterations, revealing likely genetic mechanisms. We identified 444 associations of gene expression with somatic non-coding single-nucleotide variants. We found 1,872 splicing alterations associated with somatic mutation in intronic regions, including novel exonization events associated with Alu elements. Somatic copy number alterations were the major driver of total gene and allele-specific expression (ASE) variation. Additionally, 82% of gene fusions had structural variant support, including 75 of a novel class called \"bridged\" fusions, in which a third genomic location bridged two different genes. Globally, we observe transcriptomic alteration signatures that differ between cancer types and have associations with DNA mutational signatures. Given this unique dataset of RNA alterations, we also identified 1,012 genes significantly altered through both DNA and RNA mechanisms. Our study represents an extensive catalog of RNA alterations and reveals new insights into the heterogeneous molecular mechanisms of cancer gene alterations.

genomics↗

bioRxiv2017

A pan cancer analysis of promoter activity highlights the regulatory role of alternative transcription start sites and their association with noncoding mutations

Most human protein-coding genes are regulated by multiple, distinct promoters, suggesting that the choice of promoter is as important as its level of transcriptional activity. While the role of promoters as driver elements in cancer has been recognized, the contribution of alternative promoters to regulation of the cancer transcriptome remains largely unexplored. Here we infer active promoters using RNA-Seq data from 1,188 cancer samples with matched whole genome sequencing data. We find that alternative promoters are a major contributor to context-specific regulation of isoform expression and that alternative promoters are frequently deregulated in cancer, affecting known cancer-genes and novel candidates. Our study suggests that a highly dynamic landscape of active promoters shapes the cancer transcriptome, opening many opportunities to further explore the interplay of regulatory mechanism and noncoding somatic mutations with transcriptional aberrations in cancer.

genomics↗