Applied Nonadaptive Group Testing and Superimposed Codes

DMS 9973252摘要：给定一个可唯一表征为正或负的有限基本元素集合，成组测试的目的是通过对基本集合的子集或池执行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.