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.

Abstract

The recent large scale advances in science and technology has resulted in accumulation of large amount of biological pathways data. Any metabolic pathway contains large number of enzymes, metabolites and reactions. To make sense of diverse data available on a system, one needs to correlate and analyze them as a whole. Motivated by the potential benefits of graph theory and its application in biological data, we discuss the automated reconstruction and analysis of metabolite network of Arabidopsis thaliana using concepts of graph theory. A.thaliana metabolite network was reconstructed and analysis of the global properties of its metabolite-centric graph shows that the network is small-world and scale-free in nature. The investigation of nodes with high centrality values like high degree and high betweeness in this network help in identifying important metabolites, reactions, etc. Newman’s modularity-based approach has been used in the analysis of the metabolite network of A. thaliana to identify pathway clusters, isolated pathways, and orphan metabolites or products. Our analysis on network representations helps in understanding the relationship between the metabolites, enzymes and reactions of metabolic pathways in A. thaliana.

Abstract

Graph comparisons, quantitative characterizations, computation of topological indices, clustering and partitioning are some of the major computations of graph that have yielded valuable results in various disciplines. Motivated by the potential benefits of graph theory application on biological data, we discuss the reconstruction and analysis of enzyme centric network of Arabidopsis thaliana using graph theory concepts. We had earlier constructed the metabolite network of Arabidopsis thaliana and witnessed the scale free and small world nature of the network. Compared to metabolites, the enzymes are more conserved in and across many pathways. So the aim of constructing the enzyme centric network is to see if the network follows similar network properties of the metabolite network and to look for additional details that a metabolite network cannot reveal. The enzyme flat file from KEGG FTP is used as the data set for the reconstruction of the enzyme centric network. We examined the network to find the relationship between topological connections among enzymes and their functions during evolution. The enzyme sequences of high degree and high betweenness enzymes belonged to ancient fold class and ancestry value showing evidence that they evolved very slowly.

Abstract

IGIPT is a web-based integrated platform for the identification of genomic islands (GIs). It incorporates thirteen parametric measures based on anomalous nucleotide composition on a single platform, thus improving the predictive power of a horizontally acquired region, since it is known that no single measure can absolutely predict a horizontally transferred region. The tool filters putative GIs based on standard deviation from genomic average and also provide raw output in MS excel format for further analysis. To facilitate the identification of various structural features, viz., tRNA integration sites, repeats, etc. in the vicinity of GIs, the tool provides option to extract the predicted regions and its flanking regions.

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 resistance, symbiosis and fitness, virulence, and adaptation in general. In the genomic era, with the availability of large number of bacterial genomes, the identification of genomic islands also form the first step in the annotation of the newly sequenced genomes and in identifying the differences between virulent and non-virulent strains of a species. Considerable effort is being made in their identification and analysis and in this chapter a brief summary of various approaches used in the identification and validation of horizontally acquired regions is discussed.