Biology subjects

Jain, C.

Publications and source records attributed to Jain, C..

At least 19 recordsLinked to original sources

bioRxiv2026

NanoLabel: A fast and accurate real-time nanopore signal classifier

Oxford Nanopore Technologies adaptive sampling capability promises to reduce sequencing cost and turnaround time. At its core, adaptive sampling is a real-time classification problem that distinguishes reads originating from regions of interest. Direct signal-based classification approaches bypass the computational bottleneck of basecalling and can eliminate the need for powerful GPUs. However, operating directly on noisy raw signals remains challenging in real-time settings, where classification decisions must be made quickly. In this work, we propose NanoLabel, a new method for real-time classification of nanopore signals. We build NanoLabel on top of signal-based read mapping tool, RawHash2. We accelerate the classification workflow by mapping reads using only the target regions as the reference. To further improve accuracy, we train a lightweight classifier on mapping-derived features and introduce a data augmentation strategy to construct sufficiently large and class-balanced training datasets. We evaluate NanoLabel using publicly available real sequencing datasets from three human genomes (HG001, HG002, and HG005), while assuming a cancer gene panel as the target. Compared to directly mapping reads with RawHash2, we demonstrate 80 x improvement in the classification time and 0.10 - 0.25 units improvement in the F1 score.

genomics↗

bioRxiv2025

Billi: Provably Accurate and Scalable Bubble Detection in Pangenome Graphs

A key application of pangenome graphs is the characterization of small and large genomic variants represented as bubbles within the graph. Although bubbles have been extensively studied in directed graphs in the context of genome assembly, there remains a need for a rigorous definition and systematic analysis of bubbles in bidirected graphs, which is the predominant data structure used to represent pangenomes. We show that existing bubble definitions for bidirected graphs do not fully meet the requirements for representing genetic sites and alleles; in particular, overlapping bubbles may not exhibit strict nesting. To address this, we introduce a new sub-graph abstraction called panbubble and prove that it satisfies the desired structural properties for variant characterization. We then present an exact algorithm with runtime [O] (|V |2(|V | + |E|)) for detecting all panbubbles in a bidirected graph G = (V, E). In addition, we propose a heuristic algorithm that produces identical output as the exact algorithm in practice and scales to large graphs, including both the first and second releases of the Human Pangenome Reference Consortium (HPRC). We implemented our algorithms in the tool Billi (github.com/at-cg/billi). On our largest dataset, Billi is more than 15x faster and uses over 5x less memory than VG.

bioinformatics↗

bioRxiv2025

Iron addicted colorectal cancers exploit Heme-Complex II axis to resist oxidative cell death

Colorectal cancer (CRC) cells are addicted to iron, which fuels nucleotide synthesis, mitochondrial respiration, and rapid proliferation. Yet paradoxically, high intracellular iron is cytotoxic to most other cells, raising the question of how CRC cells tolerate and exploit iron-rich environments. One pathway thought to mediate iron toxicity is ferroptosis, an iron-dependent form of cell death. However, most ferroptosis regulators were identified through synthetic chemical screens or small molecule activators, and it remains unclear whether these canonical pathways explain how iron itself triggers cell death, particularly in vivo. Here, using multi-omics profiling, CRISPR screening, and in vivo models, we uncover a heme-succinate dehydrogenase (SDH)-Coenzyme Q (CoQ) axis that enables CRC cells to buffer iron-induced oxidative stress. Heme-dependent SDH reduces CoQ, which redistributes to mitochondrial and plasma membranes to detoxify lipid ROS as a radical trapping antioxidant. This pathway functions alongside, and in some contexts independently of, canonical ferroptosis regulators. These findings reveal that CRCs co-opt metabolic cofactors not only for growth but also for survival under physiologically toxic iron levels, uncovering new vulnerabilities for therapy.

cancer biology↗

bioRxiv2025

Targeting HIF-2α in Colorectal Cancer Reveals a Cholesterol Biosynthesis-Dependent Ferroptotic Vulnerability

Colorectal carcinoma (CRC) remains a major cause of cancer-related mortality, with rising incidence in individuals under 55, highlighting the need for novel therapeutic strategies. Hypoxia-inducible factor 2 alpha (HIF-2) has been genetically validated as a critical driver of colorectal tumorigenesis, with intestinal epithelium-specific deletion in mice markedly reducing tumor formation. PT2385, a selective small-molecule HIF-2 inhibitor applied in renal cell carcinoma treatment, has not been evaluated in CRC. Here, we demonstrate that HIF-2 inhibition with PT2385 alone fails to suppress CRC growth in vitro under normoxic or hypoxic conditions and in xenograft models in vivo. To identify vulnerabilities induced by HIF-2 blockade, we performed an unbiased CRISPR metabolic screen. This revealed cholesterol biosynthesis as a critical dependency. Targeting this pathway with clinically approved statins (atorvastatin, pitavastatin, simvastatin) synergized with PT2385 to suppress CRC cell growth, reduce colony formation, and enhance cell death. Mechanistic studies show that combined HIF-2 and HMG-CoA reductase inhibition with statins promotes ferroptosis, characterized by increased lipid peroxidation and depletion of antioxidant metabolites. These effects are fully reversed by the ferroptosis inhibitor liproxstatin-1. Genetic knockdown of HIF-2 or HMG-CoA reductase recapitulated enhanced sensitivity to combination therapy. In vivo, co-administration of PT2385 and atorvastatin significantly reduced tumor growth and increased ferroptotic cell death in xenografts, confirming the mechanistic link. Collectively, these findings uncover a metabolic vulnerability of CRC to dual HIF-2 and cholesterol biosynthesis inhibition, supporting a clinically actionable strategy that leverages safe, FDA-approved statins to potentiate HIF-2-targeted therapy. SignificanceCombined HIF-2 inhibition and cholesterol biosynthesis inhibition using statins reveals a metabolic vulnerability in colorectal cancer that enhances ferroptosis, thus offering a clinically actionable strategy for therapeutic intervention.

cancer biology↗

bioRxiv2025

Haplotype-aware long-read error correction

Error correction of long reads is an important initial step in genome assembly workflows. For organisms with ploidy greater than one, it is important to preserve haplotype-specific variation during read correction. This challenge has driven the development of several haplotype-aware correction methods. However, existing methods are based on either ad-hoc heuristics or deep learning approaches. In this paper, we introduce a rigorous formulation for this problem. Our approach builds on the minimum error correction framework used in reference-based haplotype phasing. We prove that the proposed formulation for error correction of reads in de novo context, i.e., without using a reference genome, is NP-hard. To make our exact algorithm scale to large datasets, we introduce practical heuristics. Experiments using PacBio HiFi sequencing datasets from human and plant genomes show that our approach achieves accuracy comparable to state-of-the-art methods. The software is freely available at https://github.com/at-cg/HALE.

genomics↗

bioRxiv2024

Accelerating whole-genome alignment in the age of complete genome assemblies

Recent advancements in long-read sequencing and assembly methods have ushered in an era of high-quality genome assemblies. Modern assemblies commonly feature megabase-long sequences frequently spanning entire chromosomes. The increase in the assembly contiguity and the reduced number of assembly contigs also implies that whole-genome alignment is no longer an embarrassingly parallel problem. The conventional method of aligning sequences of the query genome in parallel is to utilize a single thread per sequence. This results in poor CPU utilization and long runtimes. In this work, we designed optimizations to accelerate whole-genome alignment on multi-core processors and implemented them in a commonly used aligner, minimap2. Our improvements include a fine-grained parallel chaining method and a fast mechanism for differentiating primary and secondary chains. Our approach accelerates alignment of human, plant, and primate genomes by 1.6x to 7.2x without compromising accuracy.

bioinformatics↗

bioRxiv2024

Integer programming framework for pangenome-based genome inference

Affordable genotyping methods are essential in genomics. Commonly used genotyping methods primarily support single nucleotide variants and short indels but neglect structural variants. Additionally, accuracy of read alignments to a reference genome is unreliable in highly polymorphic and repetitive regions, further impacting genotyping performance. Recent works highlight the advantage of haplotype-resolved pangenome graphs in addressing these challenges. Building on these developments, we propose a rigorous alignment-free genotyping framework. Our formulation seeks a path through the pangenome graph that maximizes the matches between the path and substrings of sequencing reads (e.g., k-mers) while minimizing recombination events (haplotype switches) along the path. We prove that this problem is NP-Hard and develop efficient integer-programming solutions. We benchmarked the algorithm using downsampled short-read datasets from homozygous human cell lines with coverage ranging from 0.1x to 10x. Our algorithm accurately estimates complete major histocompatibility complex (MHC) haplotype sequences with small edit distances from the ground-truth sequences, providing a significant advantage over existing methods on low-coverage inputs. Although our algorithm is designed for haploid samples, we discuss future extensions to diploid samples. Implementationhttps://github.com/at-cg/PHI

bioinformatics↗

bioRxiv2023

Concerted SUMO-targeted ubiquitin ligase activities of TOPORS and RNF4 are essential for stress management and cell proliferation

Protein SUMOylation provides a principal driving force for cellular stress responses including DNA-protein crosslink (DPC) repair and arsenic-induced PML body degradation. In genome-scale screens, we identified the human E3 ligase TOPORS as a key effector of SUMO-dependent DPC resolution. We demonstrate that TOPORS promotes DPC repair by functioning as a SUMO-targeted ubiquitin ligase (STUbL) for DPCs, combining ubiquitin ligase activity through its RING domain with poly-SUMO chain binding via a cluster of SUMO-interacting motifs, analogous to the STUbL RNF4. Surprisingly, the STUbL activities of TOPORS and RNF4 are both required for SUMO-dependent DPC repair, PML degradation and other stress responses, making overlapping and distinct contributions to ubiquitin chain formation on SUMOylated targets to enable p97/VCP unfoldase recruitment. Combined loss of TOPORS and RNF4 is synthetic lethal even in unstressed cells, leading to defective clearance of SUMOylated proteins from chromatin accompanied by cell cycle arrest and apoptosis. Together, our findings establish TOPORS as a novel STUbL whose concerted action with RNF4 defines a general mechanistic principle in crucial cellular processes governed by direct SUMO-ubiquitin crosstalk. HighlightsO_LIThe RING E3 ligase TOPORS is required for SUMO-dependent DPC repair C_LIO_LITOPORS is a novel SUMO-targeted ubiquitin ligase (STUbL) C_LIO_LITOPORS promotes multiple STUbL-driven processes in conjunction with RNF4 C_LIO_LICombined TOPORS and RNF4 loss is synthetic lethal in human cells C_LI

molecular biology↗

bioRxiv2023

Haplotype-aware Sequence-to-Graph Alignment

Modern pangenome graphs are built using haplotype-resolved genome assemblies. During read mapping to a pangenome graph, prioritizing alignments that are consistent with the known haplotypes has been shown to improve genotyping accuracy. However, the existing rigorous formulations for sequence-to-graph co-linear chaining and alignment problems do not consider the haplotype paths in a pangenome graph. This often leads to spurious read alignments to those paths that are unlikely recombinations of the known haplotypes. In this paper, we develop novel formulations and algorithms for haplotype-aware sequence alignment to an acyclic pangenome graph. We consider both sequence-to-graph chaining and sequence-to-graph alignment problems. Drawing inspiration from the commonly used models for genotype imputation, we assume that a query sequence is an imperfect mosaic of the reference haplotypes. Accordingly, we extend previous chaining and alignment formulations by introducing a recombination penalty for a haplotype switch. First, we solve haplotype-aware sequence-to-graph alignment in O(|Q| | E| |[H]|) time, where Q is the query sequence, E is the set of edges, and [H] is the set of haplotypes represented in the graph. To complement our solution, we prove that an algorithm significantly faster than O(|Q| | E| |[H]|) is impossible under the Strong Exponential Time Hypothesis (SETH). Second, we propose a haplotype-aware chaining algorithm that runs in O(|[H]| N log |[H]|N) time after graph preprocessing, where N is the count of input anchors. We then establish that a chaining algorithm significantly faster than O(|[H]|N) is impossible under SETH. As a proof-of-concept of our algorithmic solutions, we implemented the chaining algorithm in the Minichain aligner (https://github.com/at-cg/minichain). We demonstrate the advantage of the algorithm by aligning sequences sampled from human major histocompatibility complex (MHC) to a pangenome graph of 60 MHC haplotypes. The proposed algorithm offers better consistency with ground-truth recombinations when compared to a haplotype-agnostic algorithm.

bioinformatics↗

bioRxiv2023

Telomere-to-telomere assembly by preserving contained reads

Automated telomere-to-telomere (T2T) de novo assembly of diploid and polyploid genomes remains a formidable task. A string graph is a commonly used assembly graph representation in the overlap-based algorithms. The string graph formulation employs graph simplification heuristics, which drastically reduce the count of vertices and edges. One of these heuristics involves removing the reads contained in longer reads. However, this procedure is not guaranteed to be safe. In practice, it occasionally introduces gaps in the assembly by removing all reads that cover one or more genome intervals. The factors contributing to such gaps remain poorly understood. In this work, we mathematically derived the frequency of observing a gap near a germline and a somatic heterozygous variant locus. Our analysis shows that (i) an assembly gap due to contained read deletion is an order of magnitude more frequent in Oxford Nanopore reads than PacBio HiFi reads due to differences in their read-length distributions, and (ii) this frequency decreases with an increase in the sequencing depth. Drawing cues from these observations, we addressed the weakness of the string graph formulation by developing the RAFT assembly algorithm. RAFT addresses the issue of contained reads by fragmenting reads and producing a more uniform readlength distribution. The algorithm retains spanned repeats in the reads during the fragmentation. We empirically demonstrate that RAFT significantly reduces the number of gaps using simulated datasets. Using real Oxford Nanopore and PacBio HiFi datasets of the HG002 human genome, we achieved a twofold increase in the contig NG50 and the number of haplotype-resolved T2T contigs compared to Hifiasm.

bioinformatics↗

bioRxiv2023

Co-linear Chaining on Pangenome Graphs

Pangenome reference graphs are useful in genomics because they compactly represent the genetic diversity within a species, a capability that linear references lack. However, efficiently aligning sequences to these graphs with complex topology and cycles can be challenging. The seed-chain-extend based alignment algorithms use co-linear chaining as a standard technique to identify a good cluster of exact seed matches that can be combined to form an alignment. Recent works show how the co-linear chaining problem can be efficiently solved for acyclic pangenome graphs by exploiting their small width [Makinen et al., TALG19] and how incorporating gap cost in the scoring function improves alignment accuracy [Chandra and Jain, RECOMB23]. However, it remains open on how to effectively generalize these techniques for general pangenome graphs which contain cycles. Here we present the first practical formulation and an exact algorithm for co-linear chaining on cyclic pangenome graphs. We rigorously prove the correctness and computational complexity of the proposed algorithm. We evaluate the empirical performance of our algorithm by aligning simulated long reads from the human genome to a cyclic pangenome graph constructed from 95 publicly available haplotype-resolved human genome assemblies. While the existing heuristic-based algorithms are faster, the proposed algorithm provides a significant advantage in terms of accuracy. Implementationhttps://github.com/at-cg/PanAligner

bioinformatics↗

bioRxiv2022

Sequence to graph alignment using gap-sensitive co-linear chaining

Co-linear chaining is a widely used technique in sequence alignment tools that follow seed-filter-extend methodology. It is a mathematically rigorous approach to combine short exact matches. For colinear chaining between two sequences, efficient subquadratic-time chaining algorithms are well-known for linear, concave and convex gap cost functions [Eppstein et al. JACM92]. However, developing extensions of chaining algorithms for directed acyclic graphs (DAGs) has been challenging. Recently, a new sparse dynamic programming framework was introduced that exploits small path cover of pangenome reference DAGs, and enables efficient chaining [Makinen et al. TALG19, RECOMB18]. However, the underlying problem formulation did not consider gap cost which makes chaining less effective in practice. To address this, we develop novel problem formulations and optimal chaining algorithms that support a variety of gap cost functions. We demonstrate empirically the ability of our provably-good chaining implementation to align long reads more precisely in comparison to existing aligners. For mapping simulated long reads from human genome to a pangenome DAG of 95 human haplotypes, we achieve 98.7% precision while leaving < 2% reads unmapped. Implementationhttps://github.com/at-cg/minichain

bioinformatics↗

bioRxiv2022

Coverage-preserving sparsification of overlap graphs for long-read assembly

Read-overlap-based graph data structures play a central role in computing de novo genome assembly using long reads. Many assembly tools use the string graph model [Myers, Bioinformatics 2005] to sparsify overlap graphs. Graph sparsification improves accuracy by removing spurious and redundant connections. However, a graph model must be coverage-preserving, i.e., it must ensure that each chromosome can be spelled as a walk in the graph, given sufficient sequencing coverage. This property becomes even more important for diploid genomes, polyploid genomes and metagenomes where there is a risk of losing haplotype-specific information. We develop a novel theoretical framework under which the coverage-preserving properties of a graph model can be analysed. We first prove that de Bruijn graph and overlap graph models are guaranteed to be coverage-preserving. We also show that the standard string graph model lacks this guarantee. The latter result is consistent with the observation made in [Hui et al. ISIT16] that removal of contained reads during string graph construction can lead to coverage gaps. To remedy this, we propose practical heuristics that are well-supported by our theoretical results to sparsify overlap graphs. In our experiments conducted by using simulated long reads from HG002 human diploid genome, we find that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets. We tested the proposed heuristics for deciding which contained reads should be retained to avoid the coverage gaps. The proposed method retains a small fraction of contained reads (1 - 2%) and closes majority of the coverage gaps.

bioinformatics↗

bioRxiv2021

Accelerating long-read analysis on modern CPUs

Long read sequencing is now routinely used at scale for genomics and transcriptomics applications. Mapping of long reads or a draft genome assembly to a reference sequence is often one of the most time consuming steps in these applications. Here, we present techniques to accelerate minimap2, a widely used software for mapping. We present multiple optimizations using SIMD parallelization, efficient cache utilization and a learned index data structure to accelerate its three main computational modules, i.e., seeding, chaining and pairwise sequence alignment. These result in reduction of end-to-end mapping time of minimap2 by up to 1.8 x while maintaining identical output.

genomics↗

bioRxiv2021

Chasing perfection: validation and polishing strategies for telomere-to-telomere genome assemblies

Advances in long-read sequencing technologies and genome assembly methods have enabled the recent completion of the first Telomere-to-Telomere (T2T) human genome assembly, which resolves complex segmental duplications and large tandem repeats, including centromeric satellite arrays in a complete hydatidiform mole (CHM13). Though derived from highly accurate sequencing, evaluation revealed that the initial T2T draft assembly had evidence of small errors and structural misassemblies. To correct these errors, we designed a novel repeat-aware polishing strategy that made accurate assembly corrections in large repeats without overcorrection, ultimately fixing 51% of the existing errors and improving the assembly QV to 73.9. By comparing our results to standard automated polishing tools, we outline common polishing errors and offer practical suggestions for genome projects with limited resources. We also show how sequencing biases in both PacBio HiFi and Oxford Nanopore Technologies reads cause signature assembly errors that can be corrected with a diverse panel of sequencing technologies

genomics↗

bioRxiv2021

The complete sequence of a human genome

In 2001, Celera Genomics and the International Human Genome Sequencing Consortium published their initial drafts of the human genome, which revolutionized the field of genomics. While these drafts and the updates that followed effectively covered the euchromatic fraction of the genome, the heterochromatin and many other complex regions were left unfinished or erroneous. Addressing this remaining 8% of the genome, the Telomere-to-Telomere (T2T) Consortium has finished the first truly complete 3.055 billion base pair (bp) sequence of a human genome, representing the largest improvement to the human reference genome since its initial release. The new T2T-CHM13 reference includes gapless assemblies for all 22 autosomes plus Chromosome X, corrects numerous errors, and introduces nearly 200 million bp of novel sequence containing 2,226 paralogous gene copies, 115 of which are predicted to be protein coding. The newly completed regions include all centromeric satellite arrays and the short arms of all five acrocentric chromosomes, unlocking these complex regions of the genome to variational and functional studies for the first time.

genomics↗

bioRxiv2021

A variant selection framework for genome graphs

MotivationVariation 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. ResultsIn 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{delta} differences. This framework leads to a rich set of problems based on the types of variants (SNPs, indels), 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{delta} 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,{delta} = 1000), 99.99% SNPs and 73% indel structural variants can be safely excluded from human chromosome 1 variation graph. The graph size reduction can benefit downstream pan-genome analysis. Implementationhttps://github.com/at-cg/VF Contactchirag@iisc.ac.in, neda.tavakoli@gatech.edu, aluru@cc.gatech.edu

bioinformatics↗

bioRxiv2021

Co-linear chaining with overlaps and gap costs

Co-linear chaining has proven to be a powerful heuristic for finding near-optimal alignments of long DNA sequences (e.g., long reads or a genome assembly) to a reference. It is used as an intermediate step in several alignment tools that employ a seed-chain-extend strategy. Despite this popularity, efficient subquadratic-time algorithms for the general case where chains support anchor overlaps and gap costs are not currently known. We present algorithms to solve the co-linear chaining problem with anchor overlaps and gap costs in O(n) time, where n denotes the count of anchors. We also establish the first theoretical connection between co-linear chaining cost and edit distance. Specifically, we prove that for a fixed set of anchors under a carefully designed chaining cost function, the optimal anchored edit distance equals the optimal co-linear chaining cost. Finally, we demonstrate experimentally that optimal co-linear chaining cost under the proposed cost function can be computed orders of magnitude faster than edit distance, and achieves correlation coefficient above 0.9 with edit distance for closely as well as distantly related sequences.

bioinformatics↗