Papers for

bioinformatics analysts

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Selective inference method improves trust in spectral clustering results

Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation

Abstract: Cluster labels are often used twice: first to discover groups, and then to test whether the discovered groups differ. This double use of the data makes ordinary two-sample $p$-values anti-conservative. Selective inference fixes this by conditioning on the clustering event, but for spectral clustering the event appears difficult because the algorithm combines an affinity map, an eigendecomposition, and a rounding step. We show that, for spectral clustering based on unweighted $\varepsilon$- or $k$-nearest-neighbor graphs, the obstruction is the affinity construction rather than the eigendecomposition. Along the one-dimensional perturbation used by the truncated-$χ$ selective test, graph changes occur only at finitely many real roots of data-dependent quadratic distance comparisons. Between these breakpoints, the graph, Laplacian spectrum, embedding, rounding, and reported cluster pair are deterministic functions of a finite graph state. Consequently, in real arithmetic and under a known-scale spherical Gaussian model, the selection set is an exact finite union of intervals, yielding finite-sample selective $p$-values for selected spectral-cluster pairs. The same argument gives feature-wise truncated-normal tests. We also record direct extensions to known feature covariance, eigengap-selected $K$, and auxiliary-coordinate graphs. We validate null and partial-null calibration, operational power, numerical sensitivity, and model-scope diagnostics, and give a working-model PBMC algorithmic illustration. Smooth kernels such as RBF affinities fall outside the finite-state guarantee.

Tue 3 NovMachine Learning
The gist
When people group data into clusters, they often use the same data to both find the clusters and test if the groups are really different. This can make the usual tests for differences unreliable. The authors present a new way to make these tests accurate for a popular method called spectral clustering. They analyze how the data and clustering relate and create exact tests that only work when using certain types of graphs. Their method helps people trust the significance of their clustered groups better.
Open → 2611.04995v1

Estimating nodes and paths in directed acyclic graphs by random walks

Estimating the number of nodes and paths in a DAG by following a random path

Abstract: We investigate a simple method to compute an unbiased estimate of the number of nodes of a directed acyclic graph (DAG) by following a random directed path. This method is due to Leonard Pitt from 1987, and it generalizes a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation makes it possible to estimate the number of source-sink paths. We extend the algorithm to use many "agents" that walk cooperatively through the graph. This extension unifies and generalizes several methods that have been proposed for approximately counting the nodes of a tree.

Wed 28 OctData Structures and Algorithms
The gist
Counting all the points and routes in a network that flows in one direction without loops can be very hard. The authors talk about an old simple way to estimate the number of points by following a random route from start to end. They also tweak this method to estimate how many paths exist between starting and ending points. They improve the method by having many walkers work together, making the estimate better and connecting several past approaches into one.
Open → 2610.38586v1

Faster solutions for path intersection problems in tree graphs

Solving problems in RDV Graphs faster and easier

Abstract: In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., $O(m+n)$) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for example it is possible to find a minimum dominating set in an interval graph in $O(n)$ time. We study RDV graphs, a generalization of interval graphs, namely, the intersection graphs of directed paths in a rooted tree. It was known that the above three problems can be solved in $O(n\log n)$ time if a suitably small representation is given. In this paper, we reduce the runtime to $O(n)$. Furthermore, while the previous results used non-trivial operations such as range-minimum queries and ray-shooting queries, we need nothing more complicated than lists and (for Matching) a Union-Find data structure.

Tue 20 OctData Structures and Algorithms
The gist
Some computer problems that involve matching and grouping items can be solved quickly on simple graphs. This paper looks at a more complex kind of graph formed by directed paths in trees, called RDV graphs. The authors find ways to solve these problems even faster, improving the speed from something that took longer (n log n steps) to something closer to the fastest possible (just n steps). They also simplify the techniques required to do this, using basic data structures instead of complicated ones.
Open → 2610.28932v1

Algorithms for comparing and counting jumbled scattered word patterns

Jumbled Simon's Equivalence and Embeddings

Abstract: \emph{Jumbled scattered factors} are a generalisation of scattered factors (or subsequences) where a jumbled scattered factor is obtained from another word by deleting and rearranging letters. For limiting the number of rearrangements, we distinguish $\ell$-jumbled scattered factors where $\ell$ limits the number of letters that may occur rearranged. For instance, $\mathtt{car}$, $\mathtt{start}$, $\mathtt{rat}, \mathtt{cat}$ are jumbled scattered factors of $\mathtt{abstract}$ even though $\mathtt{car}$, $\mathtt{start}$ and $\mathtt{cat}$ are no scattered factors and each need one jumble. An example for a jumbled scattered factor with $2$ jumbles is $\mathtt{tatar}$. In this work, we investigate two problems on jumbled scattered factors from an algorithmic perspective. First, we give algorithms for testing jumbled Simon's equivalence where two words are equivalent if they share the same $\ell$-jumbled scattered factors up to length $k$. Second, we investigate how to count the possible occurrences of a jumbled scattered factor -- the jumbled binomial coefficient. After defining the jumbled binomial coefficient, we study jumbled embeddings and factorisations of such as well.

Tue 13 OctFormal Languages and Automata TheoryData Structures and Algorithms
The gist
Sometimes, parts of words can appear in a jumbled or rearranged way inside other words, not just as exact subsequences. The authors study how to tell when two words have the same jumbled scattered parts up to a certain size, and how to count the number of times these jumbled parts occur. They introduce new ways to measure and find these jumbled patterns algorithmically, which helps understand and work with complex word structures.
Open → 2610.17910v1

Practical workflow helps non-programmers use published ai models easily

PRAISE: A Reproducible Workflow for Non-Programmer Scientists to Implement Published AI Models

Abstract: Artificial Intelligence (AI) models are increasingly developed, published and used across scientific fields. Researchers, students and industry professionals who want to apply these models to their own research questions often lack the programming and data science expertise to do so. Existing guidelines cover single steps, but not the route from a published model to working predictions on one's own data. Here we present the hands-on workflow PRAISE, a Practical, Reproducible AI-model Implementation for Science and Education, that helps non-programmers implement published AI models step by step. Because implementations rarely work the first time, PRAISE anticipates common failures and provides a fallback route for each. As a proof of principle, three BSc chemistry students and their tutor applied PRAISE without prior programming or data science knowledge. They reproduced, validated and extended a state-of-the-art model that predicts enzyme-substrate interactions. This shows that with PRAISE, implementing an AI model from the literature becomes a learnable skill, one that turns non-programmer scientists from users into evaluators and improvers of AI models.

Mon 12 OctArtificial IntelligenceMachine Learning
The gist
Many scientists want to use AI models published in research but don't know how to program or handle data properly. The authors created PRAISE, a step-by-step guide that helps beginners implement these AI models even without coding skills. PRAISE also plans for common problems and tells users how to fix them. They tested this with chemistry students who were able to reproduce and improve a complex AI model about enzymes, showing this method really works.
Open → 2610.16980v1

Unison framework improves learning from scored item groups

UNISON: A Unified Framework for Learning from Scored Bags

Abstract: We introduce UNISON, a unified framework that bridges multiple instance learning and recommendation systems by treating both as instances of learning from scored bag collections of (item, score) pairs. Unlike traditional approaches that address bag-level classification and personalized recommendation as separate problems, UNISON decomposes learning into three interconnected stages: (1) learning universal item representations, (2) modeling bag-specific preference patterns through lightweight personalized parameters, and (3) inferring bag-level characteristics from learned preferences. We justify the architectural choice of linear bag-specific scoring through a first-order analysis: when item embeddings are sufficiently smooth in the score, a linear function approximates the score up to a Taylor remainder controlled by the curvature of the underlying preference function. For cold-start scenarios, we show that the cold-bag fitting problem reduces to ridge-less linear regression with a closed-form solution, and provide convergence guarantees for the iterative variant. Empirically, UNISON matches or outperforms state-of-the-art approaches across diverse domains: entertainment (books, movies), immunology (T cell receptor (TCR) based classification), and microbiome, offering superior computational efficiency and interpretability. A controlled synthetic experiment further confirms that the bag-specific parameters ($w_j, b_j$) recover the latent factors that drive item scores even when the projection $φ$ has no access to the original scoring mechanism (AUC > 0.998). UNISON is available at https://github.com/louzounlab/UNISON.

Sun 11 OctMachine Learning
The gist
Some tasks involve learning from collections of items that each have a score, such as recommending products or classifying groups in biology. This paper presents UNISON, a single approach that handles these tasks by learning item features, personalizing preferences for each group, and then predicting group-level outcomes. The authors show this method works well across different fields and is efficient and interpretable. They also prove theoretical properties that support its design and show it deals effectively with new, unseen groups.
Open → 2610.15564v1

One-step flows enable fast generation of categorical data

ReSFlow: Rectifying Categorical Flows on Statistical Manifolds for One-Step Generation

Abstract: Generative modeling for discrete data has been significantly advanced by learning continuous vector fields on the statistical manifolds to transport simple priors to target discrete distributions. However, because these continuous-time flows are not constrained to follow geodesics on the statistical manifold, thereby requiring multi-step numerical integration for simulation and leading to substantial computational costs during inference. In this work, drawing inspiration from the "straight and fast" properties of Rectified Flow in continuous Euclidean space, we propose the Rectified Statistical Flow (ReSFlow) model, which enables one-step categorical generation on statistical manifolds by explicitly learning geodesic trajectories that adhere to the intrinsic Riemannian geometry. By rectifying the flow on the statistical manifold, we theoretically guarantee that trajectories between prior and target distributions approximate geodesics. This rectification significantly reduces the transport cost by aligning the learned trajectories directly along geodesics on the statistical manifold, allowing the model to map pure noise to target discrete data in a single step. Through extensive experiments on diverse real-world generative tasks, ranging from image and text to biological domains, we demonstrate ReSFlow's superior one-step generation quality, which truly embodies geodesically optimal and rapid categorical generation. Our code is available at https://github.com/xiaohuanjia/ReSFlow.

Fri 9 OctMachine LearningArtificial Intelligence
The gist
Generating complex categorical data like text or images often requires many slow, gradual steps. The authors propose a new method called ReSFlow that learns the most direct paths—called geodesics—between simple starting points and target data on a special curved space of probabilities. This lets the model create realistic discrete data in just one step, making the process much faster and computationally cheaper. Their tests on various tasks show ReSFlow produces high-quality results quickly.
Open → 2610.13225v1

High-dimensional inference improves feature selection in sparse support vector machines

High-Dimensional Statistical Inference for Sparse Support Vector Machines

Abstract: Using a replica-symmetric high-dimensional characterization, we develop an inferential framework for sparse support vector machines when the sample size and number of features grow proportionally. The main challenge is the nonsmooth hinge loss, which prevents direct application of debiasing arguments developed for smooth classification losses. We overcome this difficulty by representing the $L_1$-penalized support vector machine (SVM) as a linear program and identifying the hinge-loss subgradient through its dual variables. This yields a computationally accessible debiased estimator whose coordinates are asymptotically Gaussian under the proportional asymptotic regime. The resulting distributional characterization provides confidence intervals and hypothesis tests for individual features and enables false-discovery-rate-controlled variable selection. Extensive simulations examine calibration, power, and variable-selection performance under a range of covariance structures, including strongly correlated designs. An analysis of high-dimensional breast cancer gene-expression data illustrates how the proposed inference can distinguish statistically significant features from variables selected by the original sparse SVM.

Tue 6 OctMachine Learning
The gist
When trying to find important features in data using support vector machines (SVMs), it can be hard to know how reliable those features are, especially when there are many features compared to samples. The authors developed a new method that makes it possible to get statistically justified confidence intervals and tests for each feature even with many features. They overcame difficulties caused by the specific methods SVMs use by turning the problem into an easier one and then analyzing it carefully. This helps in deciding which features truly matter rather than just appearing important due to how the model was trained.
Open → 2610.08345v1

Local fisher information improves sparse causal network discovery

Local Fisher Information Enables Sparse Causal Discovery

Abstract: Sparse causal discovery calls for methods that exploit graph structure without estimating high-dimensional densities. We introduce Fisher Information Completion Search (FiCS), a source-first algorithm for additive noise models that uses one local Fisher score for both ordering and parent selection. Under regularity and nonconstant-parent conditions, we prove that a node's local Fisher information equals the noise Fisher information exactly when the conditioning set contains all parents, provided that it contains no descendants. This Fisher parent completion identifies the parent set as the unique minimal Fisher completion. With a maximum conditioning set size $q$ at least the maximum indegree $d$, population FiCS queries marginals of at most $q+1$ variables and recovers the true directed acyclic graph under a positive ordering margin. Bounded conditioning also has a population advantage: reducing $q$ toward $d$ cannot decrease, and can strictly increase, the ordering margin. A growing non-Gaussian family separates local Fisher selection from conditional-variance and leaf-first Fisher ordering. For the regularized kernel Stein estimator, we establish high-dimensional DAG consistency under $q\{1+\log(p/q)\}+\log p=o(n)$, uniform Fisher separation, local approximation, and compatible ridge and parent penalty parameters. Experiments show the strongest gains when $n$ is small relative to $p$, quantify the effect of the conditioning size, and demonstrate competitive reference-graph recovery on three real-data benchmarks.

Sat 3 OctMachine Learning
The gist
Finding cause-and-effect relationships in complex data can be very hard, especially when there are many variables involved. The authors present a new method that uses a mathematical tool called local Fisher information to better identify these connections without needing to understand complex probability patterns. Their approach can find the true cause-effect structure more reliably, especially when sample size is not very large compared to the number of variables. They tested their method on real-world data and found it performed well compared to other techniques.
Open → 2610.04291v1

Online methods match growing tree data despite uncertain growth patterns

Robust and Learned Online Matching in Growing Trees

Abstract: We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret $O(\sqrt{n}\log^2 n)$, using $O(n^2\log n)$ arithmetic operations and $O(n)$ stored entries. The exact minimax rate remains open.

Wed 30 SeptData Structures and AlgorithmsMachine Learning
The gist
Matching pairs in a growing tree structure is a common challenge when new parts get added over time, like leaves to a tree. The authors study how to make good pairing decisions online, even when the rules about how the tree grows are partly wrong or unknown. They develop threshold rules that adapt based on partial information and prove these rules only lose a small amount compared to an ideal method that knows the exact growth. They also provide a way to update their method over time and bound how much the uncertainty affects performance.
Open → 2609.40077v1

Fast neural method matches labeled graphs for molecular similarity

Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

Abstract: Maximum common edge subgraph (MCES) matching finds a partial vertex correspondence between two labeled graphs that preserves as many labeled edges as possible. Molecular similarity search requires matching many graph pairs, making the cost of repeated queries important. The strongest baseline attains accurate MCES solutions but trains a separate network for each pair. We introduce Equivariant Neural Primal-Dual Assignment (ENPDA), which learns a shared matching policy and applies it to new pairs without further training, answering queries roughly three orders of magnitude faster and recovering its training cost after a few dozen queries. The policy recomputes exact objective marginals for candidate matches and learns corrections and step sizes that update their scores. Target prices respond to competition when several source vertices favor the same target. Four update rounds and a Hungarian projection produce a partial one-to-one matching. We prove per-pair guarantees that hold for any network parameters. In exact arithmetic, reordering either graph permutes the assignment and price states, the projected matching is one-to-one, and repaired prices give a valid MCES upper bound. Subtracting the preserved-edge count bounds the optimality gap; combined with structural caps, these certificates prove global optimality for 60 of 291 native test pairs. On three molecular benchmarks with disjoint train/validation/test splits, ENPDA improves over an analytic counterpart with the same update and projection budget by 7.4-8.6 accuracy points; after one second of refinement search, 2.5-3 points of the gain remain. Transferred without fine-tuning to edge-deletion tasks from social and protein graphs, the policy gains 9.1-17.6 points over the analytic counterpart. When output matchings must keep aromatic rings intact, ENPDA recovers more reference bonds than the baselines on all three datasets.

Sat 26 SeptMachine Learning
The gist
Matching parts of two complex networks to find shared connections is helpful, especially in chemistry where molecules look like graphs. The authors developed a neural network approach that learns from many graph pairs to quickly find good matches without retraining each time. This method is much faster than previous ones and can even confirm when its solutions are optimal. It works well on different datasets, including molecules and social or protein networks, and respects special rules like preserving ring structures in molecules.
Open → 2609.32661v1

SeqMaestro enables easy interpretable machine learning on DNA sequences

SeqMaestro: From nucleotide sequences to biological hypotheses through interpretable machine learning

Abstract: Nucleotide sequence analysis is central to problems spanning regulatory genomics, evolutionary biology, and phenotype prediction. Classical bioinformatics methods extract interpretable sequence properties such as motifs and k-mer composition, but their flexibility is limited. In contrast, modern deep learning models can learn powerful predictive representations directly from raw sequences, yet their internal representations and decision mechanisms are difficult to inspect. Interpretable machine learning methods (e.g., sparse linear models and decision trees) provide human-understandable representations of predictive relationships but are not designed to operate directly on nucleotide sequences. Here, we introduce SeqMaestro, a machine learning framework that proposes biological hypotheses from nucleotide sequences using interpretable models. Our solution is centered around a two-layer interface that connects nucleotide sequences with the broader ecosystem of interpretable machine learning. SeqMaestro uses this interface to fit diverse combinations of interpretable models, feature representations, and extraction strategies, leveraging variability across transparent models to identify robust biological signals and richer predictive relationships than feature importance alone can provide. The system also supports data transformation and cleaning, model fitting, hyperparameter tuning, reliability analysis, and synthesis of results into a contextualized written report. By providing these capabilities through a no-code workflow, SeqMaestro is designed to make interpretable sequence analysis accessible to researchers without requiring extensive programming or machine learning expertise. SeqMaestro thereby provides an accessible route from nucleotide sequences to biological hypotheses.

Mon 14 SeptMachine LearningArtificial Intelligence
The gist
Understanding DNA sequences helps scientists learn about biology and health. The challenge is that advanced computer models can be very accurate but hard to understand. The authors created SeqMaestro, a tool that uses simple and transparent machine learning methods directly on DNA sequences. It helps users without much coding experience find meaningful biological clues and generates easy-to-read reports. This makes it simpler to turn genetic data into useful biological ideas.
Open → 2609.14882v1