Search

Your search keyword '"Pierre Peterlongo"' showing total 100 results
Start Over Author "Pierre Peterlongo"
100 results on '"Pierre Peterlongo"'

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

Author

Daniel J Richter, Romain Watteaux, Thomas Vannier, Jade Leconte, Paul Frémont, Gabriel Reygondeau, Nicolas Maillet, Nicolas Henry, Gaëtan Benoit, Ophélie Da Silva, Tom O Delmont, Antonio Fernàndez-Guerra, Samir Suweis, Romain Narci, Cédric Berney, Damien Eveillard, Frederick Gavory, Lionel Guidi, Karine Labadie, Eric Mahieu, Julie Poulain, Sarah Romac, Simon Roux, Céline Dimier, Stefanie Kandels, Marc Picheral, Sarah Searson, Tara Oceans Coordinators, Stéphane Pesant, Jean-Marc Aury, Jennifer R Brum, Claire Lemaitre, Eric Pelletier, Peer Bork, Shinichi Sunagawa, Fabien Lombard, Lee Karp-Boss, Chris Bowler, Matthew B Sullivan, Eric Karsenti, Mahendra Mariadassou, Ian Probert, Pierre Peterlongo, Patrick Wincker, Colomban de Vargas, Maurizio Ribera d'Alcalà, Daniele Iudicone, and Olivier Jaillon

Subjects
plankton biogeography, metagenomics, metabarcoding, microbial oceanography, Medicine, Science, Biology (General), QH301-705.5
Abstract

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.

Published
2022
Full Text
View/download PDF

2. Investigating population‐scale allelic differential expression in wild populations of Oithona similis (Cyclopoida, Claus, 1866)

Author

Romuald Laso‐Jadart, Kevin Sugier, Emmanuelle Petit, Karine Labadie, Pierre Peterlongo, Christophe Ambroise, Patrick Wincker, Jean‐Louis Jamet, and Mohammed‐Amin Madoui

Subjects
allelic expression, Arctic seas, copepod, metagenomics, metatranscriptomics, selection, Ecology, QH540-549.5
Abstract

Abstract Acclimation allowed by variation in gene or allele expression in natural populations is increasingly understood as a decisive mechanism, as much as adaptation, for species evolution. However, for small eukaryotic organisms, as species from zooplankton, classical methods face numerous challenges. Here, we propose the concept of allelic differential expression at the population‐scale (psADE) to investigate the variation in allele expression in natural populations. We developed a novel approach to detect psADE based on metagenomic and metatranscriptomic data from environmental samples. This approach was applied on the widespread marine copepod, Oithona similis, by combining samples collected during the Tara Oceans expedition (2009–2013) and de novo transcriptome assemblies. Among a total of 25,768 single nucleotide variants (SNVs) of O. similis, 572 (2.2%) were affected by psADE in at least one population (FDR

Published
2020
Full Text
View/download PDF

3. Finding all maximal perfect haplotype blocks in linear time

Author

Jarno Alanko, Hideo Bannai, Bastien Cazaux, Pierre Peterlongo, and Jens Stoye

Subjects
Population genomics, Selection coefficient, Haplotype block, Positional Burrows–Wheeler Transform, Biology (General), QH301-705.5, Genetics, QH426-470
Abstract

Abstract Recent large-scale community sequencing efforts allow at an unprecedented level of detail the identification of genomic regions that show signatures of natural selection. Traditional methods for identifying such regions from individuals’ haplotype data, however, require excessive computing times and therefore are not applicable to current datasets. In 2019, Cunha et al. (Advances in bioinformatics and computational biology: 11th Brazilian symposium on bioinformatics, BSB 2018, Niterói, Brazil, October 30 - November 1, 2018, Proceedings, 2018. https://doi.org/10.1007/978-3-030-01722-4_3 ) suggested the maximal perfect haplotype block as a very simple combinatorial pattern, forming the basis of a new method to perform rapid genome-wide selection scans. The algorithm they presented for identifying these blocks, however, had a worst-case running time quadratic in the genome length. It was posed as an open problem whether an optimal, linear-time algorithm exists. In this paper we give two algorithms that achieve this time bound, one conceptually very simple one using suffix trees and a second one using the positional Burrows–Wheeler Transform, that is very efficient also in practice.

Published
2020
Full Text
View/download PDF

4. Cytosine methylation of mature microRNAs inhibits their functions and is associated with poor prognosis in glioblastoma multiforme

Author

Mathilde Cheray, Amandine Etcheverry, Camille Jacques, Romain Pacaud, Gwenola Bougras-Cartron, Marc Aubry, Florent Denoual, Pierre Peterlongo, Arulraj Nadaradjane, Joséphine Briand, Farida Akcha, Dominique Heymann, François M. Vallette, Jean Mosser, Benjamin Ory, and Pierre-François Cartron

Subjects
miRNA, Cytosine-methylation, Epigenetics, DNMT3A, AGO4, Glioblastoma, Neoplasms. Tumors. Oncology. Including cancer and carcinogens, RC254-282
Abstract

Abstract Background Literature reports that mature microRNA (miRNA) can be methylated at adenosine, guanosine and cytosine. However, the molecular mechanisms involved in cytosine methylation of miRNAs have not yet been fully elucidated. Here we investigated the biological role and underlying mechanism of cytosine methylation in miRNAs in glioblastoma multiforme (GBM). Methods RNA immunoprecipitation with the anti-5methylcytosine (5mC) antibody followed by Array, ELISA, dot blot, incorporation of a radio-labelled methyl group in miRNA, and miRNA bisulfite sequencing were perfomred to detect the cytosine methylation in mature miRNA. Cross-Linking immunoprecipiation qPCR, transfection with methylation/unmethylated mimic miRNA, luciferase promoter reporter plasmid, Biotin-tagged 3’UTR/mRNA or miRNA experiments and in vivo assays were used to investigate the role of methylated miRNAs. Finally, the prognostic value of methylated miRNAs was analyzed in a cohorte of GBM pateints. Results Our study reveals that a significant fraction of miRNAs contains 5mC. Cellular experiments show that DNMT3A/AGO4 methylated miRNAs at cytosine residues inhibit the formation of miRNA/mRNA duplex and leading to the loss of their repressive function towards gene expression. In vivo experiments show that cytosine-methylation of miRNA abolishes the tumor suppressor function of miRNA-181a-5p miRNA for example. Our study also reveals that cytosine-methylation of miRNA-181a-5p results is associated a poor prognosis in GBM patients. Conclusion Together, our results indicate that the DNMT3A/AGO4-mediated cytosine methylation of miRNA negatively. Graphical abstract

Published
2020
Full Text
View/download PDF

5. StrainFLAIR: strain-level profiling of metagenomic samples using variation graphs

Author

Kévin Da Silva, Nicolas Pons, Magali Berland, Florian Plaza Oñate, Mathieu Almeida, and Pierre Peterlongo

Subjects
Metagenomics, Variation graphs, Strain-level abundances, Read mapping, Medicine, Biology (General), QH301-705.5
Abstract

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.

Published
2021
Full Text
View/download PDF

6. Peptimapper: proteogenomics workflow for the expert annotation of eukaryotic genomes

Author

Laetitia Guillot, Ludovic Delage, Alain Viari, Yves Vandenbrouck, Emmanuelle Com, Andrés Ritter, Régis Lavigne, Dominique Marie, Pierre Peterlongo, Philippe Potin, and Charles Pineau

Subjects
Bioinformatics, Genome annotation, Peptide sequence tag, Proteogenomics, Proteomics, Tandem mass spectrometry, Biotechnology, TP248.13-248.65, Genetics, QH426-470
Abstract

Abstract Background Accurate structural annotation of genomes is still a challenge, despite the progress made over the past decade. The prediction of gene structure remains difficult, especially for eukaryotic species, and is often erroneous and incomplete. We used a proteogenomics strategy, taking advantage of the combination of proteomics datasets and bioinformatics tools, to identify novel protein coding-genes and splice isoforms, assign correct start sites, and validate predicted exons and genes. Results Our proteogenomics workflow, Peptimapper, was applied to the genome annotation of Ectocarpus sp., a key reference genome for both the brown algal lineage and stramenopiles. We generated proteomics data from various life cycle stages of Ectocarpus sp. strains and sub-cellular fractions using a shotgun approach. First, we directly generated peptide sequence tags (PSTs) from the proteomics data. Second, we mapped PSTs onto the translated genomic sequence. Closely located hits (i.e., PSTs locations on the genome) were then clustered to detect potential coding regions based on parameters optimized for the organism. Third, we evaluated each cluster and compared it to gene predictions from existing conventional genome annotation approaches. Finally, we integrated cluster locations into GFF files to use a genome viewer. We identified two potential novel genes, a ribosomal protein L22 and an aryl sulfotransferase and corrected the gene structure of a dihydrolipoamide acetyltransferase. We experimentally validated the results by RT-PCR and using transcriptomics data. Conclusions Peptimapper is a complementary tool for the expert annotation of genomes. It is suitable for any organism and is distributed through a Docker image available on two public bioinformatics docker repositories: Docker Hub and BioShaDock. This workflow is also accessible through the Galaxy framework and for use by non-computer scientists at https://galaxy.protim.eu. Data are available via ProteomeXchange under identifier PXD010618.

Published
2019
Full Text
View/download PDF

7. DiscoSnp-RAD: de novo detection of small variants for RAD-Seq population genomics

Author

Jérémy Gauthier, Charlotte Mouden, Tomasz Suchan, Nadir Alvarez, Nils Arrigo, Chloé Riou, Claire Lemaitre, and Pierre Peterlongo

Subjects
RAD-seq, SNPs, Reference-free, Insertions, Deletions, Variants, Medicine, Biology (General), QH301-705.5
Abstract

Restriction site Associated DNA Sequencing (RAD-Seq) is a technique characterized by the sequencing of specific loci along the genome that is widely employed in the field of evolutionary biology since it allows to exploit variants (mainly Single Nucleotide Polymorphism—SNPs) information from entire populations at a reduced cost. Common RAD dedicated tools, such as STACKS or IPyRAD, are based on all-vs-all read alignments, which require consequent time and computing resources. We present an original method, DiscoSnp-RAD, that avoids this pitfall since variants are detected by exploiting specific parts of the assembly graph built from the reads, hence preventing all-vs-all read alignments. We tested the implementation on simulated datasets of increasing size, up to 1,000 samples, and on real RAD-Seq data from 259 specimens of Chiastocheta flies, morphologically assigned to seven species. All individuals were successfully assigned to their species using both STRUCTURE and Maximum Likelihood phylogenetic reconstruction. Moreover, identified variants succeeded to reveal a within-species genetic structure linked to the geographic distribution. Furthermore, our results show that DiscoSnp-RAD is significantly faster than state-of-the-art tools. The overall results show that DiscoSnp-RAD is suitable to identify variants from RAD-Seq data, it does not require time-consuming parameterization steps and it stands out from other tools due to its completely different principle, making it substantially faster, in particular on large datasets.

Published
2020
Full Text
View/download PDF

8. metaVaR: Introducing metavariant species models for reference-free metagenomic-based population genomics.

Author

Romuald Laso-Jadart, Christophe Ambroise, Pierre Peterlongo, and Mohammed-Amin Madoui

Subjects
Medicine, Science
Abstract

The availability of large metagenomic data offers great opportunities for the population genomic analysis of uncultured organisms, which represent a large part of the unexplored biosphere and play a key ecological role. However, the majority of these organisms lack a reference genome or transcriptome, which constitutes a technical obstacle for classical population genomic analyses. We introduce the metavariant species (MVS) model, in which a species is represented 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 variants into MVSs directly from multisample metagenomic raw reads without a reference genome or read 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 MVS construction was tested on simulated and real metagenomic data. MVSs showed the required quality for robust population genomics and allowed an accurate estimation of genomic differentiation (ΔFST < 0.0001 and

Published
2020
Full Text
View/download PDF

9. A de novo approach to disentangle partner identity and function in holobiont systems

Author

Arnaud Meng, Camille Marchet, Erwan Corre, Pierre Peterlongo, Adriana Alberti, Corinne Da Silva, Patrick Wincker, Eric Pelletier, Ian Probert, Johan Decelle, Stéphane Le Crom, Fabrice Not, and Lucie Bittner

Subjects
Holobiont, Meta-transcriptomic, De novo assembly, Marine, Plankton, k-mer based similarity, Microbial ecology, QR100-130
Abstract

Abstract Background Study of meta-transcriptomic datasets involving non-model organisms represents bioinformatic challenges. The production of chimeric sequences and our inability to distinguish the taxonomic origins of the sequences produced are inherent and recurrent difficulties in de novo assembly analyses. As the study of holobiont meta-transcriptomes is affected by challenges invoked above, we propose an innovative bioinformatic approach to tackle such difficulties and tested it on marine models as a proof of concept. Results We considered three holobiont models, of which two transcriptomes were previously published and a yet unpublished transcriptome, to analyze and sort their raw reads using Short Read Connector, a k-mer based similarity method. Before assembly, we thus defined four distinct categories for each holobiont meta-transcriptome: host reads, symbiont reads, shared reads, and unassigned reads. Afterwards, we observed that independent de novo assemblies for each category led to a diminution of the number of chimeras compared to classical assembly methods. Moreover, the separation of each partner’s transcriptome offered the independent and comparative exploration of their functional diversity in the holobiont. Finally, our strategy allowed to propose new functional annotations for two well-studied holobionts (a Cnidaria-Dinophyta, a Porifera-Bacteria) and a first meta-transcriptome from a planktonic Radiolaria-Dinophyta system forming widespread symbiotic association for which our knowledge is considerably limited. Conclusions In contrast to classical assembly approaches, our bioinformatic strategy generates less de novo assembled chimera and allows biologists to study separately host and symbiont data from a holobiont mixture. The pre-assembly separation of reads using an efficient tool as Short Read Connector is an effective way to tackle meta-transcriptomic challenges and offers bright perpectives to study holobiont systems composed of either well-studied or poorly characterized symbiotic lineages and ultimately expand our knowledge about these associations.

Published
2018
Full Text
View/download PDF

10. Multiple comparative metagenomics using multiset k-mer counting

Author

Gaëtan Benoit, Pierre Peterlongo, Mahendra Mariadassou, Erwan Drezen, Sophie Schbath, Dominique Lavenier, and Claire Lemaitre

Subjects
Comparative metagenomics, k-mer, k-mer counting, Metagenomic, Large scale, Ecological distance, Electronic computers. Computer science, QA75.5-76.95
Abstract

Background Large scale metagenomic projects aim to extract biodiversity knowledge between different environmental conditions. Current methods for comparing microbial communities face important limitations. Those based on taxonomical or functional assignation rely on a small subset of the sequences that can be associated to known organisms. On the other hand, de novo methods, that compare the whole sets of sequences, either do not scale up on ambitious metagenomic projects or do not provide precise and exhaustive results. Methods These limitations motivated the development of a new de novo metagenomic comparative method, called Simka. This method computes a large collection of standard ecological distances by replacing species counts by k-mer counts. Simka scales-up today’s metagenomic projects thanks to a new parallel k-mer counting strategy on multiple datasets. Results Experiments on public Human Microbiome Project datasets demonstrate that Simka captures the essential underlying biological structure. Simka was able to compute in a few hours both qualitative and quantitative ecological distances on hundreds of metagenomic samples (690 samples, 32 billions of reads). We also demonstrate that analyzing metagenomes at the k-mer level is highly correlated with extremely precise de novo comparison techniques which rely on all-versus-all sequences alignment strategy or which are based on taxonomic profiling.

Published
2016
Full Text
View/download PDF

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

Author

Lucas Robidou and Pierre Peterlongo

Subjects
Statistics and Probability, Computational Mathematics, Computational Theory and Mathematics, Molecular Biology, Biochemistry, Computer Science Applications
Abstract

Motivation High 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. Results We 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. Availability and implementation https://github.com/lrobidou/fimpera.

Published
2023

20. HaploBlocks: efficient detection of positive selection in large population genomic datasets

Author

Benedikt Kirsch-Gerweck, Leonard Bohnenkämper, Michel T Henrichs, Jarno N Alanko, Hideo Bannai, Bastien Cazaux, Pierre Peterlongo, Joachim Burger, Jens Stoye, Yoan Diekmann, Department of Computer Science, Genome-scale Algorithmics research group / Veli Mäkinen, and Algorithmic Bioinformatics

Subjects
Big data, Population genetics, Natural selection, 1181 Ecology, evolutionary biology, Genetics, Genome scan, Molecular Biology, Ecology, Evolution, Behavior and Systematics
Abstract

Genomic regions under positive selection harbour variation linked for example to adaptation. Most tools for detecting positively selected variants have computational resource requirements rendering them impractical on population genomic datasets with hundreds of thousands of individuals or more. We have developed and implemented an efficient haplotype-based approach able to scan large datasets and accurately detect positive selection. We achieve this by combining a pattern matching approach based on the positional Burrows-Wheeler transform with model-based inference which only requires the evaluation of closed-form expressions. We evaluate our approach with simulations, and find it to be both sensitive and specific. The computational resource requirements quantified using UK Biobank data indicate that our implementation is scalable to population genomic datasets with millions of individuals. Our approach may serve as an algorithmic blueprint for the era of 'big data' genomics: a combinatorial core coupled with statistical inference in closed form. © The Author(s) 2023. Published by Oxford University Press on behalf of Society for Molecular Biology and Evolution.

Published
2023

21. kmdiff, large-scale and user-friendly differential k-mer analyses

Author

Téo Lemane, Rayan Chikhi, Pierre Peterlongo, Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Algorithmes pour les séquences biologiques - Sequence Bioinformatics, Institut Pasteur [Paris] (IP)-Université Paris Cité (UPCité), This work was supported by the IPL Inria Neuromarkers, ANR Inception (ANR-16-CONV-0005), ANR Prairie (ANR-19-P3IA-0001), ANR SeqDigger (ANR-19-CE45-0008), H2020 ITN ALPACA (956229)., ANR-16-CONV-0005,INCEPTION,Institut Convergences pour l'étude de l'Emergence des Pathologies au Travers des Individus et des populatiONs(2016), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), ANR-19-CE45-0008,SeqDigger,Moteur de recherche de donne´es de se´quenc¸age en ge´nomique environnementale(2019), and European Project: 956229,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions,ALPACA(2021)

Subjects
Statistics and Probability, MESH: Sequence Analysis, DNA, Genotype, Sequence Analysis, DNA, Biochemistry, Computer Science Applications, MESH: Genotype, Computational Mathematics, Computational Theory and Mathematics, MESH: Genome-Wide Association Study, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular Biology, Software, Algorithms, Genome-Wide Association Study
Abstract

Summary Genome wide association studies elucidate links between genotypes and phenotypes. Recent studies point out the interest of conducting such experiments using k-mers as the base signal instead of single-nucleotide polymorphisms. We propose a tool, kmdiff, that performs differential k-mer analyses on large sequencing cohorts in an order of magnitude less time and memory than previously possible. Availabilityand implementation https://github.com/tlemane/kmdiff Supplementary information Supplementary data are available at Bioinformatics online.

Published
2022

24. The K-mer File Format: a standardized and compact disk representation of sets of k-mers

Author

Yoann Dufresne, Teo Lemane, Pierre Marijon, Pierre Peterlongo, Amatur Rahman, Marek Kokot, Paul Medvedev, Sebastian Deorowicz, Rayan Chikhi, Département de Biologie Computationnelle - Department of Computational Biology, Institut Pasteur [Paris] (IP)-Université Paris Cité (UPCité), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Heinrich Heine Universität Düsseldorf = Heinrich Heine University [Düsseldorf], Pennsylvania State University (Penn State), Penn State System, Silesian University of Technology, R.C. was funded by ANR Inception (ANR-16-CONV-0005) and PRAIRIE [ANR-19-P3IA-0001] grants. M.K. and S.D. were supported by the National Science Centre, Poland [DEC-2019/33/B/ST6/02040]. Work supported in part by the National Science Foundation [1453527 and 1931531], and by the European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skłodowska-Curie grant agreement No 956229., ANR-16-CONV-0005,INCEPTION,Institut Convergences pour l'étude de l'Emergence des Pathologies au Travers des Individus et des populatiONs(2016), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), and European Project: 956229,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions,ALPACA(2021)

Subjects
Statistics and Probability, Compact Disks, Computational Mathematics, Computational Theory and Mathematics, Sequence Analysis, DNA, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular Biology, Biochemistry, Software, Algorithms, Computer Science Applications
Abstract

Summary Bioinformatics applications increasingly rely on ad hoc disk storage of k-mer sets, e.g. for de Bruijn graphs or alignment indexes. Here, we introduce the K-mer File Format as a general lossless framework for storing and manipulating k-mer sets, realizing space savings of 3–5× compared to other formats, and bringing interoperability across tools. Availability and implementation Format specification, C++/Rust API, tools: https://github.com/Kmer-File-Format/. Supplementary information Supplementary data are available at Bioinformatics online.

Published
2022

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

Author

Lucas Robidou, Pierre Peterlongo, Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), and ANR-19-CE45-0008,SeqDigger,Moteur de recherche de donne´es de se´quenc¸age en ge´nomique environnementale(2019)

Subjects
abundance, data structure indexation k-mers counting Bloom filters sequence data abundance AMQ, AMQ, sequence data, [INFO]Computer Science [cs], data structure, indexation, k-mers, counting Bloom filters
Abstract

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 lengthk, calledk-mers. Many applications, such as metagenomics, require the abundance of indexedk-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 thek-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 ofk-mers with their abundance, but at the expense of a sensible false positive rate.ResultsWe propose a novel algorithm, calledfimpera, 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.fimperadoes not introduce any memory overhead and may even reduces the query time.Availabilityhttps://github.com/lrobidou/fimperaSupplementary informationSupplementary data are available atBioinformaticsonline.

Published
2022

36. Critical Assessment of Metagenome Interpretation: the second round of challenges

Author

Fernando Meyer, Adrian Fritz, Zhi-Luo Deng, David Koslicki, Till Robin Lesker, Alexey Gurevich, Gary Robertson, Mohammed Alser, Dmitry Antipov, Francesco Beghini, Denis Bertrand, Jaqueline J. Brito, C. Titus Brown, Jan Buchmann, Aydin Buluç, Bo Chen, Rayan Chikhi, Philip T. L. C. Clausen, Alexandru Cristian, Piotr Wojciech Dabrowski, Aaron E. Darling, Rob Egan, Eleazar Eskin, Evangelos Georganas, Eugene Goltsman, Melissa A. Gray, Lars Hestbjerg Hansen, Steven Hofmeyr, Pingqin Huang, Luiz Irber, Huijue Jia, Tue Sparholt Jørgensen, Silas D. Kieser, Terje Klemetsen, Axel Kola, Mikhail Kolmogorov, Anton Korobeynikov, Jason Kwan, Nathan LaPierre, Claire Lemaitre, Chenhao Li, Antoine Limasset, Fabio Malcher-Miranda, Serghei Mangul, Vanessa R. Marcelino, Camille Marchet, Pierre Marijon, Dmitry Meleshko, Daniel R. Mende, Alessio Milanese, Niranjan Nagarajan, Jakob Nissen, Sergey Nurk, Leonid Oliker, Lucas Paoli, Pierre Peterlongo, Vitor C. Piro, Jacob S. Porter, Simon Rasmussen, Evan R. Rees, Knut Reinert, Bernhard Renard, Espen Mikal Robertsen, Gail L. Rosen, Hans-Joachim Ruscheweyh, Varuni Sarwal, Nicola Segata, Enrico Seiler, Lizhen Shi, Fengzhu Sun, Shinichi Sunagawa, Søren Johannes Sørensen, Ashleigh Thomas, Chengxuan Tong, Mirko Trajkovski, Julien Tremblay, Gherman Uritskiy, Riccardo Vicedomini, Zhengyang Wang, Ziye Wang, Zhong Wang, Andrew Warren, Nils Peder Willassen, Katherine Yelick, Ronghui You, Georg Zeller, Zhengqiao Zhao, Shanfeng Zhu, Jie Zhu, Ruben Garrido-Oter, Petra Gastmeier, Stephane Hacquard, Susanne Häußler, Ariane Khaledi, Friederike Maechler, Fantin Mesny, Simona Radutoiu, Paul Schulze-Lefert, Nathiana Smit, Till Strowig, Andreas Bremges, Alexander Sczyrba, Alice Carolyn McHardy, Braunschweig Integrated Centre of Systems Biology [Braunschweig] (BRICS), Technische Universität Braunschweig = Technical University of Braunschweig [Braunschweig]-Helmholtz Centre for Infection Research (HZI), Pennsylvania State University (Penn State), Penn State System, German Center for Infection Research - partner site Hannover-Braunschweig (DZIF), Saint Petersburg State University (SPBU), Department of Information Technology and Electrical Engineering [Zürich] (D-ITET), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Center for Algorithmic Biotechnology [Saint Petersburg], Institute of Translational Biomedicine [Saint-Petersburg], Saint Petersburg University (SPBU)-Saint Petersburg University (SPBU), Centre for Integrative Biology (CIBIO), University of Trento (CIBIO), University of Trento [Trento], Genome Institute of Singapore (GIS), University of Southern California (USC), University of California [Davis] (UC Davis), University of California (UC), Heinrich Heine Universität Düsseldorf = Heinrich Heine University [Düsseldorf], Lawrence Berkeley National Laboratory [Berkeley] (LBNL), Institut Pasteur [Paris] (IP), National Food Institute [Lyngby] (Forside), Drexel University, Robert Koch Institute [Berlin] (RKI), University of Technology Sydney (UTS), DOE Joint Genome Institute [Walnut Creek], University of California [Los Angeles] (UCLA), Intel Corporation [Santa Clara], Intel Corporation [USA], Department of Plant and Environmental Sciences [Frederiksberg], University of Copenhagen = Københavns Universitet (UCPH), Fudan University [Shanghai], Beijing Genomics Institute [Shenzhen] (BGI), Novo Nordisk Foundation Center for Biosustainability, Danmarks Tekniske Universitet = Technical University of Denmark (DTU), Université de Genève = University of Geneva (UNIGE), The Arctic University of Norway [Tromsø, Norway] (UiT), Charité - UniversitätsMedizin = Charité - University Hospital [Berlin], University of California [San Diego] (UC San Diego), University of Wisconsin-Madison, Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Hasso Plattner Institute [Potsdam, Germany], The University of Sydney, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Amsterdam UMC - Amsterdam University Medical Center, Structural and Computational Biology, European Molecular Biology Laboratory [Heidelberg] (EMBL), DTU Electrical Engineering [Lyngby], National Institutes of Health [Bethesda] (NIH), Department of Biology [ETH Zürich] (D-BIOL), University of Virginia, IT University of Copenhagen (ITU), Freie Universität Berlin, University of Potsdam = Universität Potsdam, Florida International University [Miami] (FIU), National Research Council of Canada (NRC), Phase Genomics [Seattle], Max Planck Institute for Plant Breeding Research (MPIPZ), Helmholtz Centre for Infection Research (HZI), Aarhus University [Aarhus], Center for Biotechnology (CeBiTec), Universität Bielefeld = Bielefeld University, Open access funding provided by Helmholtz-Zentrum für Infektionsforschung GmbH (HZI), ANR-16-CONV-0005,INCEPTION,Institut Convergences pour l'étude de l'Emergence des Pathologies au Travers des Individus et des populatiONs(2016), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), and Medical Microbiology and Infection Prevention

Subjects
06 Biological Sciences, 10 Technology, 11 Medical and Health Sciences, Reproducibility of Results, Cell Biology, DNA, Sequence Analysis, DNA, Biochemistry, Archaea, Software, Metagenome, Metagenomics, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular Biology, Sequence Analysis, Biotechnology, Developmental Biology
Abstract

Evaluating metagenomic software is key for optimizing metagenome interpretation and focus of the Initiative for the Critical Assessment of Metagenome Interpretation (CAMI). The CAMI II challenge engaged the community to assess methods on realistic and complex datasets with long- and short-read sequences, created computationally from around 1,700 new and known genomes, as well as 600 new plasmids and viruses. Here we analyze 5,002 results by 76 program versions. Substantial improvements were seen in assembly, some due to long-read data. Related strains still were challenging for assembly and genome recovery through binning, as was assembly quality for the latter. Profilers markedly matured, with taxon profilers and binners excelling at higher bacterial ranks, but underperforming for viruses and Archaea. Clinical pathogen detection results revealed a need to improve reproducibility. Runtime and memory usage analyses identified efficient programs, including top performers with other metrics. The results identify challenges and guide researchers in selecting methods for analyses., Nature Methods, 19 (8), ISSN:1548-7105, ISSN:1548-7091

Published
2022

38. Critical Assessment of Metagenome Interpretation - the second round of challenges

Author

Zho. Wang, Ariane Khaledi, Alice C. McHardy, Anton Korobeynikov, A. Cristian, Gherman Uritskiy, Huijue Jia, Philip Thomas Lanken Conradsen Clausen, Till Strowig, Denis Bertrand, N. Smit, Niranjan Nagarajan, Enrico Seiler, Adam G. Thomas, David Koslicki, Piotr Wojtek Dabrowski, Vitor C. Piro, Andreas Bremges, L. Oliker, Petra Gastmeier, Steven Hofmeyr, Zhe Wang, Jason C. Kwan, Alessio Milanese, Tue Sparholt Jørgensen, Mohammed Alser, J. S. Porter, Alexander Sczyrba, Georg Zeller, Bernhard Y. Renard, Chenhao Li, Riccardo Vicedomini, Chengxuan Tong, Andrew S. Warren, Jaqueline J. Brito, Alexey Gurevich, Axel Kola, C.T. Brown, Julien Tremblay, Shinichi Sunagawa, F. Maechler, G. Robertson, Jakob Nybo Nissen, Ruben Garrido-Oter, Rob Egan, Simon Rasmussen, Katherine Yelick, Fernando Meyer, Zhengqiao Zhao, Daniel R Mende, Shanfeng Zhu, Lizhen Shi, F. Malcher-Miranda, Fengzhu Sun, Zi. Wang, Lars Hestbjerg Hansen, J. Buchmann, S. D. Kieser, Jie Zhu, E. M. Robertsen, Fantin Mesny, Sergey Nurk, Pierre Marijon, Dmitry Meleshko, Gail L. Rosen, Nicola Segata, Nathan LaPierre, Eugene Goltsman, Varuni Sarwal, Mirko Trajkovski, Dmitry Antipov, P. Huang, Vanesa R. Marcelino, Francesco Beghini, Antoine Limasset, Rayan Chikhi, Eleazar Eskin, M. A. Gray, Camille Marchet, Lucas Paoli, Adrian Fritz, Evangelos Georganas, Zhi-Luo Deng, T. Klemetsen, Hans-Joachim Ruscheweyh, Evan R. Rees, S. Häußler, Simona Radutoiu, Stéphane Hacquard, Paul Schulze-Lefert, Mikhail Kolmogorov, N. P. Willassen, Pierre Peterlongo, Knut Reinert, Claire Lemaitre, Ronghui You, Søren J. Sørensen, Aydin Buluc, Luiz Irber, Serghei Mangul, B. Chen, and Aaron E. Darling

Subjects
Taxon, Pathogen detection, Microbial Genomes, Metagenomics, Computer science, Critical assessment, Computational biology, Taxonomic rank, Genome
Abstract

Evaluating metagenomic software is key for optimizing metagenome interpretation and focus of the community-driven initiative for the Critical Assessment of Metagenome Interpretation (CAMI). In its second challenge, CAMI engaged the community to assess their methods on realistic and complex metagenomic datasets with long and short reads, created from ∼1,700 novel and known microbial genomes, as well as ∼600 novel plasmids and viruses. Altogether 5,002 results by 76 program versions were analyzed, representing a 22x increase in results.Substantial improvements were seen in metagenome assembly, some due to using long-read data. The presence of related strains still was challenging for assembly and genome binning, as was assembly quality for the latter. Taxon profilers demonstrated a marked maturation, with taxon profilers and binners excelling at higher bacterial taxonomic ranks, but underperforming for viruses and archaea. Assessment of clinical pathogen detection techniques revealed a need to improve reproducibility. Analysis of program runtimes and memory usage identified highly efficient programs, including some top performers with other metrics. The CAMI II results identify current challenges, but also guide researchers in selecting methods for specific analyses.

Published
2021

39. Discovering millions of plankton genomic markers from the Atlantic Ocean and the Mediterranean Sea

Author

Olivier Jaillon, Mohammed-Amin Madoui, Kevin Sugier, Daniele Iudicone, Pierre Peterlongo, Jérémy Gauthier, Majda Arif, Patrick Wincker, Génomique métabolique (UMR 8030), Genoscope - Centre national de séquençage [Evry] (GENOSCOPE), Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université d'Évry-Val-d'Essonne (UEVE)-Centre National de la Recherche Scientifique (CNRS), Institut de Biologie François JACOB (JACOB), Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Stazione Zoologica Anton Dohrn (SZN), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université d'Évry-Val-d'Essonne (UEVE), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)

Subjects
Genetic Markers, 0106 biological sciences, 0301 basic medicine, Aquatic Organisms, Genotyping Techniques, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Population, Context (language use), Biology, 010603 evolutionary biology, 01 natural sciences, Zooplankton, 03 medical and health sciences, Mediterranean sea, Mediterranean Sea, Genetics, Animals, [SDV.BBM]Life Sciences [q-bio]/Biochemistry, Molecular Biology, 14. Life underwater, education, Atlantic Ocean, Ecology, Evolution, Behavior and Systematics, education.field_of_study, Natural selection, fungi, Plankton, Genetics, Population, 030104 developmental biology, Metagenomics, Evolutionary biology, Genetic structure, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], [SDE.BE]Environmental Sciences/Biodiversity and Ecology, Biotechnology
Abstract

International audience; Comparison of the molecular diversity in all plankton populations present in geographically distant water columns may allow for a holistic view of the connectivity, isolation and adaptation of organisms in the marine environment. In this context, a large‐scale detection and analysis of genomic variants directly in metagenomic data appeared as a powerful strategy for the identification of genetic structures and genes under natural selection in plankton. Here, we used DiscoSnp++, a reference‐free variant caller, to produce genetic variants from large‐scale metagenomic data and assessed its accuracy on the copepod Oithona nana in terms of variant calling, allele frequency estimation and population genomic statistics by comparing it to the state‐of‐the‐art method. DiscoSnp++ produces variants leading to similar conclusions regarding the genetic structure and identification of loci under natural selection. DiscoSnp++ was then applied to 120 metagenomic samples from four size fractions, including prokaryotes, protists and zooplankton sampled from 39 Tara Oceans sampling stations located in the Atlantic Ocean and the Mediterranean Sea to produce a new set of marine genomic markers containing more than 19 million of variants. This new genomic resource can be used by the community to relocate these markers on their plankton genomes or transcriptomes of interest. This resource will be updated with new marine expeditions and the increase of metagenomic data (availability: http://bioinformatique.rennes.inria.fr/taravariants/)

Published
2019

40. Approximate Hashing for Bioinformatics

Author

Pierre Peterlongo, Shmuel T. Klein, Guy Arbitman, Dana Shapira, Department of Computer Science [Bar Ilan], Bar-Ilan University [Israël], Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Ariel University Center (AUC), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Department of Computer Science and Mathematics [Ariel university], Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique)

Subjects
0301 basic medicine, Computer science, 0206 medical engineering, Hash function, 02 engineering and technology, 0102 computer and information sciences, Bioinformatics, 01 natural sciences, Field (computer science), Set (abstract data type), 03 medical and health sciences, Data_FILES, Data deduplication, Cluster analysis, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology, Lossless compression, 0303 health sciences, String (computer science), Outcome (probability), Substring, 030104 developmental biology, 010201 computation theory & mathematics, Large set (Ramsey theory), [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Algorithm, 020602 bioinformatics, Data compression
Abstract

A particular form of lossless data compression is known as deduplication, which is often applied in a scenario in which a large data repository is given and we wish to store a new, updated, version of it, in which the changes account only for a tiny fraction of the accumulated information. The idea is then to find duplicated parts and store only one copy P of them; the second and subsequent occurrences of these parts can then be replaced by pointers to P. One of the approaches to solve the problem is based on classical hashing with the property that when changing even a single bit of the file, the resulting hash value should be completely different, which may not be appropriate in our case. This lead to the design of what could be called an Approximate Hash function. The current work is an extension, which applies similar techniques to string processing problems arising in Bioinformatics. We concentrate on the following two problems. The first problem is that of clustering a large collection of DNA strings into sub-collections forming clusters, in the sense that strings assigned to the same cluster may be considered as similar for practical biological purposes, whereas strings of different clusters are different enough to be judged not originating from the same source. The second problem is that of locating a single string within a large collection on the basis of one of its fragments, or rather, one of its fragments that has undergone some limited number of mutations. We show how our notion of an approximate hash may be adapted to these and similar problems. The idea is to produce a signature encapsulating the main features of the strings in a small number of bits by devising an occurrence map of the various substrings of length k, called k-mers, for k ≥ 1. The ith bit of the signature, corresponding to the i-th ordered k-mer, will be set to 1 if and only if the number of occurrences of this i-th k-mer within the given string is larger than some predetermined threshold t_k, depending on their average number of occurrences. This definition tries to catch underlying similarities, but to remain flexible enough to allow some fluctuations. The new techniques have been applied on artificial and real-life DNA strings, and compared to state of the art clustering methods. The outcome of the new procedure is very similar to the clustering and search results obtained by accurate tools, but in much less time and with less required memory.

Published
2021

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

Author

Pierre Peterlongo, Christophe Ambroise, Mohammed-Amin Madoui, Romuald Laso-Jadart, Génomique métabolique (UMR 8030), Genoscope - Centre national de séquençage [Evry] (GENOSCOPE), Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université d'Évry-Val-d'Essonne (UEVE)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques et Modélisation d'Evry (LaMME), Université d'Évry-Val-d'Essonne (UEVE)-ENSIIE-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université d'Évry-Val-d'Essonne (UEVE), Université d'Évry-Val-d'Essonne (UEVE)-ENSIIE-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Transcriptome, Population genomics, 0302 clinical medicine, Invertebrate Genomics, Natural Selection, Cluster Analysis, 0303 health sciences, education.field_of_study, Multidisciplinary, Natural selection, Bacterial Genomics, Applied Mathematics, Simulation and Modeling, Microbial Genetics, Genomics, Physical Sciences, [SDE]Environmental Sciences, Medicine, Algorithms, Research Article, Evolutionary Processes, Science, Population, Single-nucleotide polymorphism, Sequence alignment, Computational biology, Microbial Genomics, Biology, Research and Analysis Methods, Microbiology, 03 medical and health sciences, Clustering Algorithms, Genetics, Bacterial Genetics, Selection, Genetic, Cluster analysis, education, 030304 developmental biology, Evolutionary Biology, Models, Genetic, Computational Biology, Genetic Variation, Biology and Life Sciences, Bacteriology, Genome Analysis, Genetics, Population, Metagenomics, Animal Genomics, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], [SDE.BE]Environmental Sciences/Biodiversity and Ecology, 030217 neurology & neurosurgery, Software, Mathematics, Reference genome
Abstract

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 asFSTin 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 (Δ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/MetaVaRContactamadoui@genoscope.cns.fr

Published
2020

42. SVJedi: genotyping structural variations with long reads

Author

Lolita Lecompte, Pierre Peterlongo, Claire Lemaitre, Dominique Lavenier, Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique)

Subjects
Statistics and Probability, Genotype, Computer science, Computational biology, Third generation sequencing, Biochemistry, 03 medical and health sciences, 0302 clinical medicine, Humans, Allele, Molecular Biology, Genotyping, Allele frequency, 030304 developmental biology, 0303 health sciences, Genome, Human, Structural variant, High-Throughput Nucleotide Sequencing, Sequence Analysis, DNA, Short read, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, 030220 oncology & carcinogenesis, Genomic Structural Variation, Human genome, Nanopore sequencing, Pacific biosciences, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], 030217 neurology & neurosurgery, Software
Abstract

Motivation Studies on structural variants (SVs) 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. Results We present a novel method to genotype known SVs from long read sequencing data. The method is based on the generation of a set of representative allele sequences that represent the two alleles of each structural variant. Long reads are aligned to these allele 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 SVs with long reads. The tool has been applied to both simulated and real human datasets and achieves high genotyping accuracy. We show that SVJedi obtains better performances than other existing long read genotyping tools and we also demonstrate that SV genotyping is considerably improved with SVJedi compared to other approaches, namely SV discovery and short read SV genotyping approaches. Availability and implementation https://github.com/llecompte/SVJedi.git Supplementary information Supplementary data are available at Bioinformatics online.

Published
2019

43. DiscoSnp-RAD: de novo detection of small variants for population genomics

Author

Nadir Alvarez, Pierre Peterlongo, Chloé Riou, Tomasz Suchan, Jérémy Gauthier, Claire Lemaitre, Charlotte Mouden, Nils Arrigo, Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Biodiversité, Gènes & Communautés (BioGeCo), Institut National de la Recherche Agronomique (INRA)-Université de Bordeaux (UB), W. Szafer Institute of Botany, Polska Akademia Nauk (PAN), Natural History Museum [Geneva], Dpt of Ecology and Evolution [Lausanne], Université de Lausanne (UNIL), and Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA)

Subjects
0106 biological sciences, Genetics, 0303 health sciences, population genomics, Shotgun sequencing, Single-nucleotide polymorphism, Computational biology, Biology, 010603 evolutionary biology, 01 natural sciences, Genome, DNA sequencing, De Bruijn graph, Phylogenetic reconstruction, RAD-Seq, Population genomics, 03 medical and health sciences, Restriction site, symbols.namesake, symbols, next-generation sequencing, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], 030304 developmental biology, de novo variant calling
Abstract

We present an original method to de novo call variants for Restriction site associated DNA Sequencing (RAD-Seq). RAD-Seq is a technique characterized by the sequencing of specific loci along the genome, that is widely employed in the field of evolutionary biology since it allows to exploit variants (mainly SNPs) information from entire populations at a reduced cost. Common RAD dedicated tools, as STACKS or IPyRAD, are based on all-versus-all read comparisons, which require consequent time and computing resources. Based on the variant caller DiscoSnp, initially designed for shotgun sequencing, DiscoSnp-RAD avoids this pitfall as variants are detected by exploring the De Bruijn Graph built from all the read datasets. We tested the implementation on RAD data from 259 specimens of Chiastocheta flies, morphologically assigned to 7 species. All individuals were successfully assigned to their species using both STRUCTURE and Maximum Likelihood phylogenetic reconstruction. Moreover, identified variants succeeded to reveal a within species structuration and the existence of two populations linked to their geographic distributions. Furthermore, our results show that DiscoSnp-RAD is at least one order of magnitude faster than state-of-the-art tools. The overall results show that DiscoSnp-RAD is suitable to identify variants from RAD data, and stands out from other tools due to his completely different principle, making it significantly faster, in particular on large datasets.LicenseGNU Affero general public licenseAvailabilityhttps://github.com/GATB/DiscoSnpContactjeremy.gauthier@inria.fr

Published
2019

44. SimkaMin: fast and resource frugal de novo comparative metagenomics

Author

Mahendra Mariadassou, Sophie Schbath, Pierre Peterlongo, Claire Lemaitre, Stéphane Robin, Gaëtan Benoit, Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Mathématiques et Informatique Appliquées du Génome à l'Environnement [Jouy-En-Josas] (MaIAGE), Institut National de la Recherche Agronomique (INRA), Mathématiques et Informatique Appliquées (MIA-Paris), Institut National de la Recherche Agronomique (INRA)-AgroParisTech, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université Paris-Saclay, Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-AgroParisTech-Université Paris-Saclay, ANR-14-CE23-0001,HydroGen,Metagenomique comparative comme instrument de mesure pour la biodiversité. Application à l'étude de la vie dans les océans(2014), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Mathématiques et Informatique Appliquées (MIA Paris-Saclay), AgroParisTech-Université Paris-Saclay-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), and AgroParisTech-Institut National de la Recherche Agronomique (INRA)

Subjects
Statistics and Probability, Scheme (programming language), Computer science, Genomics, computer.software_genre, Biochemistry, 03 medical and health sciences, Software, Resource (project management), Molecular Biology, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology, computer.programming_language, 0303 health sciences, business.industry, 030302 biochemistry & molecular biology, Sequence Analysis, DNA, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, Metagenomics, Metagenome, Data mining, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], business, computer, Algorithms
Abstract

Motivation De novo comparative metagenomics is one of the most straightforward ways to analyze large sets of metagenomic data. Latest methods use the fraction of shared k-mers to estimate genomic similarity between read sets. However, those methods, while extremely efficient, are still limited by computational needs for practical usage outside of large computing facilities. Results We present SimkaMin, a quick comparative metagenomics tool with low disk and memory footprints, thanks to an efficient data subsampling scheme used to estimate Bray-Curtis and Jaccard dissimilarities. One billion metagenomic reads can be analyzed in Availability and implementation https://github.com/GATB/simka. Supplementary information Supplementary data are available at Bioinformatics online.

Published
2019

45. ELECTOR: evaluator for long reads correction methods

Author

Lolita Lecompte, Camille Marchet, Pierre Morisse, Arnaud Lefebvre, Antoine Limasset, Thierry Lecroq, Pierre Peterlongo, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU), Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), and Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH)

Subjects
0303 health sciences, Computer science, 0206 medical engineering, 02 engineering and technology, computer.software_genre, Set (abstract data type), 03 medical and health sciences, Range (mathematics), Resource (project management), Feature (computer vision), Key (cryptography), Methods Article, Noise (video), Data mining, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Error detection and correction, computer, 020602 bioinformatics, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology
Abstract

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

Published
2019

46. Investigating Population-scale Allele Specific Expression in Wild Populations of Oithona similis (Cyclopoida, Claus 1866)

Author

Patrick Wincker, E. Petit, Christophe Ambroise, Karine Labadie, Jean-Louis Jamet, Romuald Laso-Jadart, Mohammed-Amin Madoui, Pierre Peterlongo, and Kevin Sugier

Subjects
0106 biological sciences, Oithona similis, Genetics, 0303 health sciences, education.field_of_study, biology, Population, Cyclopoida, biology.organism_classification, 010603 evolutionary biology, 01 natural sciences, Transcriptome, 03 medical and health sciences, Metagenomics, education, Copepod, Allele specific, Selection (genetic algorithm), 030304 developmental biology
Abstract

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.3×10−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.89×10−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.

Published
2019

47. Finding All Maximal Perfect Haplotype Blocks in Linear Time

Author

Jarno Alanko and Hideo Bannai and Bastien Cazaux and Pierre Peterlongo and Jens Stoye, Alanko, Jarno, Bannai, Hideo, Cazaux, Bastien, Peterlongo, Pierre, Stoye, Jens, Jarno Alanko and Hideo Bannai and Bastien Cazaux and Pierre Peterlongo and Jens Stoye, Alanko, Jarno, Bannai, Hideo, Cazaux, Bastien, Peterlongo, Pierre, and Stoye, Jens

Abstract

Recent large-scale community sequencing efforts allow at an unprecedented level of detail the identification of genomic regions that show signatures of natural selection. Traditional methods for identifying such regions from individuals' haplotype data, however, require excessive computing times and therefore are not applicable to current datasets. In 2019, Cunha et al. (Proceedings of BSB 2019) suggested the maximal perfect haplotype block as a very simple combinatorial pattern, forming the basis of a new method to perform rapid genome-wide selection scans. The algorithm they presented for identifying these blocks, however, had a worst-case running time quadratic in the genome length. It was posed as an open problem whether an optimal, linear-time algorithm exists. In this paper we give two algorithms that achieve this time bound, one conceptually very simple one using suffix trees and a second one using the positional Burrows-Wheeler Transform, that is very efficient also in practice.

Published
2019
Full Text
View/download PDF

48. A de novo approach to disentangle partner identity and function in holobiont systems

Author

Stéphane Le Crom, Eric Pelletier, Patrick Wincker, Ian Probert, Fabrice Not, Camille Marchet, Erwan Corre, Pierre Peterlongo, Johan Decelle, Adriana Alberti, Arnaud Meng, Corinne Da Silva, Lucie Bittner, Sorbonne Université (SU), Université Pierre et Marie Curie - Paris 6 - UFR de Médecine Pierre et Marie Curie (UPMC), Université Pierre et Marie Curie - Paris 6 (UPMC), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Station biologique de Roscoff (SBR), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Genoscope - Centre national de séquençage [Evry] (GENOSCOPE), Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Génomique métabolique (UMR 8030), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université d'Évry-Val-d'Essonne (UEVE), Helmholtz Zentrum für Umweltforschung = Helmholtz Centre for Environmental Research (UFZ), Analyse des Données à Haut Débit en Génomique (ADHDG), Evolution Paris Seine, Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Fédération de recherche de Roscoff (FR2424), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université d'Évry-Val-d'Essonne (UEVE)-Centre National de la Recherche Scientifique (CNRS), Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)

Subjects
0301 basic medicine, Microbiology (medical), Sequence assembly, Genomics, Computational biology, Biology, Holobiont, Microbiology, lcsh:Microbial ecology, k-mer based similarity, Transcriptome, Cnidaria, 03 medical and health sciences, Functional diversity, De novo assembly, Microalgae, Animals, Symbiosis, 030304 developmental biology, Genetics, 0303 health sciences, Marine, Coral Reefs, 030306 microbiology, Research, Meta-transcriptomic, Computational Biology, Plankton, Short read, Porifera, Rhizaria, 030104 developmental biology, Identity (object-oriented programming), lcsh:QR100-130, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Function (biology), [SDV.EE.IEO]Life Sciences [q-bio]/Ecology, environment/Symbiosis
Abstract

BackgroundStudy of meta-transcriptomic datasets involving non-model organisms represents bioinformatic challenges. The production of chimeric sequences and our inability to distinguish the taxonomic origins of the sequences produced are inherent and recurrent difficulties in de novo assembly analyses. The study of holobiont transcriptomes shares similarities with meta-transcriptomic, and hence, is also affected by challenges invoked above. Here we propose an innovative approach to tackle such difficulties which was applied to the study of marine holobiont models as a proof of concept.ResultsWe considered three holobionts models, of which two transcriptomes were previously assembled and published, and a yet unpublished transcriptome, to analyze their raw reads and assign them to the host and/or to the symbiont(s) using Short Read Connector, a k-mer based similarity method. We were able to define four distinct categories of reads for each holobiont transcriptome: host reads, symbiont reads, shared reads and unassigned reads. The result of the independent assemblies for each category within a transcriptome led to a significant diminution of de novo assembled chimeras compared to classical assembly methods. Combining independent functional and taxonomic annotations of each partner’s transcriptome is particularly convenient to explore the functional diversity of an holobiont. Finally, our strategy allowed to propose new functional annotations for two well-studied holobionts and a first transcriptome from a planktonic Radiolaria-Dinophyta system forming widespread symbiotic association for which our knowledge is limited. ConclusionsIn contrast to classical assembly approaches, our bioinformatic strategy not only allows biologists to studying separately host and symbiont data from a holobiont mixture, but also generates improved transcriptome assemblies. The use of Short Read Connector has proven to be an effective way to tackle meta-transcriptomic challenges to study holobiont systems composed of either well-studied or poorly characterized symbiotic lineages such as the newly sequenced marine plankton Radiolaria-Dinophyta symbiosis and ultimately expand our knowledge about these marine symbiotic associations.

Published
2018

49. De novo clustering of long reads by gene from transcriptomics data

Author

Camille, Marchet, Lolita, Lecompte, Corinne Da, Silva, Corinne, Cruaud, Jean-Marc, Aury, Jacques, Nicolas, and Pierre, Peterlongo

Subjects
Mice, Genome, Gene Expression Profiling, Animals, High-Throughput Nucleotide Sequencing, RNA, Methods Online, Genomics, Sequence Analysis, DNA, Transcriptome
Abstract

Long-read sequencing currently provides sequences of several thousand base pairs. It is therefore possible to obtain complete transcripts, offering an unprecedented vision of the cellular transcriptome. However the literature lacks tools for de novo clustering of such data, in particular for Oxford Nanopore Technologies reads, because of the inherent high error rate compared to short reads. Our goal is to process reads from whole transcriptome sequencing data accurately and without a reference genome in order to reliably group reads coming from the same gene. This de novo approach is therefore particularly suitable for non-model species, but can also serve as a useful pre-processing step to improve read mapping. Our contribution both proposes a new algorithm adapted to clustering of reads by gene and a practical and free access tool that allows to scale the complete processing of eukaryotic transcriptomes. We sequenced a mouse RNA sample using the MinION device. This dataset is used to compare our solution to other algorithms used in the context of biological clustering. We demonstrate that it is the best approach for transcriptomics long reads. When a reference is available to enable mapping, we show that it stands as an alternative method that predicts complementary clusters.

Published
2018

50. A resource-frugal probabilistic dictionary and applications in bioinformatics

Author

Lucie Bittner, Antoine Limasset, Lolita Lecompte, Camille Marchet, Pierre Peterlongo, Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES), Evolution Paris-Seine (EPS), Institut de Recherche pour le Développement (IRD)-Sorbonne Université (SU)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Université des Antilles (UA)-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Biologie Paris Seine (IBPS), Sorbonne Université (SU)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), ANR-12-BS02-0008,Colib'read,Méthodes d'extraction d'information biologique dans les données HTS non assemblées(2012), ANR-14-CE23-0001,HydroGen,Metagenomique comparative comme instrument de mesure pour la biodiversité. Application à l'étude de la vie dans les océans(2014), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Theoretical computer science, Bloomier filter, Computer science, Hash function, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, sequences comparison, 0102 computer and information sciences, 02 engineering and technology, Bioinformatics, computer.software_genre, Quantitative Biology - Quantitative Methods, 01 natural sciences, Set (abstract data type), data structures, Computer Science - Data Structures and Algorithms, genomics, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), Quantitative Methods (q-bio.QM), minimal perfect hash functions, Applied Mathematics, Dynamic perfect hashing, Probabilistic logic, 021107 urban & regional planning, bioinformatics, Data structure, Hash table, Hash tree, 010201 computation theory & mathematics, FOS: Biological sciences, Data mining, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Perfect hash function, computer, indexing
Abstract

Indexing massive data sets is extremely expensive for large scale problems. In many fields, huge amounts of data are currently generated, however extracting meaningful information from voluminous data sets, such as computing similarity between elements, is far from being trivial. It remains nonetheless a fundamental need. This work proposes a probabilistic data structure based on a minimal perfect hash function for indexing large sets of keys. Our structure out-compete the hash table for construction, query times and for memory usage, in the case of the indexation of a static set. To illustrate the impact of algorithms performances, we provide two applications based on similarity computation between collections of sequences, and for which this calculation is an expensive but required operation. In particular, we show a practical case in which other bioinformatics tools fail to scale up the tested data set or provide lower recall quality results., Comment: Submitted to Journal of Discrete Algorithms. arXiv admin note: substantial text overlap with arXiv:1605.08319

Published
2018

Catalog

Books, media, physical & digital resources
See catalog results