Biology subjects

Boucher, C.

Publications and source records attributed to Boucher, C..

At least 37 records · Page 2Linked to original sources

bioRxiv2022

SPUMONI 2: Improved pangenome classification using a compressed index of minimizer digests

Genomics analyses often use a large sequence collection as a reference, like a pangenome or taxonomic database. We previously described SPUMONI, which performs binary classification of nanopore reads using pangenomic matching statistics. Here we describe SPUMONI 2, an improved version that is faster, more memory efficient, works effectively for both short and long reads, and can solve multi-class classification problems with the aid of a novel sampled document array structure. By incorporating minimizers, SPUMONI 2 reduces index size by a factor of 2 compared to SPUMONI, yielding an index more than 65 times smaller than minimap2s for a mock community pangenome. SPUMONI 2 also achieves a speed improvement of 3-fold compared to SPUMONI and 15-fold compared to minimap2. We show SPUMONI 2 achieves an advantageous mix of accuracy and efficiency for short and long reads, including in an adaptive sampling scenario. We further demonstrate that SPUMONI 2 can detect contaminated contigs in genome assemblies, and can perform multi-class metagenomic read classification.

bioinformatics↗

bioRxiv2022

The K-mer Antibiotic Resistance Gene Variant Analyzer (KARGVA)

Characterization of antibiotic resistance genes (ARGs) from high-throughput sequencing data of metagenomics and cultured bacterial samples is a challenging task, with the need to account for both computational (e.g., string algorithms) and biological (e.g., gene transfers, rearrangements) aspects. Curated ARG databases exist together with assorted ARG classification approaches (e.g., database alignment, machine learning). Besides ARGs that naturally occur in bacterial strains or are acquired through mobile elements, there are chromosomal genes that can render a bacterium resistant to antibiotics through point mutations, i.e., ARG variants (ARGVs). While ARG repositories also collect ARGVs, there are only a few tools that are able to identify ARGVs from metagenomics and high throughput sequencing data, with a number of limitations (e.g., pre-assembly, a posteriori verification of mutations, or specification of species). In this work we present the k-mer, i.e., strings of fixed length k, ARGV analyzer -KARGVA- an open-source, multi-platform tool that provides: (i) an ad hoc, large ARGV database derived from multiple sources; (ii) input capability for various types of high-throughput sequencing data; (iii) a three-way, hash-based, k-mer search setup to process data efficiently, linking k-mers to ARGVs, k-mers to point mutations, and ARGVs to k-mers, respectively; (iv) a statistical filter on sequence classification to reduce type I and II errors. On semi-synthetic data, KARGVA provides very high accuracy even in presence of high sequencing errors or mutations (99.2% and 86.6% accuracy within 1% and 5% base change rates, respectively), and genome rearrangements (98.2% accuracy), with robust performance on ad hoc false positive sets. On data from the worldwide MetaSUB consortium, comprising 3,700+ metagenomics experiments, KARGVA identifies more ARGVs than Resistance Gene Identifier (4.8x) and PointFinder (6.8x), yet all predictions are below the expected false positive estimates. The prevalence of ARGVs is correlated to ARGs but ecological characteristics do not explain well ARGV variance. KARGVA is publicly available at https://github.com/DataIntellSystLab/KARGVA under MIT license.

bioinformatics↗

bioRxiv2022

Advancing antimicrobial resistance monitoring in surface waters with metagenomic and quasimetagenomic methods

Surface waters present a unique challenge for the monitoring of critically important antimicrobial resistance. Metagenomic approaches provide unbiased descriptions of taxonomy and antimicrobial resistance genes in many environments, but for surface water, culture independent data is insufficient to describe critically important resistance. To address this challenge and expand resistome reporting capacity of antimicrobial resistance in surface waters, we apply metagenomic and quasimetagenomic (enriched microbiome) data to examine and contrast water from two sites, a creek near a hospital, and a reservoir used for recreation and municipal water. Approximately 30% of the National Antimicrobial Resistance Monitoring Systems critically important resistance gene targets were identified in enriched data contrasted to only 1% in culture independent data. Four different analytical approaches consistently reported substantially more antimicrobial resistance genes in quasimetagenomic data compared to culture independent data across most classes of antimicrobial resistance. Statistically significant differential fold changes (p<0.05) of resistance determinants were used to infer microbiological differences in the waters. Important pathogens associated with critical antimicrobial resistance were described for each water source. While the single time-point for only two sites represents a small pilot project, the successful reporting of critically important resistance determinants is proof of concept that the quasimetagenomic approach is robust and can be expanded to multiple sites and timepoints for national and global monitoring and surveillance of antimicrobial resistance in surface waters.

microbiology↗

bioRxiv2021

Syotti: Scalable Bait Design for DNA Enrichment

Bait-enriched sequencing is a relatively new sequencing protocol that is becoming increasingly ubiquitous as it has been shown to successfully amplify regions of interest in metagenomic samples. In this method, a set of synthetic probes ("baits") are designed, manufactured, and applied to fragmented metagenomic DNA. The probes bind to the fragmented DNA and any unbound DNA is rinsed away, leaving the bound fragments to be amplified for sequencing. This effectively enriches the DNA for which the probes were designed. Most recently, Metsky et al. (Nature Biotech 2019) demonstrated that bait-enrichment is capable of detecting a large number of human viral pathogens within metagenomic samples. In this work, we formalize the problem of designing baits by defining the Minimum Bait Cover problem, which aims to find the smallest possible set of bait sequences that cover every position of a set of reference sequences under an approximate matching model. We show that the problem is NP-hard, and that it remains NP-hard under very restrictive assumptions. This indicates that no polynomial-time exact algorithm exists for the problem, and that the problem is intractable even for small and deceptively simple inputs. In light of this, we design an efficient heuristic that takes advantage of succinct data structures. We refer to our method as syotti. The running time of syotti shows linear scaling in practice, running at least an order of magnitude faster than state-of-the-art methods, including the recent method of Metsky et al. At the same time, our method produces bait sets that are smaller than the ones produced by the competing methods, while also leaving fewer positions uncovered. Lastly, we show that syotti requires only 25 minutes to design baits for a dataset comprised of 3 billion nucleotides from 1000 related bacterial substrains, whereas the method of Metsky et al. shows clearly super-linear running time and fails to process even a subset of 8% of the data in 24 hours. Our implementation is publicly available at https://github.com/jnalanko/syotti.

bioinformatics↗

bioRxiv2021

Towards routine employment of computational tools for antimicrobial resistance determination via high-throughput sequencing

Antimicrobial resistance (AMR) is a growing threat to public health and farming at large. In clinical and veterinary practice, timely characterization of the antibiotic susceptibility profile of bacterial infections is a crucial step in optimizing treatment. High-throughput sequencing is a promising option for clinical point-of-care and ecological surveillance, opening the opportunity to develop genotyping-based AMR determination as a possibly faster alternative to phenotypic testing. In the present work, we compare the performance of state-of-the-art methods for detection of AMR using high-throughput sequencing data from clinical settings. We consider five computational approaches based on alignment (AMRPlusPlus), deep learning (DeepARG), k-mer genomic signatures (KARGA, ResFinder) or hidden Markov models (Meta-MARC). We use an extensive collection of 585 isolates with available AMR resistance profiles determined by phenotypic tests across nine antibiotic classes. We show how the prediction landscape of AMR classifiers is highly heterogeneous, with balanced accuracy varying from 0.40 to 0.92. Although some algorithms--ResFinder, KARGA, and AMRPlusPlus- exhibit overall better balanced accuracy than others, the high per-AMR-class variance and related findings suggest that: (1) all algorithms might be subject to sampling bias present both in data repositories used for training and experimental/clinical settings; and (2) a portion of clinical samples might contain uncharacterized AMR genes that the algorithms--mostly trained on known AMR genes--fail to generalize upon. These results lead us to formulate practical advice for software configuration and application, and give suggestions for future study designs to further develop AMR prediction tools from proof-of-concept to bedside.

genomics↗

bioRxiv2021

Finding Overlapping Rmaps via Gaussian Mixture Model Clustering

Optical mapping is a method for creating high resolution restriction maps of an entire genome. Optical mapping has been largely automated, and first produces single molecule restriction maps, called Rmaps, which are assembled to generate genome wide optical maps. Since the location and orientation of each Rmap is unknown, the first problem in the analysis of this data is finding related Rmaps, i.e., pairs of Rmaps that share the same orientation and have significant overlap in their genomic location. Although heuristics for identifying related Rmaps exist, they all require quantization of the data which leads to a loss in the precision. In this paper, we propose a Gaussian mixture modelling clustering based method, which we refer to as OMO_SCPLOWCLUSTC_SCPLOW, that finds overlapping Rmaps without quantization. Using both simulated and real datasets, we show that OMO_SCPLOWCLUSTC_SCPLOW substantially improves the precision (from 48.3% to 73.3%) over the state-of-the art methods while also reducing CPU time and memory consumption. Further, we integrated OMO_SCPLOWCLUSTC_SCPLOW into the error correction methods (Elmeri and O_SCPLOWCC_SCPLOWOMO_SCPLOWETC_SCPLOW) to demonstrate the increase in the performance of these methods. When OMO_SCPLOWCLUSTC_SCPLOW was combined with O_SCPLOWCC_SCPLOWOMO_SCPLOWETC_SCPLOW to error correct Rmap data generated from human DNA, it was able to error correct close to 3x more Rmaps, and reduced the CPU time by more than 35x. Our software is written in C++ and is publicly available under GNU General Public License at https://github.com/kingufl/OMclust

bioinformatics↗

bioRxiv2021

MONI: A Pangenomics Index for Finding MEMs

Recently, Gagie et al. proposed a version of the FM-index, called the r-index, that can store thousands of human genomes on a commodity computer. Then Kuhnle et al. showed how to build the r-index efficiently via a technique called prefix-free parsing (PFP) and demonstrated its effectiveness for exact pattern matching. Exact pattern matching can be leveraged to support approximate pattern matching but the r-index itself cannot support efficiently popular and important queries such as finding maximal exact matches (MEMs). To address this shortcoming, Bannai et al. introduced the concept of thresholds, and showed that storing them together with the r-index enables efficient MEM finding -- but they did not say how to find those thresholds. We present a novel algorithm that applies PFP to build the r-index and find the thresholds simultaneously and in linear time and space with respect to the size of the prefix-free parse. Our implementation called MONI can rapidly find MEMs between reads and large sequence collections of highly repetitive sequences. Compared to other read aligners - PuffAligner, Bowtie2, BWA-MEM, and CHIC - MONI used 2-11 times less memory and was 2-32 times faster for index construction. Moreover, MONI was less than one thousandth the size of competing indexes for large collections of human chromosomes. Thus, MONI represents a major advance in our ability to perform MEM finding against very large collections of related references. AvailabilityMONI is publicly available at https://github.com/maxrossi91/moni.

bioinformatics↗

bioRxiv2021

Pan-genomic Matching Statistics for Targeted Nanopore Sequencing

Nanopore sequencing is an increasingly powerful tool for genomics. Recently, computational advances have allowed nanopores to sequence in a targeted fashion; as the sequencer emits data, software can analyze the data in real time and signal the sequencer to eject "non-target" DNA molecules. We present a novel method called SPUMONI, which enables rapid and accurate targeted sequencing with the help of efficient pangenome indexes. SPUMONI uses a compressed index to rapidly generate exact or approximate matching statistics (half-maximal exact matches) in a streaming fashion. When used to target a specific strain in a mock community, SPUMONI has similar accuracy as minimap2 when both are run against an index containing many strains per species. However SPUMONI is 12 times faster than minimap2. SPUMONIs index and peak memory footprint are also 15 to 4 times smaller than minimap2, respectively. These improvements become even more pronounced with even larger reference databases; SPUMONIs index size scales sublinearly with the number of reference genomes included. This could enable accurate targeted sequencing even in the case where the targeted strains have not necessarily been sequenced or assembled previously. SPUMONI is open source software available from https://github.com/oma219/spumoni.

bioinformatics↗

bioRxiv2021

Buffering Updates Enables Efficient Dynamic de Bruijn Graphs

MotivationThe de Bruijn graph has become a ubiquitous graph model for biological data ever since its initial introduction in the late 1990s. It has been used for a variety of purposes including genome assembly (Zerbino and Birney, 2008; Bankevich et al., 2012; Peng et al., 2012), variant detection (Alipanahi et al., 2020b; Iqbal et al., 2012), and storage of assembled genomes (Chikhi et al., 2016). For this reason, there have been over a dozen methods for building and representing the de Bruijn graph and its variants in a space and time efficient manner. ResultsWith the exception of a few data structures (Muggli et al., 2019; Holley and Melsted, 2020; Crawford et al., 2018), compressed and compact de Bruijn graphs do not allow for the graph to be efficiently updated, meaning that data can be be added or deleted. The most recent compressed dynamic de Bruijn graph (Alipanahi et al., 2020a), relies on dynamic bit vectors which are slow in theory and practice. To address this shortcoming, we present a compressed dynamic de Bruijn graph that removes the necessity of dynamic bit vectors by buffering data that should be added or removed from the graph. We implement our method, which we refer to as BufBOSS, and compare its performance to Bifrost, DynamicBOSS, and FDBG. Our experiments demonstrate that BufBOSS achieves attractive trade-offs compared to other tools in terms of time, memory and disk, and has the best deletion performance by an order of magnitude. Contactalanko.jarno@gmail.com

bioinformatics↗

bioRxiv2020

Succinct Dynamic de Bruijn Graphs

MotivationThe de Bruijn graph is one of the fundamental data structures for analysis of high throughput sequencing data. In order to be applicable to population-scale studies, it is essential to build and store the graph in a space- and time-efficient manner. In addition, due to the ever-changing nature of population studies, it has become essential to update the graph after construction e.g. add and remove nodes and edges. Although there has been substantial effort on making the construction and storage of the graph efficient, there is a limited amount of work in building the graph in an efficient and mutable manner. Hence, most space efficient data structures require complete reconstruction of the graph in order to add or remove edges or nodes. ResultsIn this paper we present DynamicBOSS, a succinct representation of the de Bruijn graph that allows for an unlimited number of additions and deletions of nodes and edges. We compare our method with other competing methods and demonstrate that DynamicBOSS is the only method that supports both addition and deletion and is applicable to very large samples (e.g. greater than 15 billion k-mers). Competing dynamic methods e.g., FDBG (Crawford et al., 2018) cannot be constructed on large scale datasets, or cannot support both addition and deletion e.g., BiFrost (Holley and Melsted, 2019). AvailabilityDynamicBOSS is publicly available at https://github.com/baharpan/dynboss. Contactbaharpan@ufl.edu

bioinformatics↗

bioRxiv2019

Data structures based on k-mers for querying large collections of sequencing datasets

High-throughput sequencing datasets are usually deposited in public repositories, e.g. the European Nucleotide Archive, to ensure reproducibility. As the amount of data has reached petabyte scale, repositories do not allow to perform online sequence searches; yet such a feature would be highly useful to investigators. Towards this goal, in the last few years several computational approaches have been introduced to index and query large collections of datasets. Here we propose an accessible survey of these approaches, which are generally based on representing datasets as sets of k-mers. We review their properties, introduce a classification, and present their general intuition. We summarize their performance and highlight their current strengths and limitations.

bioinformatics↗

bioRxiv2019

Human liver organoids; a patient-derived primary model for HBV Infection and Related Hepatocellular Carcinoma

The molecular events that drive Hepatitis B virus (HBV)-mediated transformation and tumorigenesis have remained largely unclear, due to the absence of a relevant primary model system. Here we propose the use of human liver organoids as a platform for modeling HBV infection and related tumorigenesis. We first describe a primary ex vivo HBV-infection model derived from healthy donor liver organoids after challenge with recombinant virus or HBV-infected patient serum. HBV infected organoids produced cccDNA, expressed intracellular HBV RNA and proteins, and produced infectious HBV. This ex vivo HBV infected primary differentiated hepatocyte organoid platform was amenable to drug screening for both anti-HBV activity as well as for drug-induced toxicity. We also studied HBV replication in transgenically modified organoids; liver organoids exogenously overexpressing the HBV receptor NTCP by lentiviral transduction were not more susceptible to HBV, suggesting the necessity for additional host factors for efficient infection. We also generated transgenic organoids harboring integrated HBV, representing a long-term culture system also suitable for viral production and the study of HBV transcription. Finally, we generated HBV-infected patient-derived liver organoids from non-tumor cirrhotic tissue of explants from liver transplant patients. Interestingly, transcriptomic analysis of patient-derived liver organoids indicated the presence of an aberrant early cancer gene signature, which clustered with the HCC cohort on the TCGA LIHC dataset and away from healthy liver tissue, and may provide invaluable novel biomarkers for disease surveillance and development of HCC in HBV infected patients.

cancer biology↗

bioRxiv2018

Prefix-Free Parsing for Building Big BWTs

High-throughput sequencing technologies have led to explosive growth of genomic databases; one of which will soon reach hundreds of terabytes. For many applications we want to build and store indexes of these databases but constructing such indexes is a challenge. Fortunately, many of these genomic databases are highly-repetitive--a characteristic that can be exploited to ease the computation of the Burrows-Wheeler Transform (BWT), which underlies many popular indexes. In this paper, we introduce a preprocessing algorithm, referred to as prefix-free parsing, that takes a text T as input, and in one-pass generates a dictionary D and a parse P of T with the property that the BWT of T can be constructed from D and P using workspace proportional to their total size and O(|T|)-time. Our experiments show that D and P are significantly smaller than T in practice, and thus, can fit in a reasonable internal memory even when T is very large. In particular, we show that with prefix-free parsing we can build an 131-megabyte run-length compressed FM-index (restricted to support only counting and not locating) for 1000 copies of human chromosome 19 in 2 hours using 21 gigabytes of memory suggesting that we can build a 6.73 gigabyte index for 1000 complete human-genome haplotypes in approximately 102 hours using about 1 terabyte of memory

bioinformatics↗

bioRxiv2018

Efficient Construction of a Complete Index for Pan-Genomics Read Alignment

While short read aligners, which predominantly use the FM-index, are able to easily index one or a few human genomes, they do not scale well to indexing databases containing thousands of genomes. To understand why, it helps to examine the main components of the FM-index in more detail, which is a rank data structure over the Burrows-Wheeler Transform (BWT) of the string that will allow us to find the interval in the strings suffix array (SA) containing pointers to starting positions of occurrences of a given pattern; second, a sample of the SA that -- when used with the rank data structure -- allows us access the SA. The rank data structure can be kept small even for large genomic databases, by run-length compressing the BWT, but until recently there was no means known to keep the SA sample small without greatly slowing down access to the SA. Now that Gagie et al. (SODA 2018) have defined an SA sample that takes about the same space as the run-length compressed BWT -- we have the design for efficient FM-indexes of genomic databases but are faced with the problem of building them. In 2018 we showed how to build the BWT of large genomic databases efficiently (WABI 2018) but the problem of building Gagie et al.s SA sample efficiently was left open. We compare our approach to state-of-the-art methods for constructing the SA sample, and demonstrate that it is the fastest and most space-efficient method on highly repetitive genomic databases. Lastly, we apply our method for indexing partial and whole human genomes, and show that it improves over Bowtie with respect to both memory and time.\n\nAvailabilityWe note that the implementation of our methods can be found here: https://github.com/alshai/r-index.

bioinformatics↗

bioRxiv2018

Identification of co-evolving temporal networks

MotivationBiological networks describes the mechanisms which govern cellular functions. Temporal networks show how these networks evolve over time. Studying the temporal progression of network topologies is of utmost importance since it uncovers how a network evolves and how it resists to external stimuli and internal variations. Two temporal networks have co-evolving subnetworks if the topologies of these subnetworks remain similar to each other as the network topology evolves over a period of time. In this paper, we consider the problem of identifying co-evolving pair of temporal networks, which aim to capture the evolution of molecules and their interactions over time. Although this problem shares some characteristics of the well-known network alignment problems, it differs from existing network alignment formulations as it seeks a mapping of the two network topologies that is invariant to temporal evolution of the given networks. This is a computationally challenging problem as it requires capturing not only similar topologies between two networks but also their similar evolution patterns.\n\nResultsWe present an efficient algorithm, Tempo, for solving identifying coevolving subnetworks with two given temporal networks. We formally prove the correctness of our method. We experimentally demonstrate that Tempo scales efficiently with the size of network as well as the number of time points, and generates statistically significant alignments--even when evolution rates of given networks are high. Our results on a human aging dataset demonstrate that Tempo identifies novel genes contributing to the progression of Alzheimers, Huntingtons and Type II diabetes, while existing methods fail to do so.\n\nAvailabilitySoftware is available online (https://www.cise.ufi.edu/[~]relhesha/temporal.zip).\n\nContactrelhesha@ufi.edu\n\nSupplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2018

Error Correcting Optical Mapping Data

Optical mapping is a unique system that is capable of producing high-resolution, high-throughput genomic map data that gives information about the structure of a genome [21]. Recently it has been used for scaffolding contigs and assembly validation for large-scale sequencing projects, including the maize [32], goat [6], and amborella [4] genomes. However, a major impediment in the use of this data is the variety and quantity of errors in the raw optical mapping data, which are called Rmaps. The challenges associated with using Rmap data are analogous to dealing with insertions and deletions in the alignment of long reads. Moreover, they are arguably harder to tackle since the data is numerical and susceptible to inaccuracy. We develop cOMet to error correct Rmap data, which to the best of our knowledge is the only optical mapping error correction method. Our experimental results demonstrate that cOMet has high prevision and corrects 82.49% of insertion errors and 77.38% of deletion errors in Rmap data generated from the E. coli K-12 reference genome. Out of the deletion errors corrected, 98.26% are true errors. Similarly, out of the insertion errors corrected, 82.19% are true errors. It also successfully scales to large genomes, improving the quality of 78% and 99% of the Rmaps in the plum and goat genomes, respectively. Lastly, we show the utility of error correction by demonstrating how it improves the assembly of Rmap data. Error corrected Rmap data results in an assembly that is more contiguous, and covers a larger fraction of the genome.

bioinformatics↗

bioRxiv2017

Succinct De Bruijn Graph Construction for Massive Populations Through Space-Efficient Merging

Recently, there has been significant amount of effort in developing space-efficient and succinct data structures for storing and building the traditional de Bruijn graph and its variants, including the colored de Bruijn graph. However, a problem not yet considered is developing a means to merge succinct representations of the de Bruijn graph--a challenge is necessary for constructing the de Bruijn graph on very-large datasets. We create VO_SCPLOWARIC_SCPLOWMO_SCPLOWERGEC_SCPLOW, for building the colored de Bruijn graph on a very-large dataset through partitioning the data into smaller subsets, building the colored de Bruijn graph using a FM-index based representation, and merging these representations in an iterative format. This last step is an algorithmic challenge for which we present an algorithm in this paper. Lastly, we demonstrate the utility of VO_SCPLOWARIC_SCPLOWMO_SCPLOWERGEC_SCPLOW by demonstrating: a four-fold reduction in working space when constructing an 8,000 color dataset, and the construction of population graph two orders of magnitude larger than previous reported methods.

bioinformatics↗

bioRxiv2017

Resistome SNP Calling via Read Colored de Bruijn Graphs

MotivationThe resistome, which refers to all of the antimicrobial resistance (AMR) genes in pathogenic and non-pathogenic bacteria, is frequently studied using shotgun metagenomic data [14, 47]. Unfortunately, few existing methods are able to identify single nucleotide polymorphisms (SNPs) within metagenomic data, and to the best of our knowledge, no methods exist to detect SNPs within AMR genes within the resistome. The ability to identify SNPs in AMR genes across the resistome would represent a significant advance in understanding the dissemination and evolution of AMR, as SNP identification would enable \"fingerprinting\" of the resistome, which could then be used to track AMR dynamics across various settings and/or time periods.\n\nResultsWe present LueVari, a reference-free SNP caller based on the read colored de Bruijn graph, an extension of the traditional de Bruijn graph that allows repeated regions longer than the k-mer length and shorter than the read length to be identified unambiguously. We demonstrate LueVari was the only method that had reliable sensitivity (between 73% and 98%) as the performance of competing methods varied widely. Furthermore, we show LueVari constructs sequences containing the variation which span 93% of the gene in datasets with lower coverage (15X), and 100% of the gene in datasets with higher coverage (30X).\n\nAvailabilityCode and datasets are publicly available at https://github.com/baharpan/cosmo/tree/LueVari.

bioinformatics↗