Applied Nonadaptive Group Testing and Superimposed Codes

应用非自适应组测试和叠加代码

• 批准号: 9973252
• 负责人: Anthony Macula
• 金额: $ 5.27万
• 依托单位: SUNY College at Geneseo
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-01 至 2001-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9973252&HistoricalAwards=false
• 关键词: Applied; Nonadaptive; Group; Testing; Superimposed

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.

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