Bioinformatics Vol. 16 no. 12 2000
Pages 1091-1104
© 2000 Oxford University Press
Original Paper |
Protein domain decomposition using a graph-theoretic approach
1 Computational Biosciences Section, Life
Sciences Division, Oak Ridge National Laboratory, Oak Ridge, TN
37830-6480, USA
2 Department of Computer Science, University
of Colorado, Boulder, CO 30309, USA
Received on May 10, 2000
; revised on August 3, 2000
; accepted on August 4, 2000
Motivation: Automatic decomposition of a multi-domain protein into individual domains represents a highly interesting and unsolved problem. As the number of protein structures in PDB is growing at an exponential rate, there is clearly a need for more reliable and efficient methods for protein domain decomposition simply to keep the domain databases up-to-date.
Results: We present a new algorithm for solving the domain decomposition problem, using a graph-theoretic approach. We have formulated the problem as a network flow problem, in which each residue of a protein is represented as a node of the network and each residue–residue contact is represented as an edge with a particular capacity , depending on the type of the contact. A two-domain decomposition problem is solved by finding a bottleneck (or a minimum cut) of the network, which minimizes the total cross-edge capacity, using the classical Ford–Fulkerson algorithm. A multi-domain decomposition problem is solved through repeatedly solving a series of two-domain problems. The algorithm has been implemented as a computer program, called DomainParser. We have tested the program on a commonly used test set consisting of 55 proteins. The decomposition results are 78.2% in agreement with the literature on both the number of decomposed domains and the assignments of residues to each domain, which compares favorably to existing programs. On the subset of two-domain proteins (20 in number), the program assigned 96.7% of the residues correctly when we require that the number of decomposed domains is two.
Availability: The executable of DomainParser and its web server are available at http://compbio.ornl.gov/structure/domainparser/.
Contact: xyn{at}ornl.gov
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  H. Zhou, B. Xue, and Y. Zhou DDOMAIN: Dividing structures into domains using a normalized domain-domain interaction profile Protein Sci., May 1, 2007; 16(5): 947 - 955. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 B. Raveh, O. Rahat, R. Basri, and G. Schreiber Rediscovering secondary structures as network motifs--an unsupervised learning approach Bioinformatics, January 15, 2007; 23(2): e163 - e169. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Zhao, D. Stoffler, and M. Sanner Hierarchical and multi-resolution representation of protein flexibility Bioinformatics, November 15, 2006; 22(22): 2768 - 2774. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. Pugalenthi, G. Archunan, and R. Sowdhamini DIAL: a web-based server for the automatic identification of structural domains in proteins Nucleic Acids Res., July 1, 2005; 33(suppl_2): W130 - W132. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Kundu and R. L. Jernigan Molecular Mechanism of Domain Swapping in Proteins: An Analysis of Slower Motions Biophys. J., June 1, 2004; 86(6): 3846 - 3854. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J.-t. Guo, D. Xu, D. Kim, and Y. Xu Improving the performance of DomainParser for structural domain partition using neural network Nucleic Acids Res., February 1, 2003; 31(3): 944 - 952. [Abstract] [Full Text] [PDF]
|
|