Title: Protein-protein interaction and group testing in bipartite graphs

Authors: Yingshu Li, My T. Thai, Zhen Liu, Weili Wu

Addresses: Department of Computer Science, Georgia State University, 34 Peachtree Street, Atlanta, GA 30303, USA. ' Department of Computer Science, University of Minnesota, Twin Cities, 200 Union Street S.E., Minneapolis, MN 55455, USA. ' Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA. ' Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA

Abstract: The interactions between bait proteins and prey proteins are often critical in many biological processes, such as the formation of macromolecular complexes and the transduction of signals in biological pathways. Thus, identifying all protein-protein interactions is an important task in those processes, which can be formulated as a group testing problem in bipartite graphs. In this paper, we take the advantages of the characteristics of bipartite graphs and present two nonadaptive algorithms for this problem. Furthermore, we illustrate a generalisation of our solution in a more general case.

Keywords: protein-protein interaction; group testing; bipartite graphs; nonadaptive algorithms; bait proteins; prey proteins; bioinformatics.

DOI: 10.1504/IJBRA.2005.008444

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.4, pp.414 - 419

Published online: 20 Dec 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article