DNA-Encoded Libraries (DELs) represent a transformative technology in drug discovery, facilitating the high-throughput exploration of vast chemical spaces. Despite their potential, the scarcity of publicly available DEL datasets presents a bottleneck for the advancement of machine learning methodologies in this domain. To address this gap, we introduce KinDEL, one of the largest publicly accessible DEL datasets and the first one that includes binding poses from molecular docking experiments. Focused on two kinases, Mitogen-Activated Protein Kinase 14 (MAPK14) and Discoidin Domain Receptor Tyrosine Kinase 1 (DDR1), KinDEL includes 81 million compounds, offering a rich resource for computational exploration. Additionally, we provide comprehensive biophysical assay validation data, encompassing both on-DNA and off-DNA measurements, which we use to evaluate a suite of machine learning techniques, including novel structure-based probabilistic models. We hope that our benchmark, encompassing both 2D and 3D structures, will help advance the development of machine learning models for data-driven hit identification using DELs.

We define and investigate the Fréchet edit distance problem. Given two polygonal curves $π$ and $σ$ and a threshhold value $δ>0$, we seek the minimum number of edits to $σ$ such that the Fréchet distance between the edited $σ$ and $π$ is at most $δ$. For the edit operations we consider three cases, namely, deletion of vertices, insertion of vertices, or both. For this basic problem we consider a number of variants. Specifically, we provide polynomial time algorithms for both discrete and continuous Fréchet edit distance variants, as well as hardness results for weak Fréchet edit distance variants.

We describe a simple deterministic near-linear time approximation scheme for uncapacitated minimum cost flow in undirected graphs with real edge weights, a problem also known as transshipment. Specifically, our algorithm takes as input a (connected) undirected graph $G = (V, E)$, vertex demands $b \in \mathbb{R}^V$ such that $\sum_{v \in V} b(v) = 0$, positive edge costs $c \in \mathbb{R}_{>0}^E$, and a parameter $\varepsilon > 0$. In $O(\varepsilon^{-2} m \log^{O(1)} n)$ time, it returns a flow $f$ such that the net flow out of each vertex is equal to the vertex's demand and the cost of the flow is within a $(1 + \varepsilon)$ factor of optimal. Our algorithm is combinatorial and has no running time dependency on the demands or edge costs. With the exception of a recent result presented at STOC 2022 for polynomially bounded edge weights, all almost- and near-linear time approximation schemes for transshipment relied on randomization to embed the problem instance into low-dimensional space. Our algorithm instead deterministically approximates the cost of routing decisions that would be made if the input were subject to a random tree embedding. To avoid computing the $Ω(n^2)$ vertex-vertex distances that an approximation of this kind suggests, we also take advantage of the clustering method used in the well-known Thorup-Zwick distance oracle.

In this paper we introduce and formally study the problem of k -clustering with faulty centers. Specifically, we study the faulty versions of k -center, k -median, and k -means clustering, where centers have some probability of not existing, as opposed to prior work where clients had some probability of not existing. For all three problems we provide fixed parameter tractable algorithms, in the parameters k , d , and ε , that ( 1 + ε ) -approximate the minimum expected cost solutions for points in d dimensional Euclidean space . For Faulty k -center we additionally provide a 5-approximation for general metrics. Significantly, all of our algorithms have only a linear dependence on n .

Given a set of points $P=\left(P^{+} \sqcup P^{-}\right) \subset \mathbb{R}^{d}$ for some constant d and a supply function $\mu: P \rightarrow \mathbb{R}$ such that $\mu(p)\gt$ $0 \forall p \in P^{+}, \mu(p)\lt 0 \forall p \in P^{-}$, and $\sum_{p \in P} \mu(p)=0$, the geometric transportation problem asks one to find a transportation map $\tau: P^{+} \times P^{-} \rightarrow \mathbb{R}_{\geq 0}$ such that $\sum_{q \in P^{-}} \tau(p, q)=\mu(p) \forall p \in P^{+}$, $\sum_{p \in P^{+}} \tau(p, q)=-\mu(q) \forall q \in P^{-}$, and the weighted sum of Euclidean distances for the pairs $\sum_{(p, q) \in P^{+} \times P^{-}} \tau(p, q) \cdot\|q-p\|_{2}$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $(1+\varepsilon)$ factor of optimal. More precisely, our algorithm runs in $O\left(n \varepsilon^{-(d+2)} \log ^{5} n \log \log n\right)$ time for any constant $\varepsilon>0$. While a randomized $n \varepsilon^{-O(d)} \log ^{O(d)} n$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $(1+\varepsilon)$-approximation algorithms run in $\Omega\left(n^{3 / 2}\right)$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $n \varepsilon^{-O(d)} \log ^{O(d)} n$ time $(1+\varepsilon)$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $(1+\varepsilon)$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $(1+\varepsilon)$-approximate deterministic algorithm for geometric bipartite matching and the first $(1+\varepsilon)$ approximate deterministic or randomized algorithm for geometric transportation with no dependence on d in the exponent of the running time’s polylog. As an additional application of our main ideas, we also give the first randomized near-linear $O\left(\varepsilon^{-2} m \log ^{O(1)} n\right)$ time $(1+\varepsilon)$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary real edge costs.