Abstract

In recent studies it has been shown that graph representation of protein structures is capable of capturing the 3-dimensional fold of the protein very well, thus providing a computationally efficient approach for protein structure analysis. Centrality measures are generally used to identify the relative importance of a node in the network. Here we demonstrate a novel application of centrality analysis: to identify tandemly repeated structural motifs in 3-d protein structures. This is done by analyzing the profile of various centrality measures in the repeat region. The comparative analysis of five centrality measures based on local connectivity, shortest paths, principal eigen spectra and feedback centrality is presented on proteins containing contiguous ankyrin structural motifs to identify which centrality measure best captures the repetitive pattern of ankyrin. We observe that principal eigen spectra of the adjacency matrix and Katz status index, both exhibit a distinct profile for the ankyrin motif capturing its characteristic anti-parallel helix-turn-helix fold. No such conserved pattern was observed in the repeat regions of equivalent random networks, suggesting that the conserved pattern arises from the 3d fold of the structural motif.

Abstract

Repetition of a structural motif within protein is associated with a wide range of structural and functional roles. In most cases the repeating units are well conserved at the structural level while at the sequence level, they are mostly undetectable suggesting the need for structure-based methods. Since most known methods require a training dataset, de novo approach is desirable. Here, we propose an efficient graph-based approach for detecting structural repeats in proteins. In a protein structure represented as a graph, interactions between inter- and intra-repeat units are well captured by the eigen spectra of adjacency matrix of the graph. These conserved interactions give rise to similar connections and a unique profile of the principal eigen spectra for each repeating unit. The efficacy of the approach is shown on eight repeat families annotated in UniProt, comprising of both solenoid and nonsolenoid repeats with …

Abstract

Tandem repetition of structural motifs in proteins is frequently observed across all forms of life. Topology of repeating unit and its frequency of occurrence are associated to a wide range of structural and functional roles in diverse proteins, and defects in repeat proteins have been associated with a number of diseases. It is thus desirable to accurately identify specific repeat type and its copy number. Weak evolutionary constraints on repeat units and insertions/deletions between them make their identification difficult at the sequence level and structure based approaches are desired. The proposed graph spectral approach is based on protein structure represented as a graph for detecting one of the most frequently observed structural repeats, Ankyrin repeat.

Abstract

BACKGROUND: Ankyrin repeat is one of the most frequently observed structural motif in proteins across all kingdoms of life. These proteins are involved in diverse set of cellular functions and act as transcriptional initiators, cell-cycle regulators, cytoskeletal, ion transporters and signal transducers, and consequently, defects in ankyrin repeat proteins have been found in a number of human diseases. Identification of these structural repeats at the sequence level is difficult due to low conservation between the repeat copies. Thus, analysis at the structure level is desirable. RESULTS: In this study, we propose a graph based approach in the identification and analysis of ankyrin repeats. The 3-dimensional topology of protein structures has been shown to be well captured by protein contact graphs. The connectivity information of these networks is represented in the adjacency matrix and here we propose the analysis of the eigen spectra of the adjacency matrix in the identification of structural repeats. A clear two-peak pattern corresponding to the helix-turn-helix region of the Ankyrin motif is observed in the principal eigenvector of the adjacency matrix. The length distribution of this repetitive pattern along with the organization of the secondary structure elements is used to design an algorithm to identify the Ankyrin structural motifs. The analysis has been carried out on a non-redundant set of 51 proteins annotated in the UniProt database and a very good agreement is observed. Analysis of all the proteins in the alpha class and alpha+beta class in SCOP database has been performed and a number of novel repeats, not annotated in the database have been identified. This approach is then applied on other structural repeats such as Tetraticopeptide repeat (TPR), Annexin, HEAT, ARM, etc. CONCLUSIONS: The graph based analysis of protein structures, along with domain information such as the organization of the secondary structure architecture provides a computationally efficient approach for the identification of structural repeats.

Abstract

In recent studies it has been shown that graph representation of protein structures is capable of capturing the 3-dimensional fold of the protein very well, thus providing a computationally efficient approach for protein structure analysis. Centrality measures are generally used to identify the relative importance of a node in the network. Here we demonstrate a novel application of centrality analysis: to identify tandemly repeated structural motifs in 3-d protein structures. This is done by analyzing the profile of various centrality measures in the repeat region. The comparative analysis of five centrality measures based on local connectivity, shortest paths, principal eigen spectra and feedback centrality is presented on proteins containing contiguous ankyrin structural motifs to identify which centrality measure best captures the repetitive pattern of ankyrin. We observe that principal eigen spectra of the adjacency matrix and Katz status index, both exhibit a distinct profile for the ankyrin motif capturing its characteristic anti-parallel helix-turn-helix fold. No such conserved pattern was observed in the repeat regions of equivalent random networks, suggesting that the conserved pattern arises from the 3d fold of the structural motif.

Abstract

BACKGROUND: Repetition of super secondary structure is a common phenomenon, especially in higher eukaryotic organism. The copy number and assembly of these repeating units are responsible for diverse protein-protein interactions, and consequently, defects in repeat proteins are linked to many diseases. The variation within the repeat units makes their identification difficult at the sequence level and structure based approaches are desired. Since most structure based methods employ computationally intensive structure-structure alignment, we propose a computationally efficient structure-based approach for the identification of repeats using concepts from graph theory. RESULTS: The three-dimensional topology of protein structures is known to be well captured by protein contact graphs. The connectivity information in a graph is represented in the adjacency matrix and the eigenspectra of the adjacency matrix depicts the topological importance of each node to the connectivity of the graph. In our earlier work, we observed that the principal eigenspectra of the adjacency matrix well captures the tandemly repeated structural motifs. Here we propose an algorithm for the identification of tandemly repeated structural motif using graph properties and secondary structure information from STRIDE database. The algorithm begins by first identifying the length of repeat motif by analyzing the periodicity of peaks in eigenvector centrality. The repeat boundaries are then identified by superposing the contiguous repeats and extending on either side of the peak regions to the start/end of the secondary structure elements and checking for periodicity of the secondary structure architecture in the identified repeat regions. Thus, using the secondary structure annotation helps in refining the boundaries of the repeat regions and to discard false positives. We have tested the algorithm for identifying various structural repeats such as HEAT, WD, Ankyrin (ANK), Tetratricopeptide repeat (TPR), Leucine rich repeat (LRR), etc. with different super secondary structure motif, ranging from all alpha, to all beta to a mixed topology such alpha-turn-alpha, beta-alpha, etc. The predictions are in agreement with annotation in UniProt database. CONCLUSIONS: The graph based analysis of protein structures, along with domain information such as the organization of the secondary structure elements provides a computationally efficient approach for the identification of structural repeats.

Abstract

Pattern discovery is at the heart of bioinformatics, and algorithms from computer science have been widely used for identifying biological patterns. The assumption behind pattern discovery approaches is that a pattern that occurs often enough in biological sequences/structures or is conserved across organisms is expected to play a role in defining the respective sequence’s or structure’s functional behavior and/or evolutionary relationships. The pattern recognition problem addressed here is at the genomic level and involves identifying horizontally transferred regions, called genomic islands. A horizontally transferred event is defined as the movement of genetic material between phylogenetically unrelated organisms by mechanisms other than parent to progeny inheritance. Increasing evidence suggests the importance of horizontal transfer events in the evolution of bacteria, influencing traits such as antibiotic …

Abstract

Internal repetition within proteins is a commonly observed phenomenon as these provide multiple binding sites for protein-protein interactions by forming integrated multi-repeat assemblies in three-dimension. However, at the sequence level the similarity between internal copies of the repeats is generally low, and identification at the structural level is desired. In recent studies it has been shown that graph representation of protein structures is capable of capturing the 3-dimensional fold of the protein very well, thus providing a computationally efficient approach for protein structure analysis. Here we exploit this feature of protein structure graphs and carry out a comparative analysis of eight graph centrality measures for the identification of tandem structural repeats. We observe that principal eigen spectra of the adjacency matrix and Katz status index are able to capture the repetitive pattern of the structural units. The spectral analysis being computationally efficient, in this paper we present the analysis of the principal eigen spectra of the adjacency matrix of proteins containing Ankyrin (ANK) repeats, the most commonly occurring structural motifs in proteins.

Abstract

Internal repetition within proteins is a commonly observed phenomenon and presents multiple binding and structural roles to proteins. Ankyrin repeat, one of the most widely existing protein motifs in nature, forms helix-turn-helix motif, and exclusively functions to mediate proteinprotein interactions, some of which are directly involved in the development of human cancer and other diseases. It has been observed that the ankyrin repeat motif is defined by its fold rather than by its function, and as there is no specific sequence underlying the fold, its identification at the structural level is desirable. We propose graph based approach in the identification and analysis of these repeats. The topological details of protein structures has been shown to be effectively captured by protein graphs. In this study we analyzed about twelve graph measures for the identification of repeated structural motifs. Of these, degree, Katz status, Page rank, closeness vitality and eigenvectors corresponding to the principal eigenvalue of the adjacency matrix are found to be promising. We observe that on considering the secondary structure information along with the analysis of various graph measures, it is possible to accurately identify the boundaries of individual repeats. This approach is computationally very efficient compared to the structure-structure self-comparison. Design and engineering of repeat proteins may help to elucidate their structural and biophysical properties, such as the dependence of stability and folding on the number of repeats, the importance of key intra- and inter-repeat interactions and identifying novel binding molecules suitable for biotechnological or medical applications.

Abstract

In this paper we analyze the topological properties of airport network of India (ANI) using graph theoretic approach. We show that such an analysis can be useful not only in planning the infrastructure and growth of the air-traffic connectivity, but also in managing the flow of transportation during emergencies such as accidental failure of the airport, close down of the airport due to unexpected climate changes, terrorist attacks, etc. Knowledge of the connectivity pattern and load on various routes can also help in making judicious decisions for reduction of flights to contain the spread of the infectious disease.