Biology subjects

Dilthey, A.

Publications and source records attributed to Dilthey, A..

12 recordsLinked to original sources

bioRxiv2021

Emu: Species-Level Microbial Community Profiling for Full-Length Nanopore 16S Reads

16S rRNA based analysis is the established standard for elucidating microbial community composition. While short read 16S analyses are largely confined to genus-level resolution at best since only a portion of the gene is sequenced, full-length 16S sequences have the potential to provide species-level accuracy. However, existing taxonomic identification algorithms are not optimized for the increased read length and error rate of long-read data. Here we present Emu, a novel approach that employs an expectation-maximization (EM) algorithm to generate taxonomic abundance profiles from full-length 16S rRNA reads. Results produced from one simulated data set and two mock communities prove Emu capable of accurate microbial community profiling while obtaining fewer false positives and false negatives than alternative methods. Additionally, we illustrate a real-world application of our new software by comparing clinical sample composition estimates generated by an established whole-genome shotgun sequencing workflow to those returned by full-length 16S sequences processed with Emu.

bioinformatics↗

bioRxiv2021

Haploflow: Strain-resolved de novo assembly of viral genomes

In viral infections often multiple related viral strains are present, due to coinfection or within-host evolution. We describe Haploflow, a de Bruijn graph-based assembler for de novo genome assembly of viral strains from mixed sequence samples using a novel flow algorithm. We assessed Haploflow across multiple benchmark data sets of increasing complexity, showing that Haploflow is faster and more accurate than viral haplotype assemblers and generic metagenome assemblers not aiming to reconstruct strains. Haplotype reconstructed high-quality strain-resolved assemblies from clinical HCMV samples and SARS-CoV-2 genomes from wastewater metagenomes identical to genomes from clinical isolates.

bioinformatics↗

bioRxiv2020

SARS-CoV-2 targets cortical neurons of 3D human brain organoids and shows neurodegeneration-like effects

COVID-19 pandemic caused by SARS-CoV-2 infection is a public health emergency. COVID-19 typically exhibits respiratory illness. Unexpectedly, emerging clinical reports indicate that neurological symptoms continue to rise, suggesting detrimental effects of SARS-CoV-2 on the central nervous system (CNS). Here, we show that a Dusseldorf isolate of SARS-CoV-2 enters 3D human brain organoids within two days of exposure. Using COVID-19 convalescent serum, we identified that SARS-CoV-2 preferably targets soma of cortical neurons but not neural stem cells, the target cell type of ZIKA virus. Imaging cortical neurons of organoids reveal that SARS-CoV-2 exposure is associated with missorted Tau from axons to soma, hyperphosphorylation, and apparent neuronal death. Surprisingly, SARS-CoV-2 co-localizes specifically with Tau phosphorylated at Threonine-231 in the soma, indicative of early neurodegeneration-like effects. Our studies, therefore, provide initial insights into the impact of SARS-CoV-2 as a neurotropic virus and emphasize that brain organoids could model CNS pathologies of COVID-19. One sentence summaryCOVID-19 modeling in human brain organoids

cell biology↗

bioRxiv2019

Validating paired-end read alignments in sequence graphs

Graph based non-linear reference structures such as variation graphs and colored de Bruijn graphs enable incorporation of full genomic diversity within a population. However, transitioning from a simple string-based reference to graphs requires addressing many computational challenges, one of which concerns accurately mapping sequencing read sets to graphs. Paired-end Illumina sequencing is a commonly used sequencing platform in genomics, where the paired-end distance constraints allow disambiguation of repeats. Many recent works have explored provably good index-based and alignment-based strategies for mapping individual reads to graphs. However, validating distance constraints efficiently over graphs is not trivial, and existing sequence to graph mappers rely on heuristics. We introduce a mathematical formulation of the problem, and provide a new algorithm to solve it exactly. We take advantage of the high sparsity of reference graphs, and use sparse matrix-matrix multiplications (SpGEMM) to build an index which can be queried efficiently by a mapping algorithm for validating the distance constraints. Effectiveness of the algorithm is demonstrated using real reference graphs, including a human MHC variation graph, and a pan-genome de-Bruijn graph built using genomes of 20 B. anthracis strains. While the one-time indexing time can vary from a few minutes to a few hours using our algorithm, answering a million distance queries takes less than a second.\n\n2012 ACM Subject ClassificationMathematics of computing [->] Paths and connectivity problems; Applied computing [->] Computational genomics

bioinformatics↗

bioRxiv2019

Increasing the efficiency of long-read sequencing for hybrid assembly with k-mer-based multiplexing

Hybrid genome assembly has emerged as an important technique in bacterial genomics, but cost and labor requirements limit large-scale application. We present Ultraplexing, a method to improve per-sample sequencing cost and hands-on-time of Nanopore sequencing for hybrid assembly by at least 50%, compared to molecular barcoding while maintaining high assembly quality (Quality Value; QV [≥] 42). Ultraplexing requires the availability of Illumina data and uses inter-sample genetic variability to assign reads to isolates, which obviates the need for molecular barcoding. Thus, Ultraplexing can enable significant sequencing and labor cost reductions in large-scale bacterial genome projects.

bioinformatics↗

bioRxiv2019

Accelerating Sequence Alignment to Graphs

Aligning DNA sequences to an annotated reference is a key step for genotyping in biology. Recent scientific studies have demonstrated improved inference by aligning reads to a variation graph, i.e., a reference sequence augmented with known genetic variations. Given a variation graph in the form of a directed acyclic string graph, the sequence to graph alignment problem seeks to find the best matching path in the graph for an input query sequence. Solving this problem exactly using a sequential dynamic programming algorithm takes quadratic time in terms of the graph size and query length, making it difficult to scale to high throughput DNA sequencing data. In this work, we propose the first parallel algorithm for computing sequence to graph alignments that leverages multiple cores and single-instruction multiple-data (SIMD) operations. We take advantage of the available inter-task parallelism, and provide a novel blocked approach to compute the score matrix while ensuring high memory locality. Using a 48-core Intel Xeon Skylake processor, the proposed algorithm achieves peak performance of 317 billion cell updates per second (GCUPS), and demonstrates near linear weak and strong scaling on up to 48 cores. It delivers significant performance gains compared to existing algorithms, and results in run-time reduction from multiple days to three hours for the problem of optimally aligning high coverage long (PacBio/ONT) or short (Illumina) DNA reads to an MHC human variation graph containing 10 million vertices.\n\nAvailabilityThe implementation of our algorithm is available at https://github.com/ParBLiSS/PaSGAL. Data sets used for evaluation are accessible using https://alurulab.cc.gatech.edu/PaSGAL.

bioinformatics↗

bioRxiv2018

MetaMaps - Strain-level metagenomic assignment and compositional estimation for long reads

Metagenomic sequence classification should be fast, accurate and information-rich. Emerging long-read sequencing technologies promise to improve the balance between these factors but most existing methods were designed for short reads. MetaMaps is a new method, specifically developed for long reads, that combines the accuracy of slower alignment-based methods with the scalability of faster k-mer-based methods. Using an approximate mapping algorithm, it is capable of mapping a long-read metagenome to a comprehensive RefSeq database with >12,000 genomes in <30 GB or RAM on a laptop computer. Integrating these mappings with a probabilistic scoring scheme and EM-based estimation of sample composition, MetaMaps achieves >95% accuracy for species-level read assignment and r2 > 0.98 for the estimation of sample composition on both simulated and real data. Uniquely, MetaMaps outputs mapping locations and qualities for all classified reads, enabling functional studies (e.g. gene presence/absence) and the detection of novel species not present in the current database.\n\nAvailability and ImplementationMetaMaps is implemented in C++/Perl and freely available from https://github.com/DiltheyLab/MetaMaps (GPL v3).

bioinformatics↗

bioRxiv2018

A Fast Adaptive Algorithm for Computing Whole-Genome Homology Maps

MotivationWhole-genome alignment is an important problem in genomics for comparing different species, mapping draft assemblies to reference genomes, and identifying repeats. However, for large plant and animal genomes, this task remains compute and memory intensive.\n\nResultsWe introduce an approximate algorithm for computing local alignment boundaries between long DNA sequences. Given a minimum alignment length and an identity threshold, our algorithm computes the desired alignment boundaries and identity estimates using kmer-based statistics, and maintains sufficient probabilistic guarantees on the output sensitivity. Further, to prioritize higher scoring alignment intervals, we develop a plane-sweep based filtering technique which is theoretically optimal and practically efficient. Implementation of these ideas resulted in a fast and accurate assembly-to-genome and genome-to-genome mapper. As a result, we were able to map an error-corrected whole-genome NA12878 human assembly to the hg38 human reference genome in about one minute total execution time and < 4 GB memory using 8 CPU threads, achieving more than an order of magnitude improvement in both runtime and memory over competing methods. Recall accuracy of computed alignment boundaries was consistently found to be > 97% on multiple datasets. Finally, we performed a sensitive self-alignment of the human genome to compute all duplications of length [≥] 1 Kbp and [≥] 90% identity. The reported output achieves good recall and covers 5% more bases than the current UCSC genome browsers segmental duplication annotation.\n\nAvailabilityhttps://github.com/marbl/MashMap\n\nContactadam.phillippy@nih.gov, aluru@cc.gatech.edu

bioinformatics↗

bioRxiv2017

Bayesian analysis of genetic association across tree-structured routine healthcare data in the UK Biobank

Genetic discovery from the multitude of phenotypes extractable from routine healthcare data has the ability to radically transform our understanding of the human phenome, thereby accelerating progress towards precision medicine. However, a critical question when analysing high-dimensional and heterogeneous data is how to interrogate increasingly specific subphenotypes whilst retaining statistical power to detect genetic associations. Here we develop and employ a novel Bayesian analysis framework that exploits the hierarchical structure of diagnosis classifications to jointly analyse genetic variants against UK Biobank healthcare phenotypes. Our method displays a more than 20% increase in power to detect genetic effects over other approaches, such that we uncover the broader burden of genetic variation: we identify associations with over 2,000 diagnostic terms. We find novel associations with common immune-mediated diseases (IMD), we reveal the extent of genetic sharing between specific IMDs, and we expose differences in disease perception or diagnosis with potential clinical implications.

genetics↗

bioRxiv2017

A fast approximate algorithm for mapping long reads to large reference databases

Emerging single-molecule sequencing technologies from Pacific Biosciences and Oxford Nanopore have revived interest in long read mapping algorithms. Alignment-based seed-and-extend methods demonstrate good accuracy, but face limited scalability, while faster alignment-free methods typically trade decreased precision for efficiency. In this paper, we combine a fast approximate read mapping algorithm based on minimizers with a novel MinHash identity estimation technique to achieve both scalability and precision. In contrast to prior methods, we develop a mathematical framework that defines the types of mapping targets we uncover, establish probabilistic estimates of p-value and sensitivity, and demonstrate tolerance for alignment error rates up to 20%. With this framework, our algorithm automatically adapts to different minimum length and identity requirements and provides both positional and identity estimates for each mapping reported. For mapping human PacBio reads to the hg38 reference, our method is 290x faster than BWA-MEM with a lower memory footprint and recall rate of 96%. We further demonstrate the scalability of our method by mapping noisy PacBio reads (each [≥] 5 kbp in length) to the complete NCBI RefSeq database containing 838 Gbp of sequence and > 60, 000 genomes.

bioinformatics↗

bioRxiv2017

Genome Graphs

There is increasing recognition that a single, monoploid reference genome is a poor universal reference structure for human genetics, because it represents only a tiny fraction of human variation. Adding this missing variation results in a structure that can be described as a mathematical graph: a genome graph. We demonstrate that, in comparison to the existing reference genome (GRCh38), genome graphs can substantially improve the fractions of reads that map uniquely and perfectly. Furthermore, we show that this fundamental simplification of read mapping transforms the variant calling problem from one in which many non-reference variants must be discovered de-novo to one in which the vast majority of variants are simply re-identified within the graph. Using standard benchmarks as well as a novel reference-free evaluation, we show that a simplistic variant calling procedure on a genome graph can already call variants at least as well as, and in many cases better than, a state-of-the-art method on the linear human reference genome. We anticipate that graph-based references will supplant linear references in humans and in other applications where cohorts of sequenced individuals are available.

bioinformatics↗

bioRxiv2016

Practical Use of Methods for Imputation of HLA Alleles from SNP Genotype Data

The human leukocyte antigen (HLA) genes play an essential role in immune function. Typing of HLA alleles is critical for transplantation and is informative for many disease associations. The high cost of accurate lab-based HLA typing has precluded its use in large-scale disease-association studies. The development of statistical methods to type alleles using linkage disequilibrium with nearby SNPs, called HLA imputation, has allowed large cohorts of individuals to be typed accurately, so that massive numbers of affected individuals and controls may be studied. This has resulted in many important findings. Several HLA imputation methods have been widely used, however their relative performance has not been adequately addressed. We have conducted a comprehensive study to evaluate the most widely used HLA imputation methods. We assembled a multi-ethnic panel of 10,561 individuals with SNP genotype data and lab-based typing of alleles at 11 HLA genes at two-field resolution, and used it to train and validate each method. Use of this panel leads to imputation accuracy far superior to what is currently publicly available. We present a highly-accurate new imputation method, HLA*IMP:03. We address the question of optimal use of HLA imputations in tests of genetic association, showing that it is usually not necessary to apply a probability threshold to achieve maximal power. We also investigated the effect on accuracy of SNP density and population stratification at the continental level and show that neither of these are a significant concern.

genetics↗