bioinformatics tool developers

Abstract: The frontier of large language model (LLM) performance has advanced rapidly in recent years, fueled by scaling laws for pretraining on large text corpora. However, mainstream LLMs have fundamental limitations: they generate text autoregressively, producing outputs sequentially from left to right one token at a time. This sequential process leaves parallel GPU hardware underutilized during inference--a bottleneck that has grown acute as progress shifts toward scaling post-training and inference-time compute--and commits irreversibly to each token without the ability to revise earlier mistakes. Discrete diffusion models address these limitations by generating tokens in parallel, starting from a noisy or masked sequence and iteratively refining the entire output over a series of denoising steps. This parallel generative process enables speeds of thousands of tokens per second, provides a new axis of inference-time compute scaling, and supports built-in error correction and controllable generation. Over the past two years, discrete diffusion has scaled to billions of parameters across biological sequence modeling and natural language, with open-weights and commercial releases from leading labs. This article provides a survey of key ideas in discrete diffusion and a high-level introduction to how modern diffusion LLMs are built, covering their foundations, core algorithmic and architectural building blocks, applications in biology and language, and implications for future LLM scaling laws.

Abstract: A protein-protein interaction (PPI) network is a graph whose nodes are protein sequences and whose edges represent physical interactions between proteins. Correlated Motif Mining (CMM) seeks pairs of sequence motifs whose co-occurrence in interacting proteins reveals binding sites and interaction mechanisms. Formally, in the $(\ell,d)$-CMM problem, we are given a graph $G=(V,E)$, with $V\subseteqΣ^*$ for an alphabet $Σ$, and integers $0\leq d<\ell$, and we seek a pair $\{X,Y\}$ of motifs, each of length $\ell$ and containing $d$ wildcards, that maximizes a support measure $f(G,\{X,Y\})$; e.g., the count $f_E$ of edges $\{u,v\}\in E$ such that $X$ matches a substring of $u$ and $Y$ matches a substring of $v$, or vice versa. Although existing approaches have produced biologically meaningful results, they are either inefficient or heuristic-based, as the underlying optimization problem is NP-hard. Here, we revisit $(\ell,d)$-CMM. For $d=0$, we give an exact $\mathcal{O}(N^2)$-time and $\mathcal{O}(N)$-space algorithm, where $N$ is the total length of the node strings, and prove that this time is conditionally optimal under the Strong Exponential-Time Hypothesis. For any $d>0$, we give an exact $\mathcal{O}\!\left(\binom{\ell}{d}^2N^2\right)$-time and $\mathcal{O}(N)$-space algorithm, and observe that the problem is W[1]-hard parameterized by $d$. The latter algorithm improves the state of the art by exponentially large factors in both time and space. We further demonstrate experimentally that our algorithms are practical on real-world PPI networks and find significantly higher-scoring motif pairs than the state of the art. Moreover, we show that our algorithms find many top-scoring motif pairs that the state of the art misses entirely. Taken together, our results suggest that exact CMM with wildcards is more tractable in practice than previously assumed.

Abstract: We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary $k$-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.

Abstract: Let $λ$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω(λ^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω(λ^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.

Abstract: Computational methods and software are dispersed across a literature that is increasingly difficult to review manually, while curated registries capture only a subset of available resources. We present PaperAtlas, an automatically constructed atlas derived from the PubMed Central open-access corpus. Of 6,446,741 abstracts screened, 1,074,191 were classified as computational, with schema-valid records extracted for 1,074,140. Among these, 267,893 papers describing an algorithm, software package or web server formed 1,438 clusters, with 1,000 retained after restriction to parent-level biomedical categories. In 296 clusters linked to at least five bio.tools entries, the mean concentration of the most frequent EDAM topic was 61.7%, compared with 26.4% under permutation. Of 31,180 distinct software and web-server names, 61.0% lacked a strict match in bio.tools, PyPI, CRAN, Bioconductor or Bioconda. Among 12,207 bio.tools entries with defining papers in the corpus, 56.6% were recovered end to end, increasing to 83.6% among the 8,265 entries whose defining publication entered the atlas. PaperAtlas is fully open source and available as a web server at bhargavaresearch.org/paperatlas.

Abstract: Protein-protein interaction databases record evidence without weighing it. In BioGRID, an interaction asserted once by a single high-throughput screen and one confirmed by twenty laboratories across a dozen assays are the same kind of row in the same file. Tools built on such databases inherit that flattening: they draw every reported interaction as an edge, and the resulting picture states that two proteins interact without stating how much anyone should believe it. We present ProLiVis 2.0, a rewrite of the literature-centric visualization system of arXiv:2111.12794. It contributes three things. First, a citation-trust model that scores each interaction from seven terms, including a term for the number of independent laboratories behind the supporting publications, obtained by clustering those publications over shared institutional affiliations; a plain count of publications cannot distinguish five confirmations from one group publishing five times. Second, a deterministic reformulation of the center layout, closed-form and $O(n \log n)$, which replaces the force-directed placement of the original and makes published figures regenerable from a session manifest. Third, an implementation that runs entirely in a web browser, with an embedded analytical database, requiring no installation and uploading no data. On BioGRID release 5.0.260 restricted to SARS-CoV-2, 24,344 of 34,540 reported interactions (70%) rest on a single publication, and raising the trust threshold to 0.2 leaves 11,320 of them. That the large majority of a curated interaction network is unreplicated is a fact no existing view of the database makes visible.

Abstract: We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in $\mathcal B_7$-free tournaments in time $O(n^7)$, where $\mathcal B_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.