Construction of d(H)-disjunct matrix for group testing in hypergraphs

Hong Gao; F. K. Hwang; My T. Thai; Weili Wu; Taieb Znati

doi:10.1007/s10878-006-9634-z

Construction of d(H)-disjunct matrix for group testing in hypergraphs

Hong Gao, F. K. Hwang, My T. Thai, Weili Wu, Taieb Znati

Research output: Contribution to journal › Article › peer-review

21 Citations (Scopus)

Abstract

Given a hypergraph with at most d positive edges, identify all positive edges with the minimum number of tests each of which tests on a subset of nodes, called a pool, and the outcome is positive if and only if the pool contains a positive edge. This problem is called the group testing in hypergraphs, which has been found to have many applications in molecular biology, such as the interactions between bait proteins and prey proteins, the complexes of eukaryotic DNA transcription and RNA translation. In this paper, we present a general construction for constructions of nonadaptive algorithms for group testing in hypergraphs.

Original language	English
Pages (from-to)	297-301
Number of pages	5
Journal	Journal of Combinatorial Optimization
Volume	12
Issue number	3
DOIs	https://doi.org/10.1007/s10878-006-9634-z
Publication status	Published - Nov 2006
Externally published	Yes

Keywords

Complex
DNA library screening
Group testing
Pooling designs

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-006-9634-z

Cite this

@article{8ff217893b2b4ca38792ff5387bb307f,

title = "Construction of d(H)-disjunct matrix for group testing in hypergraphs",

abstract = "Given a hypergraph with at most d positive edges, identify all positive edges with the minimum number of tests each of which tests on a subset of nodes, called a pool, and the outcome is positive if and only if the pool contains a positive edge. This problem is called the group testing in hypergraphs, which has been found to have many applications in molecular biology, such as the interactions between bait proteins and prey proteins, the complexes of eukaryotic DNA transcription and RNA translation. In this paper, we present a general construction for constructions of nonadaptive algorithms for group testing in hypergraphs.",

keywords = "Complex, DNA library screening, Group testing, Pooling designs",

author = "Hong Gao and Hwang, {F. K.} and Thai, {My T.} and Weili Wu and Taieb Znati",

note = "Funding Information: Taieb Znati: Support in part by National Science Foundation under grant CCF-0548895. Funding Information: Weili Wu: Support in part by National Science Foundation under grant ACI-0305567.",

year = "2006",

month = nov,

doi = "10.1007/s10878-006-9634-z",

language = "English",

volume = "12",

pages = "297--301",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Construction of d(H)-disjunct matrix for group testing in hypergraphs

AU - Gao, Hong

AU - Hwang, F. K.

AU - Thai, My T.

AU - Wu, Weili

AU - Znati, Taieb

N1 - Funding Information: Taieb Znati: Support in part by National Science Foundation under grant CCF-0548895. Funding Information: Weili Wu: Support in part by National Science Foundation under grant ACI-0305567.

PY - 2006/11

Y1 - 2006/11

N2 - Given a hypergraph with at most d positive edges, identify all positive edges with the minimum number of tests each of which tests on a subset of nodes, called a pool, and the outcome is positive if and only if the pool contains a positive edge. This problem is called the group testing in hypergraphs, which has been found to have many applications in molecular biology, such as the interactions between bait proteins and prey proteins, the complexes of eukaryotic DNA transcription and RNA translation. In this paper, we present a general construction for constructions of nonadaptive algorithms for group testing in hypergraphs.

AB - Given a hypergraph with at most d positive edges, identify all positive edges with the minimum number of tests each of which tests on a subset of nodes, called a pool, and the outcome is positive if and only if the pool contains a positive edge. This problem is called the group testing in hypergraphs, which has been found to have many applications in molecular biology, such as the interactions between bait proteins and prey proteins, the complexes of eukaryotic DNA transcription and RNA translation. In this paper, we present a general construction for constructions of nonadaptive algorithms for group testing in hypergraphs.

KW - Complex

KW - DNA library screening

KW - Group testing

KW - Pooling designs

UR - http://www.scopus.com/inward/record.url?scp=33748435358&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748435358&partnerID=8YFLogxK

U2 - 10.1007/s10878-006-9634-z

DO - 10.1007/s10878-006-9634-z

M3 - Article

AN - SCOPUS:33748435358

SN - 1382-6905

VL - 12

SP - 297

EP - 301

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

Construction of d(H)-disjunct matrix for group testing in hypergraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this