Group-Invariant Certificates and Solvers for Diversity Selection in Combinatorial Libraries
- 1Independent researcher
Abstract
Selection of massive, mutually non-redundant subset of highly scoring compounds from a combinatorial library is a standardized design in early stage drug discovery. It is usually solved by heuristics that return a ranking of capable candidates, however there is no quality guarantee. We formulate and introduce a method as maximum weighted independent set with a parameter soft redundancy penalty on a Cayley graph over the abelian group β€π, πβwhere π is the number of substitution positions and π the number of substituents per position. The formulation rests on one explicit and falsifiable modelling commitment: pairwise redundancy should depend only on the group difference of two compounds. Under this commitment the interactionmatrix is diagonalised by the group characters, its spectrum is available in closed form via Krawtchouk polynomials, and classical coding-theoretic bounds (Hoffman ratio, Delsarte linear programming) apply verbatim to the unweighted problem. Our contribution is an interface rather than new bound technology: we derive two valid upper bounds for the weighted objective, report the resulting a posteriori approximation-ratio lower bound πlower = π(π)/π , and introduce a coset-decomposition family of certificates that recouples the weight term with the combinatorial structure. On synthetic libraries the spectral certificate yields a mean quality floor of 59.3%, the Delsarte version 67.7%, and the coset family a further 3.3 points. A gap decomposition against exhaustively computed optima shows that 77% of the residual gap is bound looseness rather than solver suboptimality, which redirects effort to the certificate side. On the solver side, group invariance permits column generation inπ(π)without ever materialising the π Γ π matrix, and evaluation of all π translates of a linear code by a single group Fourier transform inπ(π logπ); exhaustive enumeration of cyclic codes combined with this step doubles the quality floor relative to a lookahead greedy at π = 8192 while running four times faster. We report three negative results that we believe are useful to record: PΓ³lya-based budget allocation is significantly worse than uniform allocation (π‘ = β4.65), non-coordinate conjugacy classes of index-2 subgroups are systematically looser, and orbit-level selection never wins. All experiments use synthetic libraries; no chemical validation is claimed.
Related
- Exploring the Potential of on-DNA Phthalimide Deprotection for DNA-encoded Libraries
- DNA Directed Chemistry: Scalable Programmed DNA-Encoded Library Synthesis for More Chemically Diverse and Drug-Like Libraries
- On-resin Heck coupling enables small-molecule ligand discovery with covalent peptide-encoded libraries
- DEL-GPT: learning the language of DNA-encoded libraries to design focused screening collections
- AI-enhanced adaptive virtual screening of large libraries for ligand discovery
BibTeX
@misc{yao2026groupinvariant,
title = {{Group-Invariant Certificates and Solvers for Diversity Selection in Combinatorial Libraries}},
author = {Anni Yao and yao anni},
howpublished = {ChemRxiv},
year = {2026},
month = sep,
doi = {10.26434/chemrxiv.15009197/v1},
url = {https://chemrxiv.org/doi/full/10.26434/chemrxiv.15009197/v1},
note = {CC BY},
}
RIS
TY - UNPB
TI - Group-Invariant Certificates and Solvers for Diversity Selection in Combinatorial Libraries
AU - Anni Yao
AU - yao anni
PY - 2026
DA - 2026/09/21
PB - ChemRxiv
DO - 10.26434/chemrxiv.15009197/v1
UR - https://chemrxiv.org/doi/full/10.26434/chemrxiv.15009197/v1
AB - Selection of massive, mutually non-redundant subset of highly scoring compounds from a combinatorial library is a standardized design in early stage drug discovery. It is usually solved by heuristics that return a ranking of capable candidates, however there is no quality guarantee. We formulate and introduce a method as maximum weighted independent set with a parameter soft redundancy penalty on a Cayley graph over the abelian group β€π, πβwhere π is the number of substitution positions and π the number of substituents per position. The formulation rests on one explicit and falsifiable modelling commitment: pairwise redundancy should depend only on the group difference of two compounds. Under this commitment the interactionmatrix is diagonalised by the group characters, its spectrum is available in closed form via Krawtchouk polynomials, and classical coding-theoretic bounds (Hoffman ratio, Delsarte linear programming) apply verbatim to the unweighted problem. Our contribution is an interface rather than new bound technology: we derive two valid upper bounds for the weighted objective, report the resulting a posteriori approximation-ratio lower bound πlower = π(π)/π , and introduce a coset-decomposition family of certificates that recouples the weight term with the combinatorial structure. On synthetic libraries the spectral certificate yields a mean quality floor of 59.3%, the Delsarte version 67.7%, and the coset family a further 3.3 points. A gap decomposition against exhaustively computed optima shows that 77% of the residual gap is bound looseness rather than solver suboptimality, which redirects effort to the certificate side. On the solver side, group invariance permits column generation inπ(π)without ever materialising the π Γ π matrix, and evaluation of all π translates of a linear code by a single group Fourier transform inπ(π logπ); exhaustive enumeration of cyclic codes combined with this step doubles the quality floor relative to a lookahead greedy at π = 8192 while running four times faster. We report three negative results that we believe are useful to record: PΓ³lya-based budget allocation is significantly worse than uniform allocation (π‘ = β4.65), non-coordinate conjugacy classes of index-2 subgroups are systematically looser, and orbit-level selection never wins. All experiments use synthetic libraries; no chemical validation is claimed.
ER -