DomainParser uses a new algorithm for the decomposition of a multi-domain protein into individual structural domains. The underlying principle used is that residue-residue contacts are denser within a domain than between domains. We have formulated the domain decomposition problem as a network flow problem, in which each residue is represented as a node of a 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 cut of the network, which minimizes the total cross-edge capacity (minimum cut). The classical Ford-Fulkerson algorithm is used to find a minimum cut of a network. For proteins with multiple domains, our algorithm repeatedly applies the Ford-Fulkerson algorithm to bi-partition the network and forms a partition tree until some stopping criteria are met. To deal with networks with non-unique minimum cuts, we have extended the algorithm to find all cuts, which achieve the minimum cross-edge capacity, using an enumeration algorithm by Picard and Queyranne. The capability of finding all minimum cuts of a network allows us to evaluate and rank a decomposition based on more global properties of a domain, including its compactness and three-dimensional shape; and hence improve the quality of a decomposition. A post-processing step is used to merge segments that may have been overcut, based on certain geometric and physical properties of a domain.
The program DomainParser is copyrighted and is NOT in the public domain. The authors of DomainParser make no representations about the suitability of the software for any purpose. It is provided "as is" without express or implied warranty. The authors shall not be liable for any damages suffered by Licensee from the use of this software.
Back to the DomainParser Page.