bioRxiv Science⌕ Search

Biology subjects

Kingsford, C.

Publications and source records attributed to Kingsford, C..

At least 19 recordsLinked to original sources

CodonRL: Multi-Objective Codon Sequence Optimization Using Demonstration-Guided Reinforcement Learning

Optimizing synonymous codon sequences to improve translation efficiency, RNA stability, and compositional properties is challenging because the search space grows exponentially with protein length and objectives interact through long range RNA structure. Dynamic programming-based methods can provide strong solutions for fixed objective combinations but are difficult to extend to additional constraints. Deep generative models require large-scale, high-quality mRNA sequence datasets for training, limiting applicability when such data are scarce. Reinforcement learning naturally handles sequential decision-making but faces challenges in codon optimization due to delayed rewards, large action spaces, and expensive structural evaluation. We present CodonRL, a reinforcement learning framework that learns a structural prior for mRNA design from efficient folding feedback and demonstration-guided replay, and then enables user-controlled multi-objective trade-offs during inference. CodonRL uses LinearFold for fast intermediate reward computation during training and ViennaRNA for final evaluation, warms up learning with expert sequences to accelerate convergence for global structure objectives, and introduces milestone-based intermediate rewards to address delayed feedback in long range optimization. On a benchmark of 55 human proteins, CodonRL outperforms GEMORNA, a state-of-the-art codon optimization method, across multiple metrics, achieving 9.5% higher codon adaptation index (CAI), 25.4 kcal/mol more favorable minimum free energy (MFE), and 3.4% lower uridine content on average, while improving codon stabilization coefficient (CSC) in over 90% of benchmark proteins under matched constraints. These gains translate into designs that are predicted to be more efficiently translated, more structurally stable, and less immunogenic, while supporting continuous objective reweighting at inference time.

bioinformatics↗

seq2ribo: Structure-aware integration of machine learning and simulation to predict ribosome location profiles from RNA sequences

MotivationRibosome dynamics are vital in the process of protein expression. Current methods rely on ribosome profiling (Ribo-seq), RNA-seq profiles, and full genomic context. This restricts their use in de novo sequence design, like messenger RNA (mRNA) vaccines. Simulation-only approaches like the Totally Asymmetric Simple Exclusion Process (TASEP) oversimplify translation by focusing solely on codon elongation times. ResultsWe present seq2ribo, a hybrid simulation and machine learning framework that predicts ribosome A-site locations using only an mRNA sequence as input. Our method first employs a novel structure-aware TASEP (sTASEP), which models translation using a comprehensive set of fitted parameters that include codon wait times and structural features, such as local angles, base-pairing, and discrete positional buckets. The ribosome locations generated by sTASEP are then processed by a polisher model, which learns to refine the simulated ribosome distributions. seq2ribo provides high-fidelity predictions of ribosome locations across diverse cell types (iPSC, HEK293, LCL, and RPE-1), significantly outperforming baselines. seq2ribo is the first method to achieve meaningful positional correlation with observed ribosome profiles from sequence alone, reaching transcript-level Pearson correlations up to 0.920 and withintranscript shape correlations up to 0.186, where all baselines yield near-zero values on these metrics. seq2ribo also reduces elementwise error by up to 37.7% relative to the sequence-only Translatomer baseline. By adding a task-specific head, seq2ribo achieves Pearson correlations up to 0.732 with experimental translation efficiency (TE) across several cell lines, and up to 0.903 with measured protein expression. By operating from sequence alone, seq2ribo provides a new tool for synthetic biology, enabling the rational design and optimization of mRNA sequences without the need for expression-level data or genomic context. Availabilityseq2ribo is available at https://github.com/Kingsford-Group/seq2ribo. Contactgkaynar@cs.cmu.edu, carlk@cs.cmu.edu. Supplementary informationSupplementary data are available.

bioinformatics↗

ARCADE: Controllable Codon Design from Foundation Models via Activation Engineering

Codon sequence design is crucial for generating mRNA sequences with desired functional properties for tasks such as developing mRNA vaccines or gene editing therapies. Yet existing methods lack flexibility and controllability to adapt to various design objectives. We propose a novel machine learning-based framework, ARCADE, that enables flexible and controllable multi-objective codon design. Leveraging inherent knowledge from pretrained genomic language models, ARCADE extends activation engineering, a technique originally developed for controllable text generation, beyond discrete feature manipulation such as concepts and styles, to steering continuous-valued biological metrics. Specifically, we derive biologically meaningful semantic steering vectors in the models activation space, which directly control properties such as the Codon Adaptation Index, Minimum Free Energy, and GC content. Experimental results demonstrate the flexibility of ARCADE in designing codon sequences with multiple objectives, underscoring its potential for advancing programmable biological sequence design. Our implementation is available at https://github.com/Kingsford-Group/arcade.

bioinformatics↗

DTMol: Pocket-based Molecular Docking using Diffusion Transformers

In computational chemistry, molecular docking--predicting the binding structure of a small molecule ligand to a protein--is vital for understanding interactions between small molecules and their protein targets, with broad applications in drug discovery (Morris and Lim-Wilby, 2008). Traditional docking methods rely on energy-based scoring functions and optimization algorithms to identify ligand-binding structures. However, these methods are often slow and inaccurate due to the extensive search space for binding structures and the complexity of scoring function landscapes (Corso et al., 2023). Deep learning techniques have emerged as promising alternatives for molecular docking. These methods harness the power of neural networks to understand the complex interactions between protein pockets and ligands from large datasets. They can be classified into two categories: regression-based methods (Stark et al., 2022; Lu et al., 2022), which offer greater computational efficiency compared to traditional docking methods but have yet to offer substantial improvements in accuracy (Corso et al., 2023); and generative models, particularly diffusion models (Corso et al., 2023; Qiao et al., 2024; Nakata et al., 2023; Lu et al., 2024; Schneuing et al., 2024), which lead to significant accuracy improvements compared to regression-based methods. Most diffusion-based docking methods aim to address the blind docking problem, where the ligand is docked without prior knowledge of the specific protein pocket--a site of the protein with potential ligand-binding capabilities--and only the overall protein structure is provided (Yim et al., 2024). However, in many drug discovery cases, specific pockets have already been identified (Zheng et al., 2013), meaning that the docking process only needs to determine how the ligand binds to the pocket. This defines the pocket-based docking problem. Pocket-based docking leverages the physical and chemical information of protein side chains around the pocket, significantly reducing the search space for ligand binding structures and improving the understanding of atomic-level interactions. Additionally, focusing on the local protein substructure rather than the global structure enhances computational efficiency, which allows for the use of more complex neural architectures. We introduce DTMol, a novel diffusion model designed to tackle the pocket-based docking problem. Our model integrates a pretrained molecular representation framework with a diffusion transformer architecture. The advantages of this design are twofold: first, the molecular representation models we employ are pretrained on separate datasets of small molecules and protein pockets, which are larger than the datasets of ligand-pocket interactions. Consequently, these pretrained models encode typical structural features of both elements, enhancing our models ability to represent them and predict binding structures. Second, the transformer architecture used in our diffusion model is more capable of effectively capturing all-atom interactions between the pocket and the ligand. We test our method on the docking benchmark PDBBind v2020 and PoseBuster, and compare it with other methods. DTMol achieves 77.65% top-1 success rate (RMSD {inverted exclamation} 2[A]) on PoseBuster, outperforms the second-best docking software Gnina (65.65%) We also test the performance of our method on a real-world virtual screening task using Janus kinase 2 (PDB ID: 6BBV) as the target protein. A TR-FRET screening experiment is performed on the union of top ligands identified via physics-based docking and the diffusion model, in order to measure their inhibitory activity against the JAK2 protein. The results shows that our model achieved the only positive rank correlation score compared to other traditional docking methods and machine learning-based methods. To summarize, the main contributions of this work are: - We introduce DTMol, a novel diffusion model designed to address the pocket-based docking problem. This model represents the first application of the diffusion transformer architecture in solving pocket-based molecular docking. - We propose a novel SE(3)-equivariant transformer architecture with an SE(3)-invariant and a parallel SE(3)-equivariant flow, which is straightforward to implement and train while achieving excellent performance. - We achieve new state-of-the-art results on both the PDBBind and PoseBuster pocket-based docking benchmarks, obtaining top-1 prediction rates of 45.05% and 77.65%, respectively, at RMSD < 2[A]. - Doing virtual screening on Janus kinase 2, DTMol is able to achieve the only positive rank score; and identifies 2 new experimentally effective JAK2 inhibitors.

bioinformatics↗

A Scalable Optimization Algorithm for Solving the Beltway and Turnpike Problems with Uncertain Measurements

The BO_SCPLOWELTWAYC_SCPLOW and TO_SCPLOWURNPIKEC_SCPLOW problems entail the reconstruction of circular and linear one-dimensional point sets from unordered pairwise distances. These problems arise in computational biology when the measurements provide distances but do not associate those distances with the entities that gave rise to them. Such applications include molecular structure determination, genomic sequencing, tandem mass spectrometry, and molecular error-correcting codes (since sequencing and mass spec technologies can give lengths or weights, usually without connecting them to endpoints). Practical algorithms for TO_SCPLOWURNPIKC_SCPLOWe are known when the distance measurements are accurate, but both problems become strongly NP-hard under any level of measurement uncertainty. This is problematic since all known applications experience some degree of uncertainty from uncontrollable factors. Traditional algorithms cope with this complexity by exploring a much larger solution space, leading to exponential blowup in terms of both time and space. To alleviate both issues, we propose a novel alternating optimization algorithm that can scale to large, uncertain distance sets with as many as 100,000 points. This algorithm is space and time-efficient, with each step running in O(m log(m)) time and requiring only [Formula] working space for a distance set of size m. Evaluations of this approach on synthetic and partial digest data showcase improved accuracy and scalability in the presence of uncertain, duplicated, and missing distances. Our implementation of the algorithm is available at https://github.com/Kingsford-Group/turnpikesolvermm.

bioinformatics↗

Adaptive, sample-specific parameter selection for more accurate transcript assembly

We introduce AutoTuneX, a data-driven, AI system designed to automatically predict optimal parameters for transcript assemblers -- tools for reconstructing expressed transcripts from the reads in a given RNA-seq sample. AutoTuneX is built by learning parameter knowledge from existing RNA-seq samples and transferring this knowledge to unseen samples. On 1588 human RNA-seq samples tested with two transcript assemblers, AutoTuneX predicts parameters that resulted in 98% of samples achieving more accurate transcript assembly compared to using default parameter settings, with some samples experiencing up to a 600% improvement in AUC. AutoTuneX offers a new strategy for automatically optimizing use of sequence analysis tools.

bioinformatics↗

k-nonical space: sketching with reverse complements

Sequences equivalent to their reverse complements (i.e., double-stranded DNA) have no analogue in text analysis and non-biological string algorithms. Despite this striking difference, algorithms designed for computational biology (e.g., sketching algorithms) are designed and tested in the same way as classical string algorithms. Then, as a post-processing step, these algorithms are adapted to work with genomic sequences by folding a k-mer and its reverse complement into a single sequence: the canonical representation (k-nonical space). The effect of using the canonical representation with sketching methods is understudied and not understood. As a first step, we use context-free sketching methods to illustrate the potentially detrimental effects of using canonical k-mers with string algorithms not designed to accommodate for them. In particular, we show that large stretches of the genome ("sketching deserts") are undersampled or entirely skipped by context-free sketching methods, effectively making these genomic regions invisible to subsequent algorithms using these sketches. We provide empirical data showing these effects and develop a theoretical framework explaining the appearance of sketching deserts. Finally, we propose two schemes to accommodate for these effects: (1) a new procedure that adapts existing sketching methods to k-nonical space and (2) an optimization procedure to directly design new sketching methods for k-nonical space. The code used in this analysis is freely available at https://github.com/Kingsford-Group/mdsscope.

bioinformatics↗

Detecting m6A RNA modification from nanopore sequencing using a semi-supervised learning framework

Direct nanopore-based RNA sequencing can be used to detect post-transcriptional base modifications, such as m6A methylation, based on the electric current signals produced by the distinct chemical structures of modified bases. A key challenge is the scarcity of adequate training data with known methylation modifications. We present Xron, a hybrid encoder-decoder framework that delivers a direct methylation-distinguishing basecaller by training on synthetic RNA data and immunoprecipitation-based experimental data in two steps. First, we generate data with more diverse modification combinations through in silico cross-linking. Second, we use this dataset to train an end-to-end neural network basecaller followed by fine-tuning on immunoprecipitation-based experimental data with label-smoothing. The trained neural network basecaller outperforms existing methylation detection methods on both read-level and site-level prediction scores. Xron is a standalone, end-to-end m6A-distinguishing basecaller capable of detecting methylated bases directly from raw sequencing signals, enabling de novo methylome assembly.

bioinformatics↗

Improving Hi-C contact matrices using genome graphs

Three-dimensional chromosome structure plays an important role in fundamental genomic functions. Hi-C, a high-throughput, sequencing-based technique, has drastically expanded our comprehension of 3D chromosome structures. The first step of Hi-C analysis pipeline involves mapping sequencing reads from Hi-C to linear reference genomes. However, the linear reference genome does not incorporate genetic variation information, which can lead to incorrect read alignments, especially when analyzing samples with substantial genomic differences from the reference such as cancer samples. Using genome graphs as the reference facilitates more accurate mapping of reads, however, new algorithms are required for inferring linear genomes from Hi-C reads mapped on genome graphs and constructing corresponding Hi-C contact matrices, which is a prerequisite for the subsequent steps of the Hi-C analysis such as identifying topologically associated domains and calling chromatin loops. We introduce the problem of genome sequence inference from Hi-C data mediated by genome graphs. We formalize this problem, show the hardness of solving this problem, and introduce a novel heuristic algorithm specifically tailored to this problem. We provide a theoretical analysis to evaluate the efficacy of our algorithm. Finally, our empirical experiments indicate that the linear genomes inferred from our method lead to the creation of improved Hi-C contact matrices. These enhanced matrices show a reduction in erroneous patterns caused by structural variations and are more effective in accurately capturing the structures of topologically associated domains.

genomics↗

Masked Minimizers: Unifying sequence sketching methods

Minimizers and syncmers are sequence sketching methods that extract representative substrings from a long sequence. We show that both these sampling rules are different instantiations of a new unifying concept we call masked minimizers, which applies a sub-sampling binary mask on a minimizer sketch. This unification leads to the first formal procedure to meaningfully compare minimizers, syncmers and other comparable masked minimizers. We further demonstrate that existing sequence sketching metrics, such as density (which measures the sketch sparseness) and conservation (which measures the likelihood of the sketch being preserved under random mutations), should not be independently measured when evaluating masked minimizers. We propose a new metric that reflects the trade-off between these quantities called the generalized sketch score, or GSS. Finally, we introduce a sequence-specific and gradient-based learning objective that efficiently optimizes masked minimizer schemes with respect to the proposed GSS metric. We show that our method finds sketches with better overall density and conservation compared to existing expected and sequence-specific approaches, enabling more efficient and robust genomic analyses in the many settings where minimizers and syncmers are used.

genomics↗

The Effect of Genome Graph Expressiveness on the Discrepancy Between Genome Graph Distance and String Set Distance

MotivationIntra-sample heterogeneity describes the phenomenon where a genomic sample contains a diverse set of genomic sequences. In practice, the true string sets in a sample are often unknown due to limitations in sequencing technology. In order to compare heterogeneous samples, genome graphs can be used to represent such sets of strings. However, a genome graph is generally able to represent a string set universe that contains multiple sets of strings in addition to the true string set. This difference between genome graphs and string sets is not well characterized. As a result, a distance metric between genome graphs may not match the distance between true string sets. ResultsWe extend a genome graph distance metric, Graph Traversal Edit Distance (GTED) proposed by Ebrahimpour Boroojeny et al., to FGTED to model the distance between heterogeneous string sets and show that GTED and FGTED always underestimate the Earth Movers Edit Distance (EMED) between string sets. We introduce the notion of string set universe diameter of a genome graph. Using the diameter, we are able to upper-bound the deviation of FGTED from EMED and to improve FGTED so that it reduces the average error in empirically estimating the similarity between true string sets. On simulated TCR sequences and Hepatitis B virus genomes, we show that the diameter-corrected FGTED reduces the average deviation of the estimated distance from the true string set distances by more than 250%. AvailabilityData and source code for reproducing the experiments are available at: https://github.com/Kingsford-Group/gtedemedtest/ Contactcarlk@cs.cmu.edu

bioinformatics↗

DeepMinimizer: A Differentiable Framework for Optimizing Sequence-Specific Minimizer Schemes

Minimizers are k-mer sampling schemes designed to generate sketches for large sequences that preserve sufficiently long matches between sequences. Despite their widespread application, learning an effective minimizer scheme with optimal sketch size is still an open question. Most work in this direction focuses on designing schemes that work well on expectation over random sequences, which have limited applicability to many practical tools. On the other hand, several methods have been proposed to construct minimizer schemes for a specific target sequence. These methods, however, require greedy approximations to solve an intractable discrete optimization problem on the permutation space of k-mer orderings. To address this challenge, we propose: (a) a reformulation of the combinatorial solution space using a deep neural network re-parameterization; and (b) a fully differentiable approximation of the discrete objective. We demonstrate that our framework, DO_SCPLOWEEPC_SCPLOWMO_SCPLOWINIMIZERC_SCPLOW, discovers minimizer schemes that significantly outperform state-of-the-art constructions on genomic sequences.

bioinformatics↗

Constructing smaller genome graphs via string compression

The size of a genome graph -- the space required to store the nodes, their labels and edges -- affects the efficiency of operations performed on it. For example, the time complexity to align a sequence to a graph without a graph index depends on the total number of characters in the node labels and the number of edges in the graph. The size of the graph also affects the size of the graph index that is used to speed up the alignment. This raises the need for approaches to construct space-efficient genome graphs. We point out similarities in the string encoding approaches of genome graphs and the external pointer macro (EPM) compression model. Supported by these similarities, we present a pair of linear-time algorithms that transform between genome graphs and EPM-compressed forms. We show that the algorithms result in an upper bound on the size of the genome graph constructed based on an optimal EPM compression. In addition to the transformation, we show that equivalent choices made by EPM compression algorithms may result in different sizes of genome graphs. To further optimize the size of the genome graph, we purpose the source assignment problem that optimizes over the equivalent choices during compression and introduce an ILP formulation that solves that problem optimally. As a proof-of-concept, we introduce RLZ-Graph, a genome graph constructed based on the relative Lempel-Ziv EPM compression algorithm. We show that using RLZ-Graph, across all human chromosomes, we are able to reduce the disk space to store a genome graph on average by 40.7% compared to colored de Bruijn graphs constructed by Bifrost under the default settings. The RLZ-Graph software is available at https://github.com/Kingsford-Group/rlzgraph

bioinformatics↗

Practical selection of representative sets of RNA-seq samples using a hierarchical approach

Despite numerous RNA-seq samples available at large databases, most RNA-seq analysis tools are evaluated on a limited number of RNA-seq samples. This drives a need for methods to select a representative subset from all available RNA-seq samples to facilitate comprehensive, unbiased evaluation of bioinformatics tools. In sequence-based approaches for representative set selection (e.g. a k-mer counting approach that selects a subset based on k-mer similarities between RNA-seq samples), because of the huge number of available RNA-seq samples and the large number of k-mers/sequences in each sample, computing the full similarity matrix between all samples using k-mers/sequences for the entire set of RNA-seq samples in a large database (e.g. the SRA) has memory and runtime challenges, making direct representative set selection infeasible with limited computing resources. Therefore, we developed a novel computational method called "hierarchical representative set selection" to handle this challenge. Hierarchical representative set selection is a divide-and-conquer-like algorithm that breaks the representative set selection into sub-selections and hierarchically selects representative samples through multiple levels. We demonstrate that hierarchical representative set selection can achieve performance close to that of direct representative set selection, while largely reducing the runtime and memory requirements of computing the full similarity matrix (up to 8.4X runtime reduction and 4.7X memory reduction for 10000 samples that could be practically run with direct subset selection). We show that hierarchical representative set selection substantially outperforms random sampling on the entire SRA set of RNA-seq samples, making it a practical solution to representative set selection on large databases such as the SRA.

bioinformatics↗

Sequence-specific minimizers via polar sets

Minimizers are efficient methods to sample k-mers from genomic sequences that unconditionally preserve sufficiently long matches between sequences. Well-established methods to construct efficient minimizers focus on sampling fewer k-mers on a random sequence and use universal hitting sets (sets of k-mers that appear frequently enough) to upper bound the sketch size. In contrast, the problem of sequence-specific minimizers, which is to construct efficient minimizers to sample fewer k-mers on a specific sequence such as the reference genome, is less studied. Currently, the theoretical understanding of this problem is lacking, and existing methods do not specialize well to sketch specific sequences. We propose the concept of polar sets, complementary to the existing idea of universal hitting sets. Polar sets are k-mer sets that are spread out enough on the reference, and provably specialize well to specific sequences. Link energy measures how well spread out a polar set is, and with it, the sketch size can be bounded from above and below in a theoretically sound way. This allows for direct optimization of sketch size. We propose efficient heuristics to construct polar sets, and via experiments on the human reference genome, show their practical superiority in designing efficient sequence-specific minimizers. A reference implementation and code for analyses under an open-source license are at https://github.com/kingsford-group/polarset.

bioinformatics↗

Accounting for fragments of unexpectedorigin improves transcript quantification inRNA-seq simulations focused on increased realism

Transcript and gene quantification is the first step in many RNA-seq analyses. While many factors and properties of experimental RNA-seq data likely contribute to differences in accuracy between various approaches to quantification, it has been demonstrated (1) that quantification accuracy generally benefits from considering, during alignment, potential genomic origins for sequenced fragments that reside outside of the annotated transcriptome. Recently, Varabyou et al. (2) demonstrated that the presence of transcriptional noise leads to systematic errors in the ability of tools -- particularly annotation-based ones -- to accurately estimate transcript expression. Here, we confirm the findings of Varabyou et al. (2) using the simulation framework they have provided. Using the same data, we also examine the methodology of Srivastava et al.(1) as implemented in recent versions of salmon (3), and show that it substantially enhances the accuracy of annotation-based transcript quantification in these data.

bioinformatics↗

Capturing the complexity of topologically associating domains through multi-feature optimization

The three-dimensional structure of human chromosomes is tied to gene regulation and replication timing, but there is still a lack of consensus on the computational and biological definitions for chromosomal substructures such as topologically associating domains (TADs). TADs are described and identified by various computational properties leading to different TAD sets with varying compatibility with biological properties such as boundary occupancy of structural proteins. We unify many of these computational and biological targets into one algorithmic framework that jointly maximizes several computational TAD definitions and optimizes TAD selection for a quantifiable biological property. Using this framework, we explore the variability of TAD sets optimized for six different desirable properties of TAD sets: high occupancy of CTCF, RAD21, and H3K36me3 at boundaries, reproducibility between replicates, high intra- vs inter-TAD difference in contact frequencies, and many CTCF binding sites at boundaries. The compatibility of these biological targets varies by cell type, and our results suggest that these properties are better reflected as subpopulations or families of TADs rather than a singular TAD set fitting all TAD definitions and properties. We explore the properties that produce similar TAD sets (reproducibility and inter- vs intra-TAD difference, for example) and those that lead to very different TADs (such as CTCF binding sites and inter- vs intra-TAD contact frequency difference).

genomics↗

Probabilistic method corrects previously uncharacterized Hi-C artifact

Three-dimensional chromosomal structure plays an important role in gene regulation. Chromosome conformation capture techniques, especially the high-throughput, sequencing-based technique Hi-C, provide new insights on spatial architectures of chromosomes. However, Hi-C data contains artifacts and systemic biases that substantially influence subsequent analysis. Computational models have been developed to address these biases explicitly, however, it is difficult to enumerate and eliminate all the biases in models. Other models are designed to correct biases implicitly, but they will also be invalid in some situations such as copy number variations. We characterize a new kind of artifact in Hi-C data. We find that this artifact is caused by incorrect alignment of Hi-C reads against approximate repeat regions and can lead to erroneous chromatin contact signals. The artifact cannot be corrected by current Hi-C correction methods. We design a probabilistic method and develop a new Hi-C processing pipeline by integrating our probabilistic method with the HiC-Pro pipeline. We find that the new pipeline can remove this new artifact effectively, while preserving important features of the original Hi-C matrices.

bioinformatics↗