A framework for generalized group testing with inhibitors and its potential application in neuroscience

Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao EchizenarXiv 2018 · OpenReview

Abstract: The main goal of group testing with inhibitors (GTI) is to efficiently identify a small number of defective items and inhibitor items in a large set. This work introduces generalized GTI (GGTI), which incorporates "hybrid" items that act as both signals and masks. Given the vast number of potential GGTI instances, the authors propose a non-adaptive framework for classifying all item types and demonstrate its potential for classifying neurons in neuroscience. Finally, the paper outlines how to realize this scheme in practice.

Introduction

Group testing is a combinatorial method used to identify a small number of "defective" items (signals) within a massive population. A common analogy is testing pools of blood samples to find a few infected individuals without testing everyone separately.

However, real-world biological systems are complex. In many cases, certain items act as inhibitors, canceling out the signal of defective items and causing a "false negative" in a pool. While previous research handled defectives and inhibitors separately, this paper addresses the gap where an item might be hybrid—capable of acting as both a signal and an inhibitor depending on the context. This is particularly relevant in neuroscience, where the brain's 86 billion neurons must be classified as excitatory (signals), inhibitory (masks), or hybrid. Performing this one-by-one is economically and temporally impossible; the authors propose GGTI as a scalable "divide and conquer" solution.

Methodology

The authors develop a non-adaptive framework for GGTI, meaning all test pools are designed before any results are known. This approach is significantly faster than multi-stage "adaptive" testing.

Workflow comparison between the theoretical GGTI model and its practical deployment.

The core technical contributions include:

  • The GGTI Model: A formalization of how hybrid items interact within a test pool.
  • Matrix Design via Tensor Products: To create the testing schedule (the "pooling design"), the authors use the tensor product ($\otimes$) of two specific binary matrices ($\mathcal{G}$ and $\mathcal{M}$). This allows them to handle three different properties (defective, inhibitory, and hybrid) simultaneously.
  • Decoding Algorithm: A reconstruction algorithm is provided to identify the sets of different item types from the test outcomes.
  • Neuroscience Mapping: Biological "Action Potentials" (APs) are mapped to group testing outcomes. If a pool of neurons produces an AP, the test is considered "positive."

Key Insights and Ideas

  • The Hybrid Item: The introduction of the "hybrid" category is the primary innovation. In the brain, some neurons can release different neurotransmitters (like glutamate for excitation and GABA for inhibition), making them neither purely "defective" nor purely "inhibitory" in the classical sense.
  • Combinatorial Complexity: The authors calculate that there are over 7.2 million possible instances of GGTI models based on different combinations of item types and criteria. Their framework is designed to be general enough to cover this entire space.
  • Efficiency over Exhaustion: The main advantage is the reduction in tests. In a population of $n$ items, traditional testing requires $n$ tests. GGTI aims for sub-linear complexity, meaning the number of tests required grows much slower than the number of neurons.

Results and Discussion

  • Theorem 1: The authors prove that their matrix-based design can successfully identify defective, inhibitor, and hybrid sets in $O(gA)$ time, where $g$ is related to the number of test pools.
  • Practical Feasibility: The paper outlines two implementation paths: an Ideal path using physically constructed synapses to act as test logic, and a Feasible path using multimeters and conduction fibers to track signals, which is more economical with current technology.
  • Scalability: The framework is designed to handle the "colossal" groups found in biology, where the number of items $n$ is in the billions, but the number of "interesting" items (defectives/inhibitors) remains relatively small ($d, h, b \ll n$).

Limitations and Future Work

While the framework is robust, the authors note that the formal definition of the specific conditions under which a hybrid item switches roles is left for future work. Additionally, while the paper mentions noisy settings where test outcomes might flip, a "zero-error" scheme for GGTI remains an open problem. Finally, the "Ideal" biological implementation requires precise control of neural synapses at a scale that currently sits at the edge of experimental capability.

Summary updated

Abstract

The main goal of group testing with inhibitors (GTI) is to efficiently identify a small number of defective items and inhibitor items in a large set of items. A test on a subset of items is positive if the subset satisfies some specific properties. Inhibitor items cancel the effects of defective items, which often make the outcome of a test containing defective items negative. Different GTI models can be formulated by considering how specific properties have different cancellation effects. This work introduces generalized GTI (GGTI) in which a new type of items is added, i.e., hybrid items. A hybrid item plays the roles of both defectives items and inhibitor items. Since the number of instances of GGTI is large (more than 7 million), we introduce a framework for classifying all types of items non-adaptively, i.e., all tests are designed in advance. We then explain how GGTI can be used to classify neurons in neuroscience. Finally, we show how to realize our proposed scheme in practice.
BibTeX
@misc{bui2018framework,
  author = {Thach V. Bui and Minoru Kuribayashi and Mahdi Cheraghchi and Isao Echizen},
  title = {{A framework for generalized group testing with inhibitors and its potential application in neuroscience}},
  year = {2018},
  eprint = {1810.01086},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.01086},
}
Figure