bioinformatics software developers

Abstract: Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$. We show how to compute it in $O(n+r\log r)$ time, using only $O(r)$ words of space, where $r$ denotes the number of runs in the Burrows-Wheeler transform.

Abstract: Spatial transcriptomics (ST) enables joint characterization of tissue morphology and gene expression. However, 3D volumetric ST acquisition remains expensive. AI-driven methods offer a low-cost alternative but remain limited in accuracy, while recent 2D section-wise ST acquisition still rely on dense grid sampling, resulting in redundant measurements and undersampling of biologically informative regions. To bridge the gap, we propose STRATA, a reinforcement-driven active sampling framework with tri-paradigm adaptation for reconstructing dense 3D transcriptomic maps from sparse voxel-wise ST acquisition. STRATA constructs a 3D graph integrating H&E morphology with single-cell priors and employs a reinforcement learning agent to estimate morphological sparsity and transcriptomic informativeness, enabling budget-aware selection of informative spots. Given these sparse measurements, an adaptive tri-paradigm predictor combines retrieval, regression, and cross-layer imputation through lightweight fusion, dynamically weighting their contributions. Experiments across datasets demonstrate improved sampling efficiency and accuracy, particularly under low-budget settings. Code is available at https://github.com/Junchao-Zhu/STRATA.

Abstract: We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

Abstract: Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones.These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We give generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements in the sample count and training length trade off. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.

Abstract: Machine learning models are increasingly used for automated feature extraction from weakly annotated bioimaging data, such as microscopy and cytomorphology images. Due to the sole dependency of automated feature extraction, existing methods yield inconsistent classification performance across weakly annotated datasets. Here, we propose a model-agnostic knowledge augmentation method that enables ML models to exploit domain knowledge beyond what automated feature extraction can capture. The proposed approach improves classification performance across seven ML architectures. When integrated with masked autoencoder-based self-supervised learning, our method achieves the strongest overall performance, improving precision by 2.9% over the next-best method on three in-house microscopy datasets and by an average of 6.8% across three public cytomorphology benchmarks. We perform nucleus-level classification based on mislocalization of TAR DNA-binding protein 43 (TDP-43) from the nucleus to the cytoplasm, a phenotype linked to Amyotrophic Lateral Sclerosis (ALS), using three independent microscopy datasets of motor neurons derived from human induced pluripotent stem cells. Accurate quantification of this phenotype at scale remains challenging and may contribute to inconsistencies across studies. Application of the best-performing model to these microscopy datasets reveals biological interpretations related to ALS, including dose-dependent effects of the proteasomal stressor, MG132, and the oxidative stressor, sodium arsenite (SA), on TDP-43 mislocalization, variable pathology in motor neurons from sporadic and familial ALS donors, and a lack of protection of the pharmacological compounds, edaravone and niclosamide, against SA-induced TDP-43 mislocalization. Together, our pipeline enables in-vitro cellular image analysis to advance understanding of ALS-associated pathology and potential treatments.

Abstract: Single-cell snapshot data can resolve a continuum of cellular states but do not uniquely determine the dynamics governing transitions between them. However, additional dynamical information can often be encoded in a cell-cell Markov transition kernel. Existing generative approaches for single cell trajectory inference either infer transport only from population marginals, impose a symmetric geometry on the state space, or incorporate directionality through a single velocity vector at each observed state. We introduce Finsler Flow Matching (FFM), a framework for learning continuous stochastic dynamics from discrete Markov transition graphs. We use the first and second local moments to construct a Finsler structure motivated by the Freidlin--Wentzell action, where the second moment determines anisotropic accessibility and the first moment introduces a preferred direction of motion. We learn neural approximations of the resulting directed geodesics, use their Finsler cost to construct source-target couplings, and define geometry-aware stochastic conditional paths that can be distilled into a continuous generative process through simulation-free score and flow matching. Across synthetic and single-cell trajectory inference benchmarks, FFM improves recovery of withheld intermediate populations, particularly when the transition dynamics are strongly directional or anisotropic. Our results provide a principled route from discrete transition probabilities to continuous generative dynamics while retaining both directional and diffusive structure.

Abstract: Single-cell trajectory inference maps transcriptomic measurements onto developmental continua, yet configurations that fit the data equally well can assign conflicting cell fates. FateMultiplicity is a label-free framework that constructs a statistically admissible model set, or Rashomon set, without lineage labels, by evaluating model discrepancy on cross-fitted held-out genes under non-inferiority testing calibrated against random-seed variation. Multiplicity is large and depends more on the diversity of the model space than its size: twelve configurations of a second algorithm expose 20.0% of cells where twenty-four of the first expose 3.8%. Whether the per-cell certified fate margin FM yields more reliable assignments than the fitted model already provides is then tested, and it does not. On simulation ground truth, on the same cells, FM discriminates misassignment at AUC 0.682, against 0.965 for the baseline configuration's own decision margin (p = 0.003) and 0.854 for a seed-dispersion baseline. Informativeness is governed by the breadth of the admitted set, not its cardinality: at cardinality four, seed refits give 0.933 and hyperparameter-perturbed sets 0.701. Relaxing the infimum to a q-quantile recovers discrimination but converges toward the single model's own confidence; the supremum reaches 0.973 because theta*'s membership bounds it from below, while the infimum is unanchored. Multiplicity in trajectory inference is worth measuring and reporting, but per-cell certification over a label-free Rashomon set is not a route to more reliable fate calls. Two constructions survive: a margin-erosion ratio separates real from spurious branch points in simulation (AUC 0.890, untested on real data), and against clonally observed fate, uncertified cells disagree with their clone's outcome 16.4 percentage points more often than certified cells (p < 0.001).

Abstract: Background: Protein language models (PLMs) are increasingly used for sequence generation and property prediction, but their size makes fine-tuning and deployment expensive. The effects of quantization and parameter efficient fine-tuning on performance, representations and generation remain insufficiently characterized. Results: We evaluated 4-bit quantization and low-rank adapter fine-tuning (QLoRA) across ESM-2, ESMC, ProtBERT, ProtT5, Ankh, Ankh3 and Profluent-E1. Across protein prediction tasks, many model-task pairs retained more than 90% of full fine-tuning performance. Peak GPU memory savings approached 90% for the largest models, although performance and efficiency varied by model, dataset and training configuration. QLoRA often preserved early-layer representations while inducing task-specific adaptations in middle and late layers, resembling full fine-tuning with smaller representational changes. Training speed and power effects were more varied. For unconditional generation with ProLLaMA, ProtGPT2, ProGen2, ProteinGLM and ESM3, 4-bit quantization largely preserved predicted structural and sequence-level properties, but token-level analysis revealed model-dependent shifts in autoregressive output distributions. Conclusion: QLoRA and 4-bit quantization reduce PLM computational requirements, particularly GPU memory usage. Our results support QLoRA as a first-pass strategy for memory limited adaptation, reserving full fine-tuning for challenging tasks, unstable architectures or low validation recovery. For generative PLMs, sequence-level and structural metrics should be complemented with distributional analysis, since downstream predictions alone may miss quantization-induced shifts. These approaches can broaden access to large-scale protein modelling while requiring model- and task-specific validation.

Abstract: Predicting transcriptional responses to unseen compounds is limited by fragmented chemical coverage and heterogeneous experimental platforms and gene panels. To assess molecular generalization across these settings, we build on Chem-PerturBridge to benchmark eight datasets with 16,771 compounds, withholding test compounds from every training dataset. This comparison reveals that high overall response agreement can coexist with weak prediction of drug-specific differences, despite reproducible signals across repeated measurements. To exploit complementary chemical supervision while targeting these differences, we introduce Bison: a shared gene representation connects native panels, while two discrete diffusion models compose context-dependent responses with molecular deviations learned through matched drug-contrast supervision. A single Bison model jointly trained across all eight datasets achieves the highest mean overall-response and drug-contrast Pearson correlations on the full benchmark in comparison with 11 methods trained independently per dataset. Compared with dataset-specific training of the same architecture, joint training increases mean drug-contrast correlation by 27.4\%, with gains across all eight datasets and improvements in overall response prediction. These results demonstrate how matched drug contrasts turn complementary screens into shared molecular supervision for unseen-drug response prediction while preserving native gene measurements.

Abstract: Many deep learning approaches to RNA secondary structure prediction have recently been proposed. They typically output a weight matrix $W$ where $W_{ij}$ is an arbitrary weight for base $i$ pairing with base $j$. Converting this matrix to a predicted secondary structure or base-pairing probability matrix typically involves ad hoc and problematic downstream algorithms. Despite the importance of this conversion step, which we refer to as structure extraction, it has received relatively little attention in the literature. In this work, we analyze how the congruence between training and extraction methods affects prediction performance. To do this, we compare four extraction algorithms: a Nussinov-like dynamic programming method, maximum-weight graph matching and the greedy extraction algorithms used by SPOT-RNA and RiNALMo. These are evaluated on outputs from the pretrained RiNALMo model and three toy models trained in this paper: a differentiable Nussinov-like model, a binary cross-entropy (BCE) baseline, and a model that incorporates a novel symmetric doubly stochastic matrix (SDSM) normalization algorithm during training which allows it to output base-pairing probability matrices directly, without a separate extraction step. This SDSM normalization algorithm is differentiable and can be added inline to any deep learning model during training and evaluation. We find that the performance of each extraction method depends strongly on how the corresponding model was trained. Considering the toy models themselves, the SDSM model showed the strongest overall performance: it outperformed the BCE baseline under all four extraction algorithms and produced pre-extraction outputs closest to the ground truth. These results suggest that SDSM normalization is a tractable alternative to traditional structure extraction.

Abstract: Spatial biologists use visualization to assess computational analyses of tissue data. We examine how they direct and verify analyses when an AI agent performs this work. We synthesized workflows from fourteen contextual inquiries and conducted a formative pilot followed by an observational study with ten spatial biologists using Claude Science on their own data. Participants valued help with plotting, locating cells of interest, and tasks they found laborious or could not otherwise perform. Assessing the agent's work involved obtaining suitable evidence, sometimes through additional work in external tools, and interpreting it using knowledge of the tissue and its markers. Scientists also sought information about ongoing computation to decide how analysis should proceed. We contribute a workflow synthesis, an empirical account of scientists directing and verifying agentic analyses, and four design directions addressing execution control, familiar interactive views, source and execution information, and accessible verification across computing setups and experience.

Abstract: An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.

Abstract: A cell's identity depends on where it sits in tissue: for example, a macrophage behaves differently in a tumor core than at its edge. Spatial transcriptomics has transformed how we study this by recovering that lost coordinate, but it does so by producing data that is simultaneously high-dimensional, multimodal, and uncertain. Visualizing this combination is a hard problem in its own right, and one that warrants an assessment of how the field currently represents it, what has worked, and what is still missing. We surveyed 148 papers and 1,824 figure panels using a What-Why-How coding framework grounded in Munzner's nested model, connecting the data represented, the biological tasks motivating each visualization, and the design choices through which they are expressed; a subset of the surveyed work also contributed dedicated interactive visualization software that was not necessarily reflected in the static figures, and we looked at what interaction capabilities those tools supported as well. We close by outlining where the field stands and the challenges ahead for bioinformatics and visualization researchers to tackle together.

Abstract: Biomedical knowledge graphs combine ontology-derived hierarchies with transversal associations among heterogeneous entities such as phenotypes, diseases, genes, proteins, and patients. This hybrid structure raises the question of whether hyperbolic embeddings, which naturally capture tree-like organization, remain useful beyond purely hierarchical graphs. We present a preliminary study of hyperbolic graph representation learning for Mendelian-disease differential diagnosis on a patient-integrated biomedical graph. Experiments on isolated ontology subgraphs show that hyperbolic models achieve strong performance in substantially lower dimensions than Euclidean baselines. We then evaluate the models on a link-prediction task that ranks candidate diseases for each patient. Results suggest that hyperbolic embeddings can exploit biomedical hierarchical structure while supporting diagnostic reasoning over heterogeneous patient-level graphs.

Abstract: In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the \emph{translocation operation} is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as \emph{contiguous} if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as \emph{non-contiguous}. If the exchanged prefixes are of equal length, the translocation is called \emph{uniform}. Otherwise, the translocation is termed \emph{non-uniform}. The \emph{translocation distance} between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.

Abstract: Prefix-free parsing provides an efficient way to construct compressed representations of large and repetitive pangenomes and naturally induces a graph representation known as a prefix-free graph. In this work, we initiate a theoretical study of the problem of constructing prefix-free graphs of minimum size, where the size accounts for both the total length of distinct segment labels and the paths representing the input sequences. We show that selecting an optimal set of trigger words is NP-hard, already when triggers consist of single characters. Using a synchronized-code reduction, we extend this hardness result to every fixed trigger length and further show that the problem remains NP-hard over an alphabet of size three. We then establish a structural connection between prefix-free graphs and de Bruijn graphs. In particular, we show that every compacted de Bruijn graph can be realized as a prefix-free graph and derive a hierarchy relating the sizes of minimum pangenomic graphs, minimum prefix-free graphs, compacted de Bruijn graphs, and de Bruijn graphs. Finally, we give an exact fixed-parameter algorithm running in $O(2^q n)$ time, where $q$ is the number of distinct candidate trigger words and $n$ is the total pangenome length. Our results characterize both the computational limitations and the structural properties of optimizing prefix-free graph representations and provide a theoretical foundation for the design of compact graph representations of repetitive pangenomic data.

Abstract: Hyperbolic geometry provides a natural inductive bias for genomic representation learning, but existing hyperbolic genomic models primarily use Lorentz convolutions to learn local sequence representations, while their residual pathways do not directly aggregate full Lorentz representations. We propose HyCoSeq, a contextual hyperbolic representation learning framework for genomic sequences. HyCoSeq incorporates weighted Lorentzian residual aggregation into multi-curvature Lorentz encoding, allowing full Lorentz representations to participate directly in geometry-consistent local aggregation. It further introduces a bidirectional long short-term memory network that integrates information from both sequence directions to learn contextual relationships among local representations at different positions within a genomic sequence, thereby extending local hyperbolic convolutional encoding to sequence-level contextualized representations. Extensive experiments across diverse genomic tasks show that HyCoSeq outperforms existing hyperbolic baselines and, without large-scale genomic pretraining, achieves competitive performance against substantially larger pretrained DNA language models.

Abstract: Pangenomics uses graphs to show genetic differences within or between species. In these graphs, a path can represent one genome, while regions with different paths show genetic variation. Biedged graphs use black edges for sequences and grey edges for links between them. Snarls are minimal subgraphs of a biedged graph that are separated from the rest of the graph by removing two black edges. Ultrabubbles are minimal acyclic and tip-free snarls and thus are important variant structures because they have finite paths and lack dead ends. In our previous work, we showed that in linear time every bidirected graph can be transformed to a rooted biedged bipartite one, and that in these graphs, ultrabubbles can be enumerated with a lowest common ancestor (LCA)-based method in $O(Kn)$ time, where $n$ and $K$ are the number of nodes and given snarls, respectively, of the graph. Here, we present a series of practical and theoretical improvements to our previous LCA-based approach. First, we present a hybrid method that selects between the LCA-based method and the naive approach for evaluating a snarl, depending on the size of the snarl in relation to the number of tips and cycle-closing nodes in the graph. Second, by using the theoretical framework from our previous paper, we show that all ultrabubbles can be found in $O(n + m + K)$ time, where $m$ is the number of edges, by traversing the breadth-first search (BFS) tree of the biedged bipartite graph. Third, we show that any two snarls that are candidate ultrabubbles and share a frontier node cannot be ultrabubbles; the resulting set of snarls is compatible, bound by $n$, and defines exclusive families of nested snarls. We combine these three results into six methods and present benchmarking results that illustrate how the above improvements affect practical run-times for identifying ultrabubbles.

Abstract: The evolution of DNA sequences can be viewed as stochastic dynamics on a high-dimensional discrete space, but it is unclear when empirical transition biases reduce to an effective energy landscape versus retain irreducible non-equilibrium circulation. Human context-dependent mutation probabilities offer a direct test: every single-nucleotide substitution in a local context has a reverse substitution, so the logarithm of the forward-to-reverse probability ratio defines an antisymmetric field-the human mutation field. We show this field has a dominant gradient component and a smaller but reproducible curl component. Using seven-base human germline substitution probabilities, we infer an effective mutational landscape with a Siamese neural network constrained to predict only energy differences. This model predicts forward-to-reverse log-ratios for held-out mutations with a correlation of about 0.93, close to both an unconstrained predictive reference (0.948) and the empirical reversible ceiling from Hodge projection (about 0.96). Although trained only on mutation probabilities, the inferred landscape largely recovers short-word genomic composition and Chargaff reverse-complement symmetry for sequences up to length four. Deviations from equilibrium structure reveal a small but detectable nonequilibrium component: a residual irreversible circulation violating the Kolmogorov cycle condition for detailed balance, reproducible across African, Asian, and European populations, and strongest in CpG-linked cycles and CpG-transition edges, consistent with methylcytosine deamination. These results give a thermodynamic decomposition of the human mutation field: most mutation bias is organized by a local equilibrium-like energy landscape aligned with genome composition, while the residual circulation points to specific directional mutational mechanisms.