زعفران: یک چارچوب سریع، کارآمد و مقاوم برای آزمایش گروهی مبتنی بر کدهای گراف پراکنده

آزمون گروهی مسئله شناسایی K آیتم معیوب در میان n آیتم با ترکیب گروهی آیتم‌ها است. در این مقاله، الگوریتم‌های آزمون گروهی را برای بازیابی تقریبی با پیچیدگی نمونه‌ای بهینه ترتیب طراحی می‌کنیم و از ابزارهای طراحی و تحلیل از نظریه کدگذاری گراف‌های پراکنده مدرن استفاده می‌کنیم. الگوریتم ما، SAFFRON، حداقل (1 – ε)K آیتم معیوب را با احتمال 1 – K/n⁽ʳ⁾ با m = 2(1 + r)C(ε)K log₂ n آزمایش بازیابی می‌کند، جایی که ε یک ثابت به طور دلخواه کوچک است، C(ε) یک ثابت با قابلیت توصیف دقیق است و r هر عدد صحیح مثبت است. پیچیدگی رمزگشایی Θ(K log n) است. همچنین تغییرات الگوریتم SAFFRON را پیشنهاد می‌کنیم که نسبت به نویز و ناپیوستگی‌های ناشناخته مقاوم هستند. برای مثال، برای n ≃ 4.3 × 10⁹ و K = 128، مشاهده شده که الگوریتم ما همه آیتم‌های معیوب را با m ≃ 8.3 × 10⁵ آزمایش بازیابی می‌کند، حتی در حضور نتایج آزمایشی پر نویز. علاوه بر این، زمان رمزگشایی کمتر از ۴ ثانیه روی یک لپ‌تاپ با پردازنده ۲ گیگاهرتز Intel Core i7 و حافظه ۸ گیگابایت طول می‌کشد.

Group testing is the problem of identifying K defective items among n items by pooling groups of items. In this paper, we design group testing algorithms for approximate recovery with order-optimal sample complexity by leveraging design and analysis tools from modern sparse-graph coding theory. Our algorithm, SAFFRON, recovers at least (1 – ε)K defective items w.p.1 – K/nr with m = 2(1 + r)C(ε)K log2 n tests, where ε is an arbitrarily small constant, C(ε) is a precisely characterizable constant, and r is any positive integer. The decoding complexity is Θ(K log n). We also propose variations of SAFFRON, which are robust to noise and unknown offsets. For example, for n ≃ 4.3 × 109 and K = 128, our algorithm is observed to recover all defective items with m ≃ 8.3 × 105 tests, even in the presence of noisy test results. Moreover, the decoding time takes less than 4 seconds on a laptop with a 2 GHz Intel Core i7 and 8 GB memory.