More Like this

1. Accurate short-read alignment through r-index-based pangenome indexing

   https://doi.org/10.1101/gr.279858.124  

   Varki, Rahul; Rossi, Massimiliano; Ferro, Eddie; Oliva, Marco; Garrison, Erik; Langmead, Ben; Boucher, Christina (June 2025, Genome Research)

   Aligning to a linear reference genome can result in a higher percentage of reads going unmapped or being incorrectly mapped owing to variations not captured by the reference, otherwise known as reference bias. Recently, in efforts to mitigate reference bias, there has been a movement to switch to using pangenomes, a collection of genomes, as the reference. In this paper, we introduce Moni-align, the first short-read pangenome aligner built on the r-index, a variation of the classical FM-index that can index collections of genomes in O(r)-space, whereris the number of runs in the Burrows–Wheeler transform. Moni-align uses a seed-and-extend strategy for aligning reads, utilizing maximal exact matches as seeds, which can be efficiently obtained with ther-index. Using both simulated and real short-read data sets, we demonstrate that Moni-align achieves alignment accuracy comparable to vg map and vg giraffe, the leading pangenome aligners. Although currently best suited for aligning to localized pangenomes owing to computational constraints, Moni-align offers a robust foundation for future optimizations that could further broaden its applicability. 

   more » « less
2. A variant selection framework for genome graphs

   https://doi.org/10.1093/bioinformatics/btab302  

   Jain, Chirag; Tavakoli, Neda; Aluru, Srinivas (July 2021, Bioinformatics)

   Abstract Motivation Variation graph representations are projected to either replace or supplement conventional single genome references due to their ability to capture population genetic diversity and reduce reference bias. Vast catalogues of genetic variants for many species now exist, and it is natural to ask which among these are crucial to circumvent reference bias during read mapping. Results In this work, we propose a novel mathematical framework for variant selection, by casting it in terms of minimizing variation graph size subject to preserving paths of length α with at most δ differences. This framework leads to a rich set of problems based on the types of variants [e.g. single nucleotide polymorphisms (SNPs), indels or structural variants (SVs)], and whether the goal is to minimize the number of positions at which variants are listed or to minimize the total number of variants listed. We classify the computational complexity of these problems and provide efficient algorithms along with their software implementation when feasible. We empirically evaluate the magnitude of graph reduction achieved in human chromosome variation graphs using multiple α and δ parameter values corresponding to short and long-read resequencing characteristics. When our algorithm is run with parameter settings amenable to long-read mapping (α = 10 kbp, δ = 1000), 99.99% SNPs and 73% SVs can be safely excluded from human chromosome 1 variation graph. The graph size reduction can benefit downstream pan-genome analysis. Availability and implementation https://github.com/AT-CG/VF. Supplementary information Supplementary data are available at Bioinformatics online. 

   more » « less
3. Best-practice guidance for Earth BioGenome Project sample collection and processing: progress and challenges in biodiverse reference genome creation

   https://doi.org/10.1093/gigascience/giaf041  

   Lawniczak, Mara_K_N; Kocot, Kevin_M; Astrin, Jonas_J; Blaxter, Mark; Sotero-Caio, Cibele_G; Barker, Katharine_B; Childers, Anna_K; Coddington, Jonathan; Davis, Paul; Howe, Kerstin; et al (May 2025, GigaScience)

   Abstract The Earth BioGenome Project has the extremely ambitious goal of generating, at scale, high-quality reference genomes across the entire Tree of Life. Currently in its first phase, the project is targeting family-level representatives and is progressing rapidly. Here we outline recommended standards and considerations in sample acquisition and processing for those involved in biodiverse reference genome creation. These standards and recommendations will evolve with advances in related processes. Additionally, we discuss the challenges raised by the ambitions for later phases of the project, highlighting topics related to sample collection and processing that require further development. 

   more » « less
4. Validating Paired-end Read Alignments in Sequence Graphs

   https://doi.org/10.1101/682799  

   Jain, Chirag; Zhang, Haowen; Dilthey, Alexander; Aluru, Srinivas (September 2019, Leibniz international proceedings in informatics)

   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. 

   more » « less
5. A super-pangenome of the North American wild grape species

   https://doi.org/10.1186/s13059-023-03133-2  

   Cochetel, Noé; Minio, Andrea; Guarracino, Andrea; Garcia, Jadran F.; Figueroa-Balderas, Rosa; Massonnet, Mélanie; Kasuga, Takao; Londo, Jason P.; Garrison, Erik; Gaut, Brandon S.; et al (December 2023, Genome Biology)

   Abstract BackgroundCapturing the genetic diversity of wild relatives is crucial for improving crops because wild species are valuable sources of agronomic traits that are essential to enhance the sustainability and adaptability of domesticated cultivars. Genetic diversity across a genus can be captured in super-pangenomes, which provide a framework for interpreting genomic variations. ResultsHere we report the sequencing, assembly, and annotation of nine wild North American grape genomes, which are phased and scaffolded at chromosome scale. We generate a reference-unbiased super-pangenome using pairwise whole-genome alignment methods, revealing the extent of the genomic diversity among wild grape species from sequence to gene level. The pangenome graph captures genomic variation between haplotypes within a species and across the different species, and it accurately assesses the similarity of hybrids to their parents. The species selected to build the pangenome are a great representation of the genus, as illustrated by capturing known allelic variants in the sex-determining region and for Pierce’s disease resistance loci. Using pangenome-wide association analysis, we demonstrate the utility of the super-pangenome by effectively mapping short reads from genus-wide samples and identifying loci associated with salt tolerance in natural populations of grapes. ConclusionsThis study highlights how a reference-unbiased super-pangenome can reveal the genetic basis of adaptive traits from wild relatives and accelerate crop breeding research. 

   more » « less