Sparse Identification for Automatic Large-Scale Screening: A Constraint-Aware Framework with Ultra Fast Decoding Algorithm

Jianing Li; Li Chai; Yingcheng Lai

stat.MLSep 18, 2026

Sparse Identification for Automatic Large-Scale Screening: A Constraint-Aware Framework with Ultra Fast Decoding Algorithm

Authors: Jianing Li, Li Chai, Yingcheng Lai

Organizations: College of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China

Abstract

In the early stages of a pandemic, identification of a small number of infected individuals through large-scale screening is critical for pandemic control, yet remains challenging under limited reagents and testing capacity. Existing group testing methods suffer from either high computational complexity or low identification accuracy. Even worse, no available methods provide theoretically rigorous analysis for sparse identification with hard constraints caused by the sample usage constraint and the dilution effect existing ubiquitously in practical applications. In this article, we propose the Logic Screening method (LoSc), an ultra fast, accurate, and theoretically grounded framework for large-scale screening. LoSc introduces a novel decoding algorithm with a very simple selection strategy, achieving identification of all positives with only O(klogn) pooled tests. The decoding relies only on logical operations, enabling direct hardware implementation and yielding ultra fast computational implementation. Moreover, LoSc explicitly incorporates dilution and sample usage constraints into pooling designs, and establishes theoretical guarantees to guide optimal pooling configurations. Extensive simulations confirm the superior effectiveness, efficiency, and scalability. We believe LoSc offers a fast and reliable solution for automatic large-scale screening.

Figures & tables

Fig. 1 : Overview of Logic Screening method. Samples are assigned to pools according to a specific pooling design. In the first stage, samples appearing in negative pools are declared as negative. Then, compute the frequency of occurrence in positive pools for the remaining samples. Finally, select top $k$ or $2k$ samples as the estimated set.

Panel of Figure 2 — Fig. 2 : Overview of pooling designs with different constraints. (a) Dilution-constrained design. The pool size is strictly limited to mitigate dilution effects. The corresponding pooling matrix $\Phi$ has exactly $P_{r}$ nonzero entries per row. (b) Sample-constrained design. Sample usage is restricted to prevent exhaustion. The corresponding pooling matrix $\Phi$ has at most $P_{c}$ nonzero entries per column.

Fig. 3 : Schematic diagram and Verilog code of the decoding algorithm.

Fig. 4 : Recovery performance of LoSc under optimal pooling designs. Recovery success rate as a function of $m$ under three pooling designs, each evaluated at its optimal setup. For $n=5000$ and $k=10$ , the optimal pooling parameters are $p=0.0625$ , $P_{r}=312$ and $P_{c}=19$ . For $n=10000$ , $k=20$ , the optimal pooling parameters are $p=0.0312$ , $P_{r}=312$ and $P_{c}=19$ . Insets present minimum number of pooled tests required for a $99\%$ success rate.

	$n=5000$ , $k=10$							$n=10000$ , $k=20$
	Unconstrained		Dilution-Constrained		Sample-Constrained			Unconstrained		Dilution-Constrained		Sample-Constrained
$m$	Top-k	Top-2k	Top-k	Top-2k	Top-k	Top-2k	$m$	Top-k	Top-2k	Top-k	Top-2k	Top-k	Top-2k
162	$4.0\%$	$73.5\%$	$2.5\%$	$74.0\%$	$7.0\%$	$90.5\%$	300	0	$26.0\%$	0	$26.5\%$	0	$58.0\%$
189	$18.0\%$	$99.0\%$	$22.5\%$	$98.0\%$	$55.0\%$	$100.0\%$	360	$0.5\%$	$93.0\%$	0	$90.0\%$	$9.5\%$	$99.0\%$
216	$50.0\%$	$100.0\%$	$54.5\%$	$99.5\%$	$82.5\%$	$99.5\%$	420	$9.5\%$	$99.5\%$	$8.0\%$	$99.5\%$	$54.0\%$	$99.0\%$
243	$71.5\%$	$100.0\%$	$79.5\%$	$99.5\%$	$94.5\%$	$100.0\%$	480	$36.0\%$	$99.5\%$	$42.0\%$	$99.5\%$	$92.5\%$	$99.0\%$

TABLE I : Recovery success rate of LoSc under optimal pooling designs

Panel of Figure 6 — Fig. 5 : Performance comparison of constrained and unconstrained designs. Recovery success rate versus the number of pooled tests $m$ for $n=5000$ under (a) dilution-constrained and (b) sample-constrained settings. Three pooling designs are compared: the unconstrained design, the constrained design, and the unconstrained design with imposed constraints. Insets present minimum number of pooled tests required for a $99\%$ success rate.

Panel of Figure 7 — Fig. 6 : Comparison of decoding algorithms. (a) Minimum number of pooled tests required for a $99\%$ success rate versus pooling parameter $p$ for LoSc under Top-k and Top-2k strategies, COMP, DD. Each panel corresponds to a different value of $k$ and $n=5000$ . (b) The running times are evaluated across different values of $n$ and $k$ under the unconstrained design with $p=0.25$ . The shadows near each curve represent the $90\%$ confidence interval.

	Unconstrained				Dilution-Constrained				Sample-Constrained
	Top-k		Top-2k		Top-k		Top-2k		Top-k		Top-2k
$k$	$p^{*}$	$m^{*}$	$p^{*}$	$m^{*}$	$P^{*}_{r}$	$m^{*}$	$P^{*}_{r}$	$m^{*}$	$P^{*}_{c}$	$m^{*}$	$P^{*}_{c}$	$m^{*}$
1	0.5000	18	0.5000	18	2500	18	2500	18	6	27	6	27
5	0.1250	153	0.1250	108	625	162	625	117	13	162	6	108
10	0.0625	333	0.0625	189	312	324	312	198	19	270	6	162
15	0.0625	486	0.0625	270	312	459	312	261	13	405	9	216

TABLE II : Experimentally optimal parameters for pooling designs in LoSc (

n=5000

)

$k$	$p^{*}$	$m^{*}$	$k$	$p^{*}$	$m^{*}$
	$n=5000$			$n=10000$
1	0.5000	12	2	0.2240	32
5	0.1072	67	10	0.0498	155
10	0.0698	108	20	0.0338	254
15	0.0476	180	30	0.0284	318
20	0.0365	231	40	0.0222	415

TABLE III : Experimentally optimal parameters for unconstrained design in CS-based method

Panel of Figure 10 — Fig. 7 : Impact of pooling parameters on recovery performance. Recovery success rate as a function of $m$ under different pooling parameters when $n=5000$ and $k=10$ .

Fig. 8 : Experimental and theoretical results of $m^{*}(p)$ for unconstrained design. $m^{*}(p)$ is the function of $p$ under the Top-k strategy when $n=5000$ . Vertical lines mark the theoretically and experimentally optimal pooling parameters.

Fig. 9 : Experimental and theoretical results of $m^{*}(P_{r})$ for dilution-constrained design. $m^{*}\left(P_{r}\right)$ is the function of $P_{r}$ under the Top-k strategy when $n=5000$ . Vertical lines mark the theoretically and experimentally optimal pooling parameters.

Fig. 10 : Experimental and theoretical results of $m^{*}\left(P_{c}\right)$ for sample-constrained design. $m^{*}\left(P_{c}\right)$ is the function of $P_{c}$ under the Top-k strategy when $n=5000$ . Vertical lines mark the theoretically and experimentally optimal pooling parameters.

	Unconstrained				Dilution-Constrained				Sample-Constrained
	Experiment		Theory		Experiment		Theory		Experiment		Theory
$k$	$p^{*}$	$m^{*}$	$p^{*}$	$m^{*}$	$P^{*}_{r}$	$m^{*}$	$P^{*}_{r}$	$m^{*}$	$P_{c}^{*}$	$m^{*}$	$P_{c}^{*}$	$m^{*}$
1	0.5000	18	0.5000	46	2500	18	2500	46	6	27	13	36
5	0.1250	153	0.1667	190	625	162	833	190	13	162	13	179
10	0.0625	333	0.0909	368	312	324	454	368	19	270	13	357
15	0.0625	486	0.0625	547	312	459	312	546	13	405	13	535

TABLE IV : Comparison between theoretical and experimental optimal parameters under the Top-k strategy (

n=5000

)

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

	Unconstrained				Dilution-Constrained				Sample-Constrained
	Top-k		Top-2k		Top-k		Top-2k		Top-k		Top-2k
$k$	$p^{*}$	$m^{*}$	$p^{*}$	$m^{*}$	$P^{*}_{r}$	$m^{*}$	$P^{*}_{r}$	$m^{*}$	$P^{*}_{c}$	$m^{*}$	$P^{*}_{c}$	$m^{*}$
2	0.2500	60	0.2500	50	2500	70	2500	60	9	60	6	60
10	0.0625	350	0.0625	220	312	440	625	220	13	300	9	180
20	0.0313	710	0.0313	400	312	700	312	390	19	600	9	300
30	0.0156	1160	0.0313	520	312	980	312	510	13	840	6	420

Appendix

TABLE S1 : Experimentally optimal parameters for pooling designs in LoSc (

n=10000

)

	Unconstrained				Dilution-Constrained				Sample-Constrained
	Experiment		Theory		Experiment		Theory		Experiment		Theory
$k$	$p^{*}$	$m^{*}$	$p^{*}$	$m^{*}$	$P_{r}^{*}$	$m^{*}$	$P_{r}^{*}$	$m^{*}$	$P_{c}^{*}$	$m^{*}$	$P_{c}^{*}$	$m^{*}$
2	0.2500	60	0.3333	87	2500	70	3333	87	9	60	14	76
10	0.0625	350	0.0909	388	312	440	909	387	13	300	14	376
20	0.0313	710	0.0476	763	312	700	476	762	19	600	14	752
30	0.0156	1160	0.0323	1139	312	980	322	1137	13	840	14	1127

Appendix

TABLE S2 : Comparison between theoretical and experimental optimal parameters under the Top-k strategy (

n=10000

)

Panel of Figure 17 — Fig. S1 : Impact of pooling parameters on recovery performance. Recovery success rate as a function of $m$ under different pooling parameters when $n=5000$ and $k=50$ .

Panel of Figure 18 — Fig. S2 : Impact of pooling parameters on recovery performance. Recovery success rate as a function of $m$ under different pooling parameters when $n=10000$ and $k=20$ .

Panel of Figure 19 — Fig. S3 : Impact of pooling parameters on recovery performance. Recovery success rate as a function of $m$ under different pooling parameters when $n=10000$ and $k=100$ .

Fig. S4 : Experimental and theoretical results of $m^{*}(p)$ for unconstrained design. $m^{*}(p)$ is the function of $p$ under the Top-k strategy when $n=10000$ . Vertical lines mark the theoretically and experimentally optimal pooling parameters.

Fig. S5 : Experimental and theoretical results of $m^{*}\left(P_{r}\right)$ for dilution-constrained design. $m^{*}\left(P_{r}\right)$ is the function of $P_{r}$ under the Top-k strategy when $n=10000$ . Vertical lines mark the theoretically and experimentally optimal pooling parameters.

Fig. S6 : Experimental and theoretical results of $m^{*}\left(P_{c}\right)$ for sample-constrained design. $m^{*}\left(P_{c}\right)$ is the function of $P_{c}$ under the Top-k strategy when $n=10000$ . Vertical lines mark the theoretically and experimentally optimal pooling parameter.

Explore similar work

CRC-Screen: Certified DNA-Synthesis Hazard Screening Under Taxonomic Shift
Apr 30, 2026Najmul HasanDistribution Shift Toxicity Detection
University of North Carolina at Pembroke.
Hit Selection Using SSMD-Based Machine Learning Performance Metrics in High-Throughput Screening Assays
Aug 6, 2026Xiaohua Douglas ZhangDrug Discovery
Department of Biostatistics, College of Public Health, University of Kentucky, Lexington, KY40536, USA
No Screening is More Efficient with Multiple Objects
Aug 19, 2024Shunya Noda, Genta OkadaMechanism Design
Graduate School of Economics, the University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-0033, Japan

Apr 30, 2026J/K move · Enter open · S save

CRC-Screen: Certified DNA-Synthesis Hazard Screening Under Taxonomic Shift

Najmul Hasan

University of North Carolina at Pembroke.

Distribution Shift Toxicity Detection Safety Filtering Conformal Risk Control

Open paper AskPDF arXiv

DNA-synthesis providers screen incoming orders by searching the requested sequence against curated hazard lists. We show that this baseline collapses to a 100% false-flag rate when the hazardous sequence comes from a taxonomic family absent from the reference set: under Conformal Risk Control's certified miss-rate constraint, a low-discrimination signal forces the threshold below the entire test-benign mass. We compose three signals derived from a synthesis order's public annotation:

k

-mer Jaccard similarity to known toxins, the trimmed-mean score of a five-LLM judge panel, and cosine similarity to clustered embedding centroids. Fused under a monotone logistic aggregator and calibrated by Conformal Risk Control, the resulting screener certifies

\mathbb{E}[\mathrm{FNR}] \le α+ \mathrm{TV}

, where the additive term is the calibration-to-test distribution shift under family holdout (a certified ceiling of 24-49% across folds). Across ten leave-one-taxonomic-family-out folds at

α=0.05

on UniProt KW-0800 reviewed toxins, the calibrated screener achieves 0% empirical test miss rate on every fold and 0% test false-flag rate on nine of ten folds. The bound's finite-sample slack

1/(n_{\mathrm{cal}}+1)

caps the certifiable miss rate at 1.77% on our 200-hazard subsample; reaching procurement-grade

α=10^{-3}

requires an

18\times

larger calibration set, which the full reviewed UniProt KW-0800 corpus is large enough to deliver. The binding constraint on certifiable DNA-synthesis screening is calibration data, not algorithms. Code: https://github.com/najmulhasan-code/crc-screen

Abstract

Explore similar work

CRC-Screen: Certified DNA-Synthesis Hazard Screening Under Taxonomic Shift

Hit Selection Using SSMD-Based Machine Learning Performance Metrics in High-Throughput Screening Assays

No Screening is More Efficient with Multiple Objects