article: Protein–DNA interactions are crucial for many cellular processes. Now with the increased availability of structures of protein–DNA complexes, gaining deeper insights into the nature of protein–DNA interactions has become possible. Earlier, investigations have characterized the interface properties by considering pairwise interactions. However, the information communicated along the interfaces is rarely a pairwise phenomenon, and we feel that a global picture can be obtained by considering a protein–DNA complex as a network of noncovalently interacting systems. Furthermore, most of the earlier investigations have been carried out from the protein point of view (protein-centric), and the present network approach aims to combine both the protein-centric and the DNA-centric points of view. Part of the study involves the development of methodology to investigate protein–DNA graphs/networks with the development of key parameters. A network representation provides a holistic view of the interacting surface and has been reported here for the first time. The second part of the study involves the analyses of these graphs in terms of clusters of interacting residues and the identification of highly connected residues (hubs) along the protein–DNA interface. A predominance of deoxyribose–amino acid clusters in β-sheet proteins, distinction of the interface clusters in helix–turn–helix, and the zipper-type proteins would not have been possible by conventional pairwise interaction analysis. Additionally, we propose a potential classification scheme for a set of protein–DNA complexes on the basis of the protein–DNA interface clusters. This provides a general idea of how the proteins interact with the different components of DNA in different complexes. Thus, we believe that the present graph-based method provides a deeper insight into the analysis of the protein–DNA recognition mechanisms by throwing more light on the nature and the specificity of these interactions.
  A network of interactions among the macromolecules drives the cell. The protein–DNA interactions orchestrate the high fidelity processes like DNA recombination, DNA replication, and transcription. With the increasing number of high-resolution structures of macromolecular complexes, it is now possible to obtain insights into the atomic details of interactions governing their structural and functional integrity. In the present study, we focus on protein–DNA interactions, which can either be specific or non-specific depending on the functional requirement. Insights into the mechanism of protein–DNA binding and recognition have come from extensive analysis of protein–DNA interfaces [1]–[14]. Some of these investigations have been carried out at the level of pairwise interactions between the atoms/residues of the interacting partners. However, the information communicated along the interfaces is rarely a pairwise phenomenon. New insights can be gained by investigating the interactions holistically, extending beyond the pairwise analysis of atomic/residue interactions. This can be achieved through the use of efficient methods, which capture the topological features from the structures of these complexes. The concept of representing protein structures as graphs exists in the literature [15]–[21]. In these studies the amino acids in proteins are considered as nodes and the interaction between these nodes have been considered as edges for constructing different types of graphs. These protein structure graphs (PSG) have been successfully used in the analysis of protein structure, stability and function [22], [23]. PSGs have also been analyzed in protein–DNA complexes to identify significant interactions as clusters of interacting amino acids at the protein–DNA interfaces [4]. However in such studies, the interacting nucleotides of the DNA were not considered as part of the graphs, since the parameters required for representing DNA as graphs were not available at that time. As a conceptual turning point, it has been pointed out that most of the information on protein–DNA complexes have been obtained from a “protein-centric” view and new insights are likely to emerge if protein–DNA complexes are investigated from a “protein–DNA-centric” viewpoint [24]. Recently, protein–DNA complexes have been classified on the basis of structural descriptors that highlights the significance of the protein induced distortions of the DNA [3]. In the current article, the interactions between the protein and the DNA in protein–DNA complexes have been evaluated in a collective fashion by considering the complexes as bipartite graphs. We have developed the parameters to evaluate the strength of interaction between the amino acids and the nucleotides, based on the atomic contacts. Such a combined graph based analysis of protein–DNA interactions has been presented for the first time in this study. The protein–DNA graph is of special interest, since we are dealing with two different types of biopolymers with unique structural and chemical properties. In the case of proteins, the two amino acids are linked by a rigid peptide bond and each amino acid could be unambiguously considered as a node in the protein graph. However, in the case of DNA, the linkage between two nucleotides is through a flexible phosphodiester bond and the nodes can be defined at various levels. For example, a nucleotide as a whole or its individual chemical components such as the phosphate group, deoxyribose and the bases (A, T, G, and C) can be represented as nodes. Such a different representation of nodes has distinct advantages of their own, in interpreting the nature of interaction between the protein and DNA [13], as we will show in this study. An important component of the analysis is to quantify the strength of interaction (on the basis of the number of atomic contacts) between these chemically different molecules to capture the essence of the intermolecular interactions at the protein–DNA interface. The present graph based analysis of protein–DNA complexes focuses on the following points. Primarily, the interface interactions of protein–DNA complexes have been investigated at a network level. This is achieved by constructing protein–DNA graphs (PDGs) on the basis of the strength of interaction between the nodes and also by performing extensive calibrations to choose the optimal strength of interactions to gain structural insights. Secondly, the clusters and hubs of such interacting amino acids and the nucleotides at the interfaces have been analyzed in a set of protein–DNA complexes. Significant results that are inaccessible by conventional pairwise analysis of the structure or by sequence analysis have been obtained from the present work. These include the identification of spatial networks of interacting residues that are sequentially far apart, the evaluation of a scale of interaction strength along which we can compare and analyze the interaction networks of protein–DNA complexes and the identification of groups of optimally interacting residues which stabilize the structural architecture. Furthermore, we have been able to revisit the classification scheme of DNA binding proteins. Our classification schema, which is based on the concepts of graphs/network, interaction strength, and the type of interaction, is distinct from the classification schemes proposed earlier with a protein-centric point of view. We have compared our results with the other classification schemes [3], [25].
  A protein–DNA graph (PDG) is a bipartite graph constructed to represent the interaction between the amino acids of the protein and the nucleotides of the DNA in a protein–DNA complex. A bipartite graph deals with two different node sets and edges are defined across the two node sets. A contact in the bipartite PDG is defined when a side chain of an amino acid interacts with the nucleotide. The interactions of the amino acid with the nucleotide can be considered at different levels: with the phosphate (p), deoxyribose sugar (S) or base (B) components individually, or with the nucleotide as a complete entity. The edges are defined upon quantification of the interaction between the amino acids and the nucleotides with the “Interaction Strength, ” Iij (It is to be noted that the interaction strength mentioned here is based on the number of atom-atom contacts and in a way reflects only the local packing density.) The details of the construction of PDG are presented in the Materials and Methods section. A bipartite PDG representation of a protein–DNA complex is illustrated in Figure 1. The nodes in a PDG are connected if the Iij evaluated between the nodes is greater than or equal to a user-defined Iij. The user-defined Iij is termed as Minimal Effective Connection (MEC). We have constructed PDGs from protein–DNA complexes using a range of MEC from 0% to 15%. A graph generated with a high MEC is sparse with strongly connected nodes, and the graph generated with a low MEC is dense with weakly connected nodes (Figure S1). Hence, the choice of the window of MEC for the analysis of the graphs becomes important, which ensures that we neither include insignificant (weak) interactions nor miss significant (strong) ones. As we have partitioned the nucleotide of the DNA into its phosphate, deoxyribose and base components, an optimal range of MEC (OMEC) is chosen for constructing protein-phosphate (P-p), protein-deoxyribose (P-S) and protein-base (P-B) graphs. The OMEC is selected to balance a trade-off between the strength of interaction and the cluster size. Thus, the MEC is further classified into weak (WMEC), optimal (OMEC) and strong (SMEC) on the basis of Iij and the ranges of MEC values are listed in Table 1. All further discussions are based on the analyses with the OMEC ranges, unless otherwise specified. We obtain P-p, P-S, and P-B clusters and hubs from the adjacency matrices of PDGs (see Materials and Methods section). The detailed analysis of protein–DNA complexes through these parameters is presented in the following section. The propensities of amino acids to form P-p, P-S, and P-B graphs were calculated from DS1 (see Materials and Methods section). The results are presented in Figure 2. In general, we observe a higher propensity of basic residues (Arg and Lys) to occur in PDGs. Arg is more preferred in P-B graphs whereas Lys is more preferred in P-p graphs. All polar amino acids occur significantly in all the three component clusters, however the preferences vary. For instance, Ser, the smallest polar amino acid has a higher propensity to occur in P-p graphs, and Asn/Gln, which contain the planar conjugated amide group has higher propensity of occurrence in P-B graphs. The interactions of Val, Ile, Leu, Phe, Trp are higher in the P-S graphs indicating that the deoxyribose is involved in hydrophobic and van der Waals interactions. The acidic residues (Asp and Glu) are not excluded from the interface interactions, in spite of the net negative charge of DNA. However, the occurrence of these amino acids near the phosphate backbone (P-p graphs) is minimal and significant near the bases (P-B graphs). Also, Glu interacts with bases more frequently than Asp. Thus, the analysis confirms some of the expected trends of interaction between amino acids and DNA, such as the dominance of basic and polar residues, and lesser preference of hydrophobic and acidic amino acids in PDGs. Additionally, the preference of interactions with individual chemical components such as the phosphate backbone, deoxyribose sugar and bases have been elucidated in detail. Such a level of analysis is useful in understanding the subtleties involved in protein–DNA interactions, and for interpreting the nature of component graphs as will be discussed later in the context of classification of protein–DNA complexes. The protein–DNA complexes have been classified into different groups based on the structural similarity of the proteins bound to the DNA. Luscombe et al have provided a comprehensive classification of the protein–DNA complexes based on the secondary structural motifs of proteins interacting with the DNA [25]. The classification results in eight groups of complexes: β-sheet group, β-hairpin group, helix turn helix (HTH), zipper type (ZT), zinc coordinating group, other α-helices, enzymes and others [25]. We have cured it further to remove structures with single-stranded DNA (see Table S1 for details regarding the members of the dataset). We have generated PDGs for all groups of protein–DNA complexes. The PDGs are further analyzed to investigate the properties such as the preference of proteins to interact with the DNA, the components of the DNA to which the protein binds, the dominance of a particular type of cluster (P-p, P-S, or P-B). We have also tried to find a generic pattern (if any) of clusters that could be identified amongst the groups of protein–DNA complexes. The important results for each group are discussed in the following sections. The importance of classifying the DNA binding proteins from the protein–DNA point of view, rather than the protein-centric view is being recognized for developing better protein–DNA recognition code [24]. Since our method considers the spatial relationships between the amino acids and the nucleotides at the interface, we have attempted to classify the DNA binding proteins based on these spatial relationships. The interface P-p, P-S, and P-B clusters are examined in the protein–DNA complexes. The analysis of these clusters shows that the complexes can either have exclusive P-p, P-S, or P-B clusters or they can contain a mixture of these types of clusters. In cases where more than one type of cluster is observed, we define overlapping (amino acids sharing the same nucleotide) or non-overlapping (amino acids making contact with different nucleotides) clusters. Based on the types of clusters observed, the complexes are classified into seven groups. The complexes containing exclusive P-p, P-S, and P-B clusters are denoted as class 1,2, and 3, respectively. Mixtures of (P-p+P-S), (P-S+P-B), and (P-p+P-B) clusters are denoted as class 4,5, and 6, respectively. The complexes containing all the three component clusters (P-p, P-S, and P-B) are considered as class 7. A sub-classification based on the presence of overlapping or non-overlapping (P-p+P-S) or (P-S+P-B) or (P-p+P-B) components is made for cases 4 to 7. The details of the classification of the protein–DNA complexes are presented in Table 4. Among the protein–DNA complexes of the dataset only ten complexes exhibit exclusive P-p, P-S, or P-B clusters at the protein–DNA interface and thereby fall into distinct classes 1,2, or 3 (Table 4). Majority of the other complexes however, seem to employ concerted interactions and interact with different chemical components of the nucleotide by forming two or more types of clusters (either overlapping or non-overlapping) at the interface (see Figure S2 for illustrative figures). It should be noted that our classification scheme based on the interaction patterns of amino acids with nucleotide components in PDG does not directly deal with the type of interaction involved (like electrostatics, van der Waals, H-bonding, etc). However, indirectly, the P-p cluster is dominated by electrostatic interaction and the P-S clusters are composed of van der Waals interactions along with stacking of aromatic residues with the deoxyribose ring. The P-B graphs are dominated by stacking of amino acids (mostly the planar side chain of Arg) with the bases, H-bonding and also charge mediated interactions. A comparison of the present classification with the structural motif based classification by Luscombe et al [25] shows distinct differences. A major difference is that the proteins from the same group (motif based classification) fall under different classes of interface clusters. In other words, even though the proteins have the same secondary structure motif (e. g. , HTH motif), their mode of interaction may vary significantly depending on factors like the sequence of DNA (cognate/non-cognate DNA binding) and the component (p, S, or B) of the nucleotide to which it binds. However, we see a few salient features, which are common to both the classification schemes. For example, most members of the Zinc Coordinating group belong to non-overlapping category of class 6 (P-p and P-B), and non-overlapping class 4 (P-p and P-S). A few exceptions are ZIF-268 DNA complex (1zaa), Glucocorticoid mutant–DNA complex (1lat), and Reverba Orphan Nuclear Receptor/DNA complex (1a6y). Similarly, in the Helix Turn Helix members (with the exception of Matα2 Homeodomain Operator Complex (1apl), lambda repressor mutant protein/ DNA complex (1lli), and Engineered Cro monomer/DNA complex (3orc) ) belong to either class 4 or class 7, both of which contain P-p and P-S clusters (overlapping as well as non-overlapping). The β-sheet group, which bind to the TATA box, belong to the classes 5 and 7, both of which contain P-S and P-B clusters. These protein–DNA complexes (with the exception of TFIIB/TBP/TATA element ternary complex (1vol) ) belong to the overlapping type, indicating the continuous involvement of the deoxyribose and the base moieties of the nucleotides. As we had seen earlier, the P-S clusters in these complexes are extensive in most of the cases. Finally, a majority of the enzymes belong to the classes 4 and 7 (both overlapping and non-overlapping), which have P-p and P-S clusters (Table 4). Here we have shown that the DBPs classification based on the protein–DNA interface interaction at the molecular level differs significantly from the protein motif based classification, although a little consensus is observed. DBPs have also been classified based on other criteria. For instance, Prabakaran et al [3] have classified DBPs based on the structural descriptors (Structural Descriptor Based Classification-SDBC), involving both protein and DNA. And Siggers et al [7] have developed a score (IAS) based on the interface geometry to align interfaces, which has been used to classify protein–DNA complexes. We have also investigated the interface clusters of the complexes from the dataset used by Prabakaran et al and found only a marginal correspondence in classification. For example, Class 1 of SDBC has prominent overlapping P-p and P-B clusters when subjected to our method of classification. This class is characterized by major groove binding proteins and interact mostly with the bases of the DNA. Also Class 2 of SDBC, which has high number of both major and minor groove contacts, and structurally deformed DNA, has overlapping P-p and P-S clusters. Class 5 of SDBC shows mostly overlapping P-S and P-B clusters. The fact that there is only a marginal overlap between different classification schemas underscores the versatilities in protein–DNA recognition mechanism. It may be valuable to use different approaches to obtain complementary information to understand the protein–DNA recognition mechanisms in detail. The present study aims to represent a protein–DNA interface as an undirected bipartite graph based on non-covalent interactions. A quantitative method has been developed to represent the interactions between both DNA and protein as a single, combined graph. Such a representation has facilitated the study of the spatial relationships between the amino acids and the nucleotides at the protein–DNA interface in a holistic way. Thus, protein–DNA interfaces across the spectrum of complexes could be compared at a uniform level, irrespective of the structural and functional differences. In general, we have provided a method of quantifying the interactions of proteins with the components of nucleotides (phosphate, deoxyribose and base). It is now clear that the combined representation of protein and DNA as PDGs could highlight the intricacies involved in protein–DNA recognition of some families of proteins. For instance, the predominance of protein-deoxyribose (P-S) clusters and hubs has brought out the specificity of the interaction in β-sheet proteins. Such analysis and the group specific features of protein–DNA recognition could be used as a starting point in predicting the DNA binding sites on these proteins. We have also proposed a scheme for classifying the structures based on the nature of the network connectivity present at the protein–DNA interface. Based on comparative analysis, we conclude that different classification schemes could provide complementary information on the nature of protein–DNA interactions. Thus, the analyses performed on a dataset of protein–DNA complexes have highlighted the nature of the clusters and hubs present at the recognition site. These clusters and hubs may not only prove to be valuable in understanding the residues contributing to the stability of the protein–DNA interfaces, but also could be identified as features characteristic for a given group of proteins. The knowledge gained from the study could also provide a platform for further docking and prediction experiments.
  The protein–DNA complexes with resolution better than 2. 5 Å and with protein identity less than 25% were taken from PDB (Version 3. 1) [39] and were further cured so that the proteins (size>40 amino acids) are bound to at least one complete turn of double-stranded DNA. This resulted in a dataset (DS1) of 118 protein–DNA complexes (Table S5), which was used for evaluating the amino acid propensities for various component graphs and for recalculating the normalization values. The interface clusters and hubs were identified on two datasets, DS2 from Luscombe et al [25] and DS3 from Prabakaran et al [3], which were used for direct comparison of their classification schemes with our graph based classification scheme. DS2 was further cured for removing identical protein chains and the complexes containing single stranded DNA (Table S1). The interaction between the amino acids and the nucleotides at the protein–DNA interface is represented as undirected bipartite Protein–DNA Graphs (PDGs). Here, the amino acids comprise one node set and the nucleotides constitute the other node set of the bipartite-PDGs as shown in Figure 1. As the focus of this work is on the protein–DNA interface, we have adopted this bipartite graph, in which the edges are made only across the amino acids and the nucleotides. The non-covalent interactions between the amino acid side chains and the nucleotides form the basis for linking the nodes. These non-covalent interactions are evaluated from the atomic contacts of the nodes. Any two atoms from nodes i and j, are considered to make a contact if they are within a distance of 4. 5 Å and the total number of such contacts (nij) is evaluated between a pair of nodes i and j. The strength of interaction (Iij) between these nodes i and j is evaluated in a manner similar to that adopted in the case of protein structure graphs [4], [23], [40], as given in Equation 1. (1) where Iij is the strength of interaction between the amino acid side chain (i) and the nucleotide (j) of the protein–DNA complex. As the graphs are undirected Iij = Iji. nij is the number of interactions existing between nodes i and j (contacts within distance of 4. 5 Å). Ni and Nj are the normalization values of the corresponding nodes evaluated as described in the next subsection. Here the evaluation of the strength of interaction is restricted only to atom-atom contact and does not explicitly take into account the details such as hydrogen bond, salt bridge interactions etc. Indirectly, this amounts to a measure of packing density at the selected region. Iij is evaluated for all the amino acid-nucleotide (interface) interactions of a given protein–DNA complex. A threshold of Iij is used to connect two nodes in a graph. The threshold Iij representing the minimal atomic connectivity between interacting amino acids and the nucleotides is called as the Minimal Effective Connection (MEC). Thus, an edge between nodes i, j is defined if the Iij evaluated is greater than the user-defined MEC. For instance, a MEC of 6% specified by the user results in the generation of a PDG with nodes connected by the interaction strength Iij≥6%. Here the evaluation of Iij requires the normalization values (maximum number of contacts made by the unit) for corresponding nucleotide and amino acid units. The details of the evaluation of the normalization values are discussed below. The normalization values are the estimates of the maximum non-covalent contacts an amino acid or a nucleotide can have in protein–DNA complexes. The method of obtaining normalization values for amino acids in proteins was previously given [40] and a similar method is used to obtain protein–DNA normalization values. These values are evaluated from a non-redundant dataset of protein–DNA complexes [41], for all the 20 amino acids (Na) and the A, G, T, C nucleotides (Nn) as shown below, (2) where Max ak is the maximum number of non-covalent contacts made by the amino acid, “a, ” with other amino acids and nucleotides in the protein–DNA complex “k. ” Similarly, Max nk is evaluated for the nucleotide “n” in the structure “k. ” “m” is the total number of protein–DNA complexes from the non-redundant dataset. Here it should be noted that, while calculating the amino acid - amino acid contacts, the contacts made by an amino acid side chain with its sequence neighbors (i±1) are ignored. However, in the case of nucleotides, the sequential base contacts (stacking) of a nucleotide (i±1) are taken into account, ignoring only the covalent phosphate and the sugar contacts of the sequential residues. We wish to point out that the normalization values of amino acids obtained here from protein–DNA complexes are not significantly different from those obtained only from protein structures [40]. Protein-nucleic acid recognition mechanisms are often mediated by amino acids through a specific or nonspecific recognition of a nucleotide backbone or base at the protein–DNA interface. Quite often the electrostatic interactions of proteins with the phosphate groups are considered as non-specific and the stacking interactions and hydrogen bonding with bases are considered as specific. Furthermore, there is substantial conformational flexibility in the phosphodiester bond and in the conformation of the deoxyribose ring. Therefore, the nucleotides have been dissected into their chemical components such as the phosphate backbone (p), deoxyribose sugar (S), and the base (B). The interactions of an amino acid with all these individual components are characterized by constructing separate interaction graphs of amino acids with all the p, S, and B components of the DNA. The normalization values (NP, NS, and NB) for these dissected components of the nucleotide are also calculated using Equation 3 where, in place of the whole nucleotide, the dissected component of the nucleotide is considered as, (3) where Max pk is the maximum number of non-covalent contacts, made by the phosphate with other amino acid and nucleotide residues in a protein–DNA complex “k. ” Similarly, Max Sk and Max Bk are evaluated for the deoxyribose sugar and the base, respectively, from the complex “k. ” “m” is the total number of protein–DNA complexes from the non-redundant dataset. These individual phosphate, sugar backbone, and base-specific normalization values are useful to obtain finer details regarding the molecular connectivity existing at the protein–DNA interface. The normalization values of the individual chemical components of the nucleotide thus obtained are given in Table 5. The PDGs are constructed as specified above and represented as binary adjacency matrices at a given MEC. Clusters of interacting nodes are identified from the adjacency matrix using Depth First Search (DFS) algorithm [42]. This is a method of graph traversal in which we obtain all the nodes that are either directly or indirectly linked to a node Vx from which the search starts. The backtracking of Vx starts only when all such connected nodes are explored. The next start point Vy is the next unvisited node in the graph. Thus, a cluster of strongly interacting nodes (higher MEC) captures the significant interactions that exist between the amino acids and the nucleotides at the protein–DNA interface. In this study, we have focused on the interaction of protein with the components of nucleotides. Thus, we have identified the component clusters, P-p, P-S, and P-B, to capture the interaction of amino acids with the phosphate, deoxyribose and the base of the nucleotides, respectively. In many cases, amino acids interact with more than one component of a nucleotide (for example, an amino acid may interact with the phosphate atoms as well as the deoxyribose of the nucleotide). In such cases, we have defined the clusters as “overlapping clusters” (which consists of both phosphate and deoxyribose of the same nucleotide). Thus overlapping clusters constitute the interactions of amino acids captured with two or more components of a nucleotide. The details of the interface clusters for DS2 are given in Table S1 and Table S2. Hubs are highly interacting nodes in a graph. In protein structure graphs, a node was declared as a hub if it was connected to a minimum of four nodes [23]. The same definition is being used here for the protein-sugar (P-S) and protein-base (P-B) hubs in PDGs. In the case of a protein-phosphate (P-p) graph, a phosphate residue connected to a minimum of three residues is considered as a hub. The purpose of hub analysis in this study is to identify the nucleic acid component, highly connected to the amino acid residues and vice versa. Thus, a (P-B) hub for example, may constitute an amino acid connected to four or more bases or a base being connected to four or more amino acid residues. The interface component hubs for the protein–DNA complexes of DS2 are presented in Table S1 and Table S3.
summary: The interaction of proteins with DNA is crucial for several cellular processes. Some insights into the mode of interaction can be obtained from the analysis of the complexed structures. Conventional analyses are based on the identification of pairwise interactions. However, a collective representation of the network of interactions and the analyses of such networks provide valuable information, which is not easy to obtain from pairwise analyses. Although the protein structure networks have been described in the literature, this is the first time that a network representation of protein–DNA is described. Construction and analysis of such networks have given valuable information on protein–DNA interactions in terms of network parameters, such as clusters of interacting residues and hubs, which are highly connected residues. Furthermore, the results also represent both the protein- and the DNA-centric viewpoints, because the analysis is carried out on combined networks. The methodology developed here can lead to predictions, such as important residues responsible for stabilizing protein–DNA interactions, and will be of interest to experimentalists.
keywords: computational biology/macromolecular structure analysis
  biophysics/macromolecular assemblies and machines
title: Insights into Protein–DNA Interactions through Structure Network Analysis