YYYun William Yu

Yun William Yu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Yun William Yu has a total of 72 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Approximate local alignment via chained MEM divergence estimation for detecting horizontal gene transfer

    by Grace Oualline, Sakshi Pandey, Xiaolei Brian Zhang, Christina Boucher, Yun William Yu

    Local alignment tools struggle at querying against thousands of bacterial genomes, because the reference indexes are memory-intensive and base-level dynamic programming is slow. We present alamem ( https://github.com/yunwilliamyu/alamem ), an approximate local aligner that streams unprocessed reference databases and estimates average nucleotide identity (ANI) from Maximal-Exact-Match (MEM) chaining statistics. Alamem can query a bacterial genome against >85,000 prokaryotic genomes in under 30 seconds (with multithreading) using 4 GB of memory, making it over 16x faster and 21x more memory-efficient than existing local aligners using their default running modes. On top of alamem, we built alasight ( https://github.com/graceoualline/alasight ) for detecting signatures of horizontal gene transfer (HGT) by finding pairs of alamem hits to divergent genomes. Alasight achieves over an order of magnitude better sensitivity on data from real bovid microbiomes than existing mobile genetic element-detection software and provides depth and sparsity information supporting each putative HGT region.

  • k -mer-based Upstream Preprocessing of long reads for Isoform Discovery

    by Molly Borowiak, Yun William Yu

    Eukaryotic genes can encode multiple protein isoforms based on alternative splicing of their transcribed regions. Most modern novel isoform discovery methods function by identifying and assembling exon splice junctions from an RNA-seq sample. However, splice junctions can only be accurately annotated with time-intensive dynamic programming alignment. This manuscript introduces KuPID, a method for preprocessing long RNA-seq reads with the goal of better identifying novel isoform transcripts. KuPID utilizes k -mer sketching as a prefilter to quickly pseudo-align reads to known reference isoforms. Full alignment need only then be applied to reads that are most relevant to isoform discovery. Not only does KuPID speed up the discovery pipeline, it also increases downstream accuracy by filtering out extraneous reads. KuPID preprocessing simultaneously increases the f1 accuracy of isoform discovery pipelines by up to 11.6 points while decreasing the runtime by a factor of 2-3×;. An optional mode permits a KuPID sample to be paired with both isoform discovery and transcript quantification.

  • Open Access

    Incorporating indel channels into average-case analysis of seed-chain-extend.

    by Spencer Gibson, Yun William Yu

    Given a sequence s1 of n letters drawn independently and identically (i.i.d.) from an alphabet of size σ and a mutated substring s2 of length m<n, we want to recover the mutation history that generated s2 from s1. Many modern sequence aligners for this task use seed-chain-extend with k-mer seeds. Previously, Shaw and Yu showed linear-gap cost chaining can produce a chain with 1-O(1m) recoverability, the proportion of the mutation history that is recovered, in O(mn2.43θ log n) expected time for seed-chain-extend (assuming pre-seeded reference), where θ<0.206 is the mutation rate under a substitution-only channel and s1 is uniformly random. A gap remains between theory and practice, as real genomes include insertions and deletions (indels). We introduce mathematical machinery to deal with the two new obstacles introduced by indel channels: the dependence of neighbouring anchors and the presence of anchors that are only partially correct. We prove that expected recoverability of an optimal chain is ≥1-O(1m) and expected runtime is O(mn3.15·θT log n), given the total mutation rate θT=θi+θd+θs (sum of substitution, insertion, and deletion rates) is θT≤0.159. We thus narrow (but not close) the gap between theory and practice. https://github.com/Lazarus42/seed_chainer_indels.


  • Open Access

    RAmpSim: a thermodynamic simulator for hybridization capture in metagenomic sequencing

    by Aidan Zhang, Christina Boucher, Noelle Noyes, Yun William Yu

    Motivation: Simulators that generate synthetic datasets help address the lack of ground truth for developing and benchmarking computational tools. Many read simulators assume uniform sampling across reference genomes; however, for newer capture-based sequencing technologies (e.g. TELSeq), this assumption is intentionally broken to oversample regions of interest. Along with systematic biases arising from probe multiplicity, sequence composition, and species abundances inherent to capture-based sequencing, this mismatch between modeling assumptions and the characteristics of real data necessitates the design of a new capture-based sequencing-specific simulator. Results: We present RAmpSim, a fast simulator that models bait–target hybridization and fragment capture using a thermodynamic nearest-neighbor energy model and Boltzmann-weighted sampling of binding sites. Fragments are generated through multinomial sampling parameterized by bait concentration, binding energy, and genomic abundance before being passed to existing models of platform-specific errors. Implemented in Rust, RAmpSim reproduces empirical within-genome coverage and cross-species enrichment patterns observed in capture-based metagenomic datasets. RAmpSim generally outperforms a uniform baseline with respect to position-based earth mover’s distance when compared against the empirical coverage distribution. Classification analysis also shows high recall in recovering empirical high-coverage regions while outperforming a uniform baseline. Availability: Code, example scripts, and data sources are available at https://github.com/az002/RAmpSim.git.

  • Open Access

    RAmpSim: A Thermodynamic Simulator for Hybridization Capture in Metagenomic Sequencing

    by Aidan Zhang, Christina Boucher, Noelle Noyes, Yun William Yu

    Hybridization (bait) capture combined with long-read sequencing enables targeted profiling within complex metagenomes but introduces systematic biases from bait multiplicity, sequence composition, and species abundance that existing simulators ignore. We present RAmpSim, a fast simulator that models bait-target hybridization and fragment capture using a thermodynamic nearest-neighbor energy model and Boltzmann-weighted sampling of binding sites. Fragments are generated through multinomial sampling parameterized by bait concentration, binding energy, and genomic abundance before being passed to existing long-read simulators for modeling platform-specific errors. Implemented in Rust, RAmpSim reproduces empirical within-genome coverage and cross-species enrichment patterns observed in capture-based metagenomic datasets. Compared to uniform-coverage baselines,RAmpSim's simulated coverage distributions are up to an order of magnitude closer to real data with respect to earth mover's distance. Classification analysis reveals high recall in classifying high coverage regions between simulated and experimental distributions while outperforming a uniform baseline. Supporting accurate benchmarking and bait-set evaluation, RAmpSim provides an interpretable, efficient framework for simulating capture-based metagenomic sequencing.


  • Open Access

    KuPID: Kmer-based Upstream Preprocessing of Long Reads for Isoform Discovery

    by Molly Borowiak, Yun William Yu

    Eukaryotic genes can encode multiple protein isoforms based on alternative splicing of their transcribed regions. Most modern novel isoform discovery methods function by identifying and assembling exon splice junctions from an RNAseq sample. However, splice junctions can only be accurately annotated with time-intensive dynamic programming alignment. This manuscript introduces KuPID, a method for preprocessing long RNAseq reads with the goal of better identifying novel isoform transcripts. KuPID utilizes kmer sketching as a pre-filter to quickly pseudo-align reads to known reference isoforms. Full alignment need only then be applied to reads that are most relevant to isoform discovery. Not only does KuPID speed up the discovery pipeline, it also increases downstream accuracy by filtering out extraneous reads. KuPID preprocessing simultaneously increases the f1 accuracy of isoform discovery pipelines by up to 16.7 points while decreasing the runtime by a factor of 2-3x. An optional mode permits a KuPID sample to be paired with both isoform discovery and transcript quantification. Code availability: https://github.com/mboro2000/KuPID.git

  • Open Access

    Incorporating indel channels into average-case analysis of seed-chain-extend

    by Spencer Gibson, Yun William Yu

    Given a sequence $s_1$ of $n$ letters drawn i.i.d. from an alphabet of size $σ$ and a mutated substring $s_2$ of length $m < n$, we often want to recover the mutation history that generated $s_2$ from $s_1$. Modern sequence aligners are widely used for this task, and many employ the seed-chain-extend heuristic with $k$-mer seeds. Previously, Shaw and Yu showed that optimal linear-gap cost chaining can produce a chain with $1 - O\left(\frac{1}{\sqrt{m}}\right)$ recoverability, the proportion of the mutation history that is recovered, in $O\left(mn^{2.43θ} \log n\right)$ expected time, where $θ< 0.206$ is the mutation rate under a substitution-only channel and $s_1$ is assumed to be uniformly random. However, a gap remains between theory and practice, since real genomic data includes insertions and deletions (indels), and yet seed-chain-extend remains effective. In this paper, we generalize those prior results by introducing mathematical machinery to deal with the two new obstacles introduced by indel channels: the dependence of neighboring anchors and the presence of anchors that are only partially correct. We are thus able to prove that the expected recoverability of an optimal chain is $\ge 1 - O\Bigl(\frac{1}{\sqrt{m}}\Bigr)$ and the expected runtime is $O(mn^{3.15 \cdot θ_T}\log n)$, when the total mutation rate given by the sum of the substitution, insertion, and deletion mutation rates ($θ_T = θ_i + θ_d + θ_s$) is less than $0.159$.

  • Open Access

    Long-read reconstruction of many diverse haplotypes with devider

    by Jim Shaw, Christina Boucher, Yun William Yu, Noelle Noyes, Heng Li

    Reconstructing exact haplotypes is important when sequencing a mixture of similar sequences. Long-read sequencing can connect distant alleles to disentangle similar haplotypes, but handling sequencing errors requires specialized techniques. Here, we present devider , an algorithm for haplotyping small sequences, such as viruses or genes, from long-read sequencing. devider uses a positional de Bruijn graph with sequence-to-graph alignment on an alphabet of informative alleles to provide a fast assembly-inspired approach compatible with various long-read sequencing technologies. On a synthetic Oxford Nanopore Technologies (ONT) long-read data set containing seven HIV strains, devider recovers 97% of the haplotype content and has the most accurate abundance estimates while taking 8000× coverage. Benchmarking on synthetic mixtures of antimicrobial-resistance (AMR) genes shows that devider recovers 83% of haplotypes, 23 percentage points higher than the next best method. On real Pacific Biosciences (PacBio) and ONT data sets, devider recapitulates previously known results in seconds, disentangling a bacterial community with more than 10 strains and an HIV-1 coinfection data set. We use devider to investigate the within-host diversity of a long-read bovine gut metagenome enriched for AMR genes, discovering 13 distinct haplotypes for a tet(Q) tetracycline-resistance gene with >18,000× coverage and six haplotypes for a CfxA2 beta-lactamase gene. We find clear recombination blocks for these AMR gene haplotypes, showcasing devider's ability to unveil evolutionary signals for heterogeneous mixtures.


  • Open Access

    devider: long-read reconstruction of many diverse haplotypes

    by Jim Shaw, Christina Boucher, Yun William Yu, Noelle Noyes, Heng Li

    Reconstructing haplotypes is important when sequencing a mixture of similar sequences. Long-read sequencing can connect distant alleles to disentangle similar haplotypes, but handling se-quencing errors requires specialized techniques. We present devider , an algorithm for haplotyping small sequences—such as viruses or genes—from long-read sequencing. devider uses a positional de Bruijn graph with sequence-to-graph alignment on an alphabet of informative alleles to provide a fast assembly-inspired approach compatible with various long-read sequencing technologies. On a synthetic Nanopore dataset containing seven HIV strains, devider recovered 97% of the haplotype content compared to 86% for the next best method while taking < 4 minutes and 1 GB of memory for > 8000× coverage. Benchmarking on synthetic mixtures of antimicrobial resistance (AMR) genes showed that devider recovered 83% of haplotypes, 23 percentage points higher than the next best method. On real PacBio and Nanopore datasets, devider recapitulates previously known results in seconds, disentan-gling a bacterial community with > 10 strains and an HIV-1 co-infection dataset. We used devider to investigate the within-host diversity of a long-read bovine gut metagenome enriched for AMR genes, discovering 13 distinct haplotypes for a tet(Q) tetracycline resistance gene with > 18, 000× coverage and 6 haplotypes for a CfxA2 beta-lactamase gene. We found clear recombination blocks for these AMR gene haplotypes, showcasing devider ’s ability to unveil ecological signals for heterogeneous mixtures.


  • Top Cited Papers
    Open Access

    Rapid species-level metagenome profiling and containment estimation with sylph

    by Jim Shaw, Yun William Yu

    Profiling metagenomes against databases allows for the detection and quantification of microorganisms, even at low abundances where assembly is not possible. We introduce sylph, a species-level metagenome profiler that estimates genome-to-metagenome containment average nucleotide identity (ANI) through zero-inflated Poisson k-mer statistics, enabling ANI-based taxa detection. On the Critical Assessment of Metagenome Interpretation II (CAMI2) Marine dataset, sylph was the most accurate profiling method of seven tested. For multisample profiling, sylph took >10-fold less central processing unit time compared to Kraken2 and used 30-fold less memory. Sylph’s ANI estimates provided an orthogonal signal to abundance, allowing for an ANI-based metagenome-wide association study for Parkinson disease (PD) against 289,232 genomes while confirming known butyrate–PD associations at the strain level. Sylph took <1 min and 16 GB of random-access memory to profile metagenomes against 85,205 prokaryotic and 2,917,516 viral genomes, detecting 30-fold more viral sequences in the human gut compared to RefSeq. Sylph offers precise, efficient profiling with accurate containment ANI estimation even for low-coverage genomes.