Applied Nonadaptive Group Testing and Superimposed Codes

摘要给定一个有限的可唯一表征为正或负的元素地面集，群检验的目标是通过对地面集的子集或池进行0、1次检验来优化正对象的识别。组测试算法是搜索算法。如果将搜索算法看作一组测试，那么非自适应组测试算法中的任何测试都不能被任何其他测试的结果修改。因此，执行测试的顺序是不相关的。根据正在建模的实际问题，通常可以同时执行测试。因此，当内存或数据存储能力有限时，非自适应搜索算法非常适合并行处理和计算。每个并行算法都是非自适应的。在这个项目中，我们建议使用和开发组合码和代数码，从这些码的矩阵表示构造非自适应群测试算法。该提案的一个具体目标是开发更高效的高通量组测试算法，当测试错误率高达10%时，可以发现大量的阳性结果。从应用的角度来看，有效和高效地搜索未知物体的能力对生物技术、电信和国家安全领域的许多努力都是必不可少的。这些未知物体可能是特定DNA序列的位置，也可能是一群计算机黑客。由于其计算能力，群体测试算法在人类基因组计划中发挥着关键作用，它们在筛选许多不同类型的生物和化学数据库中至关重要。群测试算法也已应用于计算机网络协议中，可用于计算机入侵检测软件的开发。

DMS 9973252Abstract: Given a finite ground set of elements which can be uniquely characterized as positive or negative, the object of group testing is to optimize the identification of the positive objects by performing 0, 1 tests on subsets or pools of the ground set. Group testing algorithms are search algorithms. If one thinks of a search algorithm as a battery of tests, then no test in a nonadaptive group testing algorithm can be modified by the results of any other test. Thus the order in which the tests are performed is irrelevant. Depending upon the real world problem that is being modeled, it is often the case that the tests can be carried out simultaneously. Hence, nonadaptive search algorithms are well suited for parallel processing and computing when memory or data storage capability is limited. Every parallel algorithm is nonadaptive. In this project, we propose to use and develop combinatorial and algebraic codes to construct nonadaptive group testing algorithms from the matrix representations of these codes. A specific aim of this proposal is to develop more efficient high throughput group testing algorithms that find a large number of positives when testing error rates can range up to 10%.From an applied point of view, the ability to effectively and efficiently search for unknown objects is essential to many endeavors in the areas of biotechnology, telecommunications, and national security. The unknownobjects may be the locations of particular DNA sequences or a group of computer hackers. Because of their computational power, group testing algorithms play a pivotal role in the Human Genome Project and they are essential in the screening many different kinds of biological and chemical data bases. Group testing algorithms have also been applied to computer network protocols and can be used in the development of computer intrusion detection software.