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.

Abstract

In the present study, we have constructed and analysed the metabolic networks of virulent and non-virulent strain of E. coli. Concepts from graph theory are used to systematically determine how differences in basic metabolism of different strains of E. coliare reflected at the systems level. Analysis of metabolic networks can help us to understand the evolutionary history of cellular metabolic process and we can also identify the potential drug target by comparing the networks.

Abstract

Two classes of networks that have been extensively studied in the analysis of physical systems are: (i) regular networks, wherein each node interacts with a specified number of neighboring nodes on geometrical lattices, and (ii) random networks, wherein every pair of nodes have a fixed probability of interacting with each other. Recently much attention is being focused on a class of network models that are neither strictly regular nor completely random, but are somewhere in-between and exhibit properties of both, called small world networks. These networks are shown to exhibit high clustering (i.e., nodes sharing a common neighbor have a higher probability of being connected to each other than to other nodes) and a low average path length (the average of the shortest distance/path between every pair of nodes in the network). Examples for small-world networks are found to occur widely across the biological (e.g., neural connection patterns), social (e.g., friendship network, co-authorship) and technological (e.g., the world wide web) domains. Also it has been observed that a large number of real complex systems exhibit power-law behaviour in their degree distribution, i.e., a few nodes have a very high degree. Such networks are referred to as scale-free networks. Thus, non-standard topologies with long-range connections (i.e., non-local diffusion) and uneven degree distributions are not uncommon in real-life systems and may provide different kinds of spatiotemporal dynamics depending on the extent of non-local diffusion. Here we discuss the characterization and control of spatiotemporal dynamics on four different network topologies, viz., (i) regular, (ii) random, (iii) small-world, and (iv) scale-free by external perturbation or pinning a few nodes in the network. This would provide us insight into the role of the network topology (the underlying connectivity structure) on the dynamics of the systems defined on such networks and the efficacy with which the dynamics can be the controlled or manipulated. An extensively studied example of a nonlinear system exhibiting a wide variety of complex dynamics ranging from simple periodic behavior to chaos is the logistic map. Here we define coupled logistic maps on the four different topologies and systematically investigate the control by external perturbation/pinning for two chaotic regimes: (i) r = 3.6 (weak-chaos), and (ii) r = 3.9 (strong chaos). Our preliminary results show that pinning nodes at regularly spaced intervals, 2nd, 4th, etc., the pinning strength required on a small-world network is similar to that in case of regular networks. For 25% of the nodes pinned, the dynamics on the scale-free topology is controllable but on random networks, it is not. However, on pinning nodes having high centrality measures, viz., degree, betweenness and closeness, we observe that control of the spatiotemporal dynamics is achieved, by pinning only 10% of high degree/ betweenness nodes in low chaotic regime on both small-world and scale-free networks. Complete control of the network is not observed on pinning nodes with high closeness values. For strongly chaotic dynamics, control is achievable only on scale-free networks on pinning 20% of nodes having either high degree, betweenness, or closeness values. Key Words: Dynamics, Control, Topologies, Coupled Logistic Maps, Chaos, Regular, Smallworld, Random, Scale-free networks, Centrality.

Abstract

In this study we analyze the topology and structure of Airport Network of India (ANI) using the graph theoretic approach. We investigate the transmission flow in the network using graph centrality measures. We observe that though ANI exhibits scale-free behaviour, it differs from Barabasi-Albert scale-free model and we suggest a scale-free model that results in high clustering coefficient to be most suitable to model ANI. The analysis is not only useful in planning the infrastructure and expansion of the air-traffic connectivity, but also in managing the flow of transportation during emergencies such as accidental failure of the airport, closing down the airport due to unexpected climate changes, terrorist attacks etc. It has been observed that densely connected air-transportation networks play a major role in the spread of infectious diseases, viz., Avian-influenza, Swine-Flu, etc., turning from epidemic into pandemic. Knowledge of the connectivity pattern for reduction of flights on certain routes can help to reduce the spread of the disease.

Abstract

Here we apply the graph-theoretic concept of Betweenness centrality to a class of protein repeats, e.g., Armadillo (ARM) and HEAT. The Betweenness of a node represents how often a node is traversed on the shortest path between all pairs of nodes i, j in the network and thus gives the contribution of each node in the network. These repeats are not easily detectable at the sequence level because of low conservation between independent repeated units, e.g., HEAT repeats are known to have less than 13% identity. Their identification at the structure level typically involves self structure-structure comparison, which can be computationally very intensive. Our analysis of a set of proteins from ARM and HEAT repeat family shows that the repeat regions exhibit similar connectivity patterns for the repeating units. Since it is generally accepted that in many networks, the larger the degree of a node, the larger the chance that many of the shortest paths will pass through this node, computing vertex Betweenness provides a simple and elegant approach for identifying tandem structural repeats in proteins.

Abstract

Here we present a simple method based on graph spectral properties to automatically partition multi-domain proteins into individual domains. The identification of structural domains in proteins is based on the assumption that the interactions between the amino acids are higher within a domain than across the domains. These interactions and the topological details of protein structures can be effectively captured by the protein contact graph, constructed by considering each amino acid as a node with an edge drawn between two nodes if the Cα atoms of the amino acids are within 7Å. Here we show that Newman’s community detection approach in social networks can be used to identify domains in protein structures. We have implemented this approach on protein contact networks and analyze the eigenvectors of the largest eigenvalue of modularity matrix, which is a modified form of the Adjacency matrix, using a quality function called “modularity” to identify optimal divisions of the network into domains. The proposed approach works even when the domains are formed with amino acids not occurring sequentially along the polypeptide chain and no a priori information regarding the number of nodes is required.