Biology subjects

Peterlongo, P.

Publications and source records attributed to Peterlongo, P..

At least 19 recordsLinked to original sources

bioRxiv2026

Lossless compression of k-mer matrices enabling random row access

Genomic search engines such as Logan-Search index petabytes of sequencing data as large binary matrices, called k-mer matrices, where each row encodes the presence of a k-mer across thousands to millions of genomic samples. Logan-Search contains a petabyte of binary matrices, and storing them is expensive, yet compression must not prevent fast random access to any matrix row at query time. We present kmcomp, a lossless compression method for k-mer matrices that satisfies these competing requirements. Block compression partitions the matrix into fixed-size row blocks, each compressed independently; block start positions are stored in an Elias-Fano encoded array, enabling O(1) random access to any block. To improve compressibility without introducing additional decompression steps, we introduce the{pi} -compression: a column reordering that groups similar samples together by solving the Traveling Salesman Problem via a nearest-neighbor heuristic. We accelerate this heuristic with a novel variant of the vantage-point tree, the masked vp-tree, which dynamically prunes nearest-neighbor search space. On three (meta)genomic datasets, kmcomp achieves compression ratios of 1.3 to 5.4;{pi} -compression further improves these to 1.5 to 51.3. Applied to the Logan-Search petabyte-scale index, compression reduces storage by approximately half, and{pi} -compression adds a further 13% gain. Query overhead remains modest: queries of hundreds of nucleotides incur an absolute latency increase of{approx} 100 ms, and highly compressed indexes can match uncompressed query times thanks to reduced disk reads.

bioinformatics↗

bioRxiv2026

Interpolating and Extrapolating Node Counts in Colored Compacted de Bruijn Graphs for Pangenome Diversity

A pangenome is a collection of taxonomically related genomes, often from the same species, serving as a representation of their genomic diversity. The study of pangenomes, or pangenomics, aims to quantify and compare this diversity, which has significant relevance in fields such as medicine and biology. Originally conceptualized as sets of genes, pangenomes are now commonly represented as pangenome graphs. These graphs consist of nodes representing genomic sequences and edges connecting consecutive sequences within a genome. Among possible pangenome graphs, a common option is the compacted de Bruijn graph. In our work, we focus on the colored compacted de Bruijn graph, where each node is associated with a set of colors that indicate the genomes traversing it. In response to the evolution of pangenome representation, we introduce a novel method for comparing pangenomes by their node counts, addressing two main challenges: the variability in node counts arising from graphs constructed with different numbers of genomes, and the large influence of rare genomic sequences. We propose an approach for interpolating and extrapolating node counts in colored compacted de Bruijn graphs, adjusting for the number of genomes. To tackle the influence of rare genomic sequences, we apply Hill numbers, a well-established diversity index previously utilized in ecology and metagenomics for similar purposes, to proportionally weight both rare and common nodes according to the frequency of genomes traversing them.

bioinformatics↗

bioRxiv2025

Kaminari: a resource-frugal index for approximate colored k-mer queries

MotivationThe problem of identifying the set of textual documents from a given database containing a query string has been studied in various fields of computing, e.g., in Information Retrieval, Databases, and Computational Biology. We consider the approximate version of this problem, that is, the result set is allowed to contain some false positive matches (but no false negatives), and focus on the specific case where the indexed documents are DNA strings. In this setting, state-of-the-art solutions rely on Bloom filters as a way to index all k-mers (substrings of length k) in the documents. To answer a query, the k-mers of the query string are tested for membership against the index and documents that contain at least a user-prescribed fraction of them (e.g., 75-80%) are returned. Methods and resultsHere, we explore an alternative index design based on k-mer minimizers and integer compression methods. We show that a careful implementation of this design outperforms previous solutions based on Bloom filters by a wide margin: the index has lower memory footprint and faster query times, while false positive matches have only a minor impact on the ranking of the documents reported. This trend is robust across genomic datasets of different complexity and query workloads. SoftwareThe software is implemented in C++17 and available under the MIT license at github.com/yhhshb/kaminari. Reproducibility information and additional results are provided at github.com/vicLeva/benchmarks_kaminari.

bioinformatics↗

bioRxiv2024

Cdbgtricks: strategies to update a compacted de bruijn graph

AO_SCPLOWBSTRACTC_SCPLOWWe propose Cdbgtricks, a new method for updating a compacted de Bruijn graph when adding novel sequences, such as full genomes. Our method indexes the graph, enabling to identify in constant time the location (unitig and offset) of any k-mer. The update operation that we propose also updates the index. Our results show that Cdbgtricks is faster than Bifrost and GGCAT. We benefit from the index of the graph to provide new functionalities, such as reporting the subgraph that shares a desired percentage of k-mers with a query sequence with the ability to query a set of reads. The open-source Cdbgtricks software is available at https://github.com/khodor14/Cdbgtricks.

bioinformatics↗

bioRxiv2024

The Backpack Quotient Filter: a dynamic and space-efficient data structure for querying k-mers with abundance.

Genomic data sequencing has become indispensable for elucidating the complexities of biological systems. As databases storing genomic information, such as the European Nucleotide Archive, continue to grow exponentially, efficient solutions for data manipulation are imperative. One funda-mental operation that remains challenging is querying these databases to determine the presence or absence of specific sequences and their abundance within datasets. This paper introduces a novel data structure indexing k-mers (substrings of length k), the Back-pack Quotient Filter (BQF), which serves as an alternative to the Counting Quotient Filter (CQF). The BQF offers enhanced space efficiency compared to the CQF while retaining key properties, including abundance information and dynamicity, with a negligible false positive rate, below 10-5%. The approach involves a redefinition of how abundance information is handled within the structure, alongside with an independent strategy for space efficiency. We show that the BQF uses 4x less space than the CQF on some of the most complex data to index: sea-water metagenomics sequences. Furthermore, we show that space efficiency increases as the amount of data to be indexed increases, which is in line with the original objective of scaling to ever-larger datasets. Availabilityhttps://github.com/vicLeva/bqf

bioinformatics↗

bioRxiv2023

Back to sequences: find the origin of kmers

A vast majority of bioinformatics tools dedicated to the treatment of raw sequencing data heavily use the concept of k-mers. This enables us to reduce the data redundancy (and thus the memory pressure), to discard sequencing errors, and to dispose of objects of fixed size that can be manipulated and easily compared to each others. A drawback is that the link between each k-mer and the original set of sequences it belongs to is generally lost. Given the volume of data considered in this context, finding back this association is costly. In this work, we present "back_to_sequences", a simple tool designed to index a set of k-mers of interests, and to stream a set of sequences, extracting those containing at least one of the indexed k-mer. In addition, the number of occurrences of k-mers in the sequences is provided. Our results show that back_to_sequences streams{approx} 200 short read per millisecond, enabling to search k-mers in hundreds of millions of reads in a matter of a few minutes. Availabilitygithub.com/pierrepeterlongo/back_to_sequences

bioinformatics↗

bioRxiv2023

kmindex and ORA: indexing and real-time user-friendly queries in terabytes-sized complex genomic datasets

Public sequencing databases contain vast amounts of biological information, yet they are largely underutilized as one cannot efficiently search them for any sequence(s) of interest. We present kmindex, an innovative approach that can index thousands of highly complex metagenomes and perform sequence searches in a fraction of a second. The index construction is an order of magnitude faster than previous methods, while search times are two orders of magnitude faster. With negligible false positive rates below 0.01%, kmindex outperforms the precision of existing approaches by four orders of magnitude. We demonstrate the scalability of kmindex by successfully indexing 1,393 complex marine seawater metagenome samples from the Tara Oceans project. Additionally, we introduce the publicly accessible web server "Ocean Read Atlas" (ORA) at https://ocean-read-atlas.mio.osupytheas.fr/, which enables real-time queries on the Tara Oceans dataset. The open-source kmindex software is available at https://github.com/tlemane/kmindex.

bioinformatics↗

bioRxiv2022

fimpera: drastic improvement of Approximate Membership Query data-structures with counts

MotivationHigh throughput sequencing technologies generate massive amounts of biological sequence datasets as costs fall. One of the current algorithmic challenges for exploiting these data on a global scale consists in providing efficient query engines on these petabyte-scale datasets. Most methods indexing those datasets rely on indexing words of fixed length k, called k-mers. Many applications, such as metagenomics, require the abundance of indexed k-mers as well as their simple presence or absence, but no method scales up to petabyte-scaled datasets. This deficiency is primarily because storing abundance requires explicit storage of the k-mers in order to associate them with their counts. Using counting Approximate Membership Queries (cAMQ) data structures, such as counting Bloom filters, provides a way to index large amounts of k-mers with their abundance, but at the expense of a sensible false positive rate. ResultsWe propose a novel algorithm, called fimpera, that enables the improvement of any cAMQ performance. Applied to counting Bloom filters, our proposed algorithm reduces the false positive rate by two orders of magnitude and it improves the precision of the reported abundances. Alternatively, fimpera allows for the reduction of the size of a counting Bloom filter by two orders of magnitude while maintaining the same precision. fimpera does not introduce any memory overhead and may even reduces the query time. Availabilityhttps://github.com/lrobidou/fimpera Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2021

findere: fast and precise approximatemembership query

MotivationApproximate membership query (AMQ) structures as Cuckoo filters or Bloom filters are widely used for representing large sets of elements. Their lightweight space usage explains their success, mainly as they are the only way to scale hundreds of billions or trillions of elements. However, they suffer by nature from non-avoidable false-positive calls that bias downstream analyses of methods using these data structures. ResultsIn this work we propose a simple strategy and its implementation for reducing the false-positive rate of any AMQ data structure indexing k-mers (words of length k). The method we propose, called findere, enables to speed-up the queries by a factor two and to decrease the false-positive rate by two order of magnitudes. This achievement is done one the fly at query time, without modifying the original indexing data-structure, without generating false-negative calls and with no memory overhead. With no drawback, this method, as simple as it is effective, reduces either the false-positive rate or the space required to represent a set given a user-defined false-positive rate. Availabilityhttps://github.com/lrobidou/findere

bioinformatics↗

bioRxiv2021

kmtricks: Efficient construction of Bloom filters for large sequencing data collections

When indexing large collections of short-read sequencing data, a common operation that has now been implemented in several tools (Sequence Bloom Trees and variants, BIGSI, ..) is to construct a collection of Bloom filters, one per sample. Each Bloom filter is used to represent a set of k-mers which approximates the desired set of all the non-erroneous k-mers present in the sample. However, this approximation is imperfect, especially in the case of metagenomics data. Erroneous but abundant k-mers are wrongly included, and non-erroneous but low-abundant ones are wrongly discarded. We propose kmtricks, a novel approach for generating Bloom filters from terabase-sized collections of sequencing data. Our main contributions are 1/ an efficient method for jointly counting k-mers across multiple samples, including a streamlined Bloom filter construction by directly counting, partitioning and sorting hashes instead of k-mers, which is approximately four times faster than state-of-the-art tools; 2/ a novel technique that takes advantage of joint counting to preserve low-abundant k-mers present in several samples, improving the recovery of non-erroneous k-mers. Our experiments highlight that this technique preserves around 8x more k-mers than the usual yet crude filtering of low-abundance k-mers in a large metagenomics dataset. Availabilityhttps://github.com/tlemane/kmtricks FundingThe work was funded by IPL Inria Neuromarkers, ANR Inception (ANR-16-CONV-0005), ANR Prairie (ANR-19-P3IA-0001), ANR SeqDigger (ANR-19-CE45-0008).

bioinformatics↗

bioRxiv2021

StrainFLAIR: Strain-level profiling of metagenomic samples using variation graphs

Current studies are shifting from the use of single linear references to representation of multiple genomes organised in pangenome graphs or variation graphs. Meanwhile, in metagenomic samples, resolving strain-level abundances is a major step in microbiome studies, as associations between strain variants and phenotype are of great interest for diagnostic and therapeutic purposes. We developed StrainFLAIR with the aim of showing the feasibility of using variation graphs for indexing highly similar genomic sequences up to the strain level, and for characterizing a set of unknown sequenced genomes by querying this graph. On simulated data composed of mixtures of strains from the same bacterial species Escherichia coli, results show that StrainFLAIR was able to distinguish and estimate the abundances of close strains, as well as to highlight the presence of a new strain close to a referenced one and to estimate its abundance. On a real dataset composed of a mix of several bacterial species and several strains for the same species, results show that in a more complex configuration StrainFLAIR correctly estimates the abundance of each strain. Hence, results demonstrated how graph representation of multiple close genomes can be used as a reference to characterize a sample at the strain level. Availabilityhttp://github.com/kevsilva/StrainFLAIR

bioinformatics↗

bioRxiv2020

Pleiotropy-guided transcriptome imputation from normal and tumor tissues identifies new candidate susceptibility genes for breast and ovarian cancer

Familial, genome-wide association (GWAS), and sequencing studies and genetic correlation analyses have progressively unraveled the shared or pleiotropic germline genetics of breast and ovarian cancer. In this study, we aimed to leverage this shared germline genetics to improve the power of transcriptome-wide association studies (TWAS) to identify candidate breast cancer and ovarian cancer susceptibility genes. We built gene expression prediction models using the PrediXcan method in 681 breast and 295 ovarian tumors from The Cancer Genome Atlas and 211 breast and 99 ovarian normal tissue samples from the Genotype-Tissue Expression project and integrated these with GWAS meta-analysis data from the Breast Cancer Association Consortium (122,977 cases/105,974 controls) and the Ovarian Cancer Association Consortium (22,406 cases/40,941 controls). The integration was achieved through novel application of a pleiotropy-guided conditional/conjunction false discovery rate approach for the first time in the setting of a TWAS. This identified 14 new candidate breast cancer susceptibility genes spanning 11 genomic regions and 8 new candidate ovarian cancer susceptibility genes spanning 5 genomic regions at conjunction FDR < 0.05 that were > 1 Mb away from known breast and/or ovarian cancer susceptibility loci. We also identified 38 candidate breast cancer susceptibility genes and 17 candidate ovarian cancer susceptibility genes at conjunction FDR < 0.05 at known breast and/or ovarian susceptibility loci. Overlaying candidate causal risk variants identified by GWAS fine mapping onto expression prediction models for genes at known loci suggested that the association for 55% of these genes was driven by the underlying GWAS signal. SignificanceThe 22 new genes identified by our cross-cancer analysis represent promising candidates that further elucidate the role of the transcriptome in mediating germline breast and ovarian cancer risk.

genetics↗

bioRxiv2020

metaVaR: introducing metavariant species models for reference-free metagenomic-based population genomics

MotivationThe availability of large metagenomic data offers great opportunities for the population genomic analysis of uncultured organisms, especially for small eukaryotes that represent an important part of the unexplored biosphere while playing a key ecological role. However, the majority of these species lacks reference genome or transcriptome which constitutes a technical barrier for classical population genomic analyses. ResultsWe introduce the metavariant species (MVS) model, a representation of the species only by intra-species nucleotide polymorphism. We designed a method combining reference-free variant calling, multiple density-based clustering and maximum weighted independent set algorithms to cluster intra-species variant into MVS directly from multisample metagenomic raw reads without reference genome or reads assembly. The frequencies of the MVS variants are then used to compute population genomic statistics such as FST in order to estimate genomic differentiation between populations and to identify loci under natural selection. The MVSs construction was tested on simulated and real metagenomic data. MVs showed the required quality for robust population genomics and allowed an accurate estimation of genomic differentiation ({Delta}FST < 0.0001 and < 0.03 on simulated and real data respectively). Loci predicted under natural selection on real data were all found by MVSs. MVSs represent a new paradigm that may simplify and enhance holistic approaches for population genomics and evolution of microorganisms. AvailabilityThe method was implemented in a R package, metaVaR. https://github.com/madoui/MetaVaR Contactamadoui@genoscope.cns.fr

bioinformatics↗

bioRxiv2019

Genomic evidence for global ocean plankton biogeography shaped by large-scale current systems

Biogeographical studies have traditionally focused on readily visible organisms, but recent technological advances are enabling analyses of the large-scale distribution of microscopic organisms, whose biogeographical patterns have long been debated. Here we assessed the global structure of plankton geography and its relation to the biological, chemical and physical context of the ocean (the seascape) by analyzing metagenomes of plankton communities sampled across oceans during the Tara Oceans expedition, in light of environmental data and ocean current transport. Using a consistent approach across organismal sizes that provides unprecedented resolution to measure changes in genomic composition between communities, we report a pan-ocean, size-dependent plankton biogeography overlying regional heterogeneity. We found robust evidence for a basin-scale impact of transport by ocean currents on plankton biogeography, and on a characteristic timescale of community dynamics going beyond simple seasonality or life history transitions of plankton.

ecology↗

bioRxiv2019

SVJedi: Genotyping structural variations with long reads

MotivationStudies on structural variants (SV) are expanding rapidly. As a result, and thanks to third generation sequencing technologies, the number of discovered SVs is increasing, especially in the human genome. At the same time, for several applications such as clinical diagnoses, it is important to genotype newly sequenced individuals on well defined and characterized SVs. Whereas several SV genotypers have been developed for short read data, there is a lack of such dedicated tool to assess whether known SVs are present or not in a new long read sequenced sample, such as the one produced by Pacific Biosciences or Oxford Nanopore Technologies. ResultsWe present a novel method to genotype known SVs from long read sequencing data. The method is based on the generation of a set of reference sequences that represent the two alleles of each structural variant. Long reads are aligned to these reference sequences. Alignments are then analyzed and filtered out to keep only informative ones, to quantify and estimate the presence of each SV allele and the allele frequencies. We provide an implementation of the method, SVJedi, to genotype insertions and deletions with long reads. The tool has been applied to both simulated and real human datasets and achieves high genotyping accuracy. We also demonstrate that SV genotyping is considerably improved with SVJedi compared to other approaches, namely SV discovery and short read SV genotyping approaches. Availabilityhttps://github.com/llecompte/SVJedi.git Contactlolita.lecompte@inria.fr

bioinformatics↗

bioRxiv2019

Linking Allele-Specific Expression And Natural Selection In Wild Populations

Allele-specific expression (ASE) is a widely studied molecular mechanism at cell, tissue and organism levels. Here, we extrapolated the concept of ASE to the population-scale (psASE), aggregating ASEs detected at smaller scales. We developed a novel approach to detect psASE based on metagenomic and metatranscriptomic data of environmental samples containing communities of organisms. This approach which measures the deviation between the frequency and the relative expression of biallelic loci, was applied on samples collected during the Tara Oceans expedition (2009-2013), in combination to new Oithona similis transcriptomes, a widespread marine copepod. Among a total of 25,768 single nucleotide variants (SNVs) of O. similis, 587 (2.3%) were targeted by psASE in at least one population. The distribution of SNVs targeted by psASE in different populations is significantly shaped by population genomic differentiation (p-value = 9.3x10-9), supporting a partial genetic control of psASE. To investigate the link between evolution and psASE, loci under selection were compared to loci under psASE. A significant amount of SNVs (0.6%) were targeted by both selection and psASE (p-values < 9.89x10-3), supporting the hypothesis that natural selection and ASE may lead to the same phenotype. Population-scale ASE offers new insights into the gene regulation control in populations and its link with natural selection.

genomics↗

bioRxiv2019

Toward perfect reads: short reads correction via mapping on compacted de Bruijn graphs

MotivationsShort-read accuracy is important for downstream analyses such as genome assembly and hybrid long-read correction. Despite much work on short-read correction, present-day correctors either do not scale well on large data sets or consider reads as mere suites of k-mers, without taking into account their full-length read information. ResultsWe propose a new method to correct short reads using de Bruijn graphs, and implement it as a tool called Bcool. As a first step, Bcool constructs a compacted de Bruijn graph from the reads. This graph is filtered on the basis of k-mer abundance then of unitig abundance, thereby removing most sequencing errors. The cleaned graph is then used as a reference on which the reads are mapped to correct them. We show that this approach yields more accurate reads than k-mer-spectrum correctors while being scalable to human-size genomic datasets and beyond. Availability and ImplementationThe implementation is open source and available at http://github.com/Malfoy/BCOOL under the Affero GPL license and as a Bioconda package. ContactAntoine Limasset antoine.limasset@gmail.com & Jean-Francois Flot jflot@ulb.ac.be & Pierre Peterlongo pierre.peterlongo@inria.fr

bioinformatics↗

bioRxiv2019

ELECTOR: Evaluator for long reads correction methods

MotivationIn the last few years, the error rates of third generation sequencing data have been capped above 5%, including many insertions and deletions. Thereby, an increasing number of long reads correction methods have been proposed to reduce the noise in these sequences. Whether hybrid or self-correction methods, there exist multiple approaches to correct long reads. As the quality of the error correction has huge impacts on downstream processes, developing methods allowing to evaluate error correction tools with precise and reliable statistics is therefore a crucial need. Since error correction is often a resource bottleneck in long reads pipelines, a key feature of assessment methods is therefore to be efficient, in order to allow the fast comparison of different tools. ResultsWe propose ELECTOR, a reliable and efficient tool to evaluate long reads correction, that enables the evaluation of hybrid and self-correction methods. Our tool provides a complete and relevant set of metrics to assess the read quality improvement after correction and scales to large datasets. ELECTOR is directly compatible with a wide range of state-of-the-art error correction tools, using whether simulated or real long reads. We show that ELECTOR displays a wider range of metrics than the state-of-the-art tool, LRCstats, and additionally importantly decreases the runtime needed for assessment on all the studied datasets. AvailabilityELECTOR is available at https://github.com/kamimrcht/ELECTOR. Contactcamille.marchet@univ-lille.fr or pierre.morisse2@univ-rouen.fr

bioinformatics↗