Functional Pattern Detection And Phylogenetic Analysis Based On Metabolic Networks

Cellular metabolism is essential for the maintenance and upgrowth of lives. All the reactions are catalysed by enzymes in cells, and such movement will decompose the nutrients in order to keep all the reactions in balance under various conditions. Thus such movement will generate other nutrients and provide energys of beings. From the perspective of graph theory, the metabolic pathway of an organism can be effectively modelled and analysed by a graph (here we call it a network) by regarding each of substrates as a vertex and each reaction as an edge. The studying of the metabolic networks in topological properties, organization rules, functional motif, functional module and orthology analysis provide a deep understanding in cellular metabolic process. Furthermore, it promotes the development of desease diagnosing, medicine designing and toxicology analysis, etc.The KEGG metabolic pathway is an authoritative and widely used metabolic database. Based on the KEGG database, we analyze the topological properties of metabolic networks, and several effective algorithms are proposed for the detection of motif and functional modules. The phylogenetic analysis based on metabolic networks is also studied. The detailed original works include:A new algorithm is proposed for reconstructing the metabolic networks which causes no redundance and data loss. We reconstruct 61 organisms including 15 archaea, 38 bacteria and 8 eukaryotes in the forms of enzyme-enzyme relation networks and compound interaction networks. All the subsequent researches are progressed based on these accurate data. We take a detail study of some topological properties on the networks, including degree distribution, small-world, modular organized structure and bow-tie structure, which are consistent with existing research.Frequent subgraph mining has emerged as a key issue for motif discovery. A novel algorithm, named by ESRD, for this problem is proposed, which can efficiently obtain all the subgraphs in networks based on the distribution of rings. In order to enhance the efficiency of subgraph mining in non-exhaustive enumerate mode with high accuracy of subgraph frequency, a dynamic sample algorithm is also developed. The experimental results in four real bio-networks show the superiority of our algorithm to existing algorithms. The partial list of size-3 and size-4 motif in metabolic networks is provided and the high scoring motifs take a similar distribution order in the 3 domain of phylogenetic tree, which prove that the metabolic networks are highly conserved. The modules in metabolic networks carry out their functions and some of specific functional modules are conserved in various kinds of networks. A new similarity measure between compounds integrating the phylogeny is firstly proposed. Based on the similarity, the AP algorithm is adopted with an immediate purpose to obtain a hard partition of the multiple species networks. A soft partition is finally obtained with an overlapping extension that is concerning about the orthologous coefficient of modules. By applying the method, we can not only find the orthologous modules functions ubiquitously existing in the phylogenetic tree, but also detect the periphery modules existing in partial of the tree. The experimental results demonstrate that the conserved functional modules are perfect matched with those proposed in the KEGG database. Furthermore, the periphery modules show that the distribution of functional modules differs greatly in various species.The construction of phylogenetic tree of various species is very important in learning the origin and the evolution of species. By introducing the concept of "kernel", we propose a new algorithm for defining the similarity between different metabolic pathways as the summation of weighted matching score of the kernel subgraph and the non-kernel one respectively, the phylogenetic tree is constructed using Neighbor-Joining algorithm. The experiments show that it is an efficient method according to the comparison between the trees obtained and NCBI taxonomy.