Search bioRxiv⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.1101/2021.11.05.467426

Syotti: Scalable Bait Design for DNA Enrichment

Alanko, J.·Slizovskiy, I.·Lokshtanov, D.·Gagie, T.·Noyes, N.·Boucher, C.
View original source ↗Export metadata ↓

Abstract

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.

Explore related subjects

bioinformaticsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Alanko, J., Slizovskiy, I., Lokshtanov, D., Gagie, T., Noyes, N., Boucher, C.. 2021-11-05. Syotti: Scalable Bait Design for DNA Enrichment. https://doi.org/10.1101/2021.11.05.467426

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related preprints

bioRxiv2026

Accelerating discovery and integration from RNA to Protein with R2T2P

Integrating transcriptomics and proteomics data remains an unmet challenge in the post-genomics era, discouraging researchers from pursuing integrative approaches to molecular biology research. Leveraging the power of translation profiling, we present RNA to Translation to Protein (R2T2P), a computational platform integrating genome-guided transcriptome assembly with identification of translation and proteins, including a tailored differential analysis framework and support for multiple reference transcriptomes. We applied R2T2P to investigate a cellular model of facioscapulohumeral muscular dystrophy (FSHD), where ectopic expression of the DUX4 retrogene in skeletal muscle triggers significant alterations in transcription and RNA metabolism. We uncovered hundreds of uncharacterized, highly overexpressed RNAs, including antisense and alternative transcripts, and quantified their contribution to translatome and proteome. Re-analysis of expression datasets from patient-derived myotubes and muscle biopsies validated this alternative transcriptome in FSHD patients, adding a reservoir of bona-fide novel molecular actors in a rare disease. Available at https://github.com/nfdata-omics/R2T2P/, R2T2P is a flexible and powerful workflow in modern integrative biology.

bioinformatics↗
bioRxiv2026

MorphoANOVA: Dissecting Histology-Gene Expression Relationships in Spatial Transcriptomics

Spatial transcriptomics (ST) measures the expression of hundreds to thousands of genes within tissue architecture, often accompanied by histology images. However, it remains challenging to systematically characterize which genes exhibit associations with tissue morphology, whether these associations vary spatially, and which genes show additional spatial expression patterns beyond those captured by morphology. Here we introduce MorphoANOVA, a gene-wise statistical framework for characterizing morphology--expression relationships across genes measured by ST. Using nested spatially varying coefficient models and sequential ANOVA, MorphoANOVA assesses slide-wide associations with an H\&E-derived morphology feature, location-specific changes in these associations, and additional spatial variation after accounting for the selected feature. The resulting statistics enable gene prioritization and pathway enrichment analysis, while spatial component maps support the interpretation of individual genes. Simulations demonstrate MorphoANOVA's ability to distinguish the modeled components and recover their spatial patterns. Applications to human cortex and breast cancer identify biological programs associated with different morphology--expression patterns and reveal distinct relationships with cell composition. Across three HER2-positive breast cancer patients, invasive-cancer marker genes consistently exhibit stronger evidence of location-specific morphology associations. MorphoANOVA thus provides a framework for systematically interpreting spatial gene-expression patterns in relation to tissue morphology.

bioinformatics↗
bioRxiv2026

Evaluation effects can rival reported concordance gains in cross-cancer survival prediction

Studies of cross-cancer learning for survival prediction from tumour omics have reported concordance gains of 0.020 and 0.045, but how such gains compare with evaluation effects remains unclear. We examined these effects across 13 TCGA cancers (5,761 patients, 1,526 disease-specific deaths), using five repeats of five-fold cross-validation and paired bootstrap intervals. When model selection did not use test data, our borrowing model gained 0.009 (95% interval 0.001 to 0.016) over its target-fitted reference when cancers received equal weight (post hoc). Random-effects pooling gave a gain of 0.002 (-0.002 to 0.006), with most weight assigned to cancers where the model made little use of the pretrained score. Choosing the fusion weight on test splits raised the apparent equal-weight gain to 0.017. We reimplemented a published method, VAECox, which showed no pretraining gain over random initialisation at the last or validation-selected training step. Choosing each network's best test step, as the published code does, raised concordance by 0.03 to 0.05 across the 13-cancer and ten-cancer overall-survival settings, but barely changed the difference between networks. In a constructed post hoc experiment, choosing the best test step only for the pretrained network changed the equal-weight mean difference from -0.004 to +0.045 (+0.035 to +0.054). Across seven multi-omics comparisons, estimates from single five-fold runs differed from their cancer's five-run mean by at least 0.02 in 11% to 42% of runs. Concordance was about 0.02 lower at held-out tissue source sites. Interpreting a reported gain therefore requires each model's selection rule, variation across repeated partitions, the weighting of cancers and the evaluation population.

bioinformatics↗