Identifying Functional Modules And Analyzing Evolution In Metabolism Networks

In the post-genome era, with the completion of gene sequencing in hundreds of species and a better understanding of these genes, it become possible to reconstruct reliable species-specific metabolic networks from genomic information. The systematic analysis of metabolic pathway and how metabolites interact will be benefit for better understanding and use of the cellular metabolic process, and to promote the development of fermentation technology and drug engineering. In addition, through the comparison and analysis of the topologies in different metabolic networks we can have a better understanding of evolutionary history and evolu-tionary law. Therefore, decomposition of metabolic network, discovery of the function module and the conservative model, and the calculation of evolutionary distance are becoming hot research focuses.Based on the our study of the characters of topology structures and centrality measures of nodes in metabolic network, our work on decom-position and comparison of metabolic networks is studied using complex network theory, graph theory and many other mathematical methods. The main contributions summarized the follows:Complex network theory and graph theory were applied to the analysis of the topology structure characters and centrality measures of nodes in different specie metabolic networks, such as the degree distribu-tion, the clustering coefficient and characteristic path length. Some com-mon characters are detected from these metabolic networks, which can provide foundation for developing reasonable algorithms of decompose, compare and mining metabolic networks.Since most of the hierarchical clustering algorithm can not detect overlapping community in complex networks, this paper proposed a new measurement for evaluating the connectivity between communities. Based on the proposed measurement, a fast hierarchical clustering algo-rithm, named F-HOC, was proposed to detect overlapping and hierarchi-cal community structure. Compared with existing algorithms for detecting overlapping and hierarchical community structure in complex network, F-HOC can achieve better performances on speed and sensitivity when applied on network with obvious community structure. The running time of F-HOC maintains grow linearly with the increasing of the size of the network, which substantiates F-HOC is more suitable for large-scale complex networks than others.To avoid the problem of combinatorial explosion of pathway when analyzing Pathway in large metabolic networks, appropriate algorithms for an automated decomposition of these networks into smaller subsys-tems are needs. This paper proposed CMD, a community connec-tivity-based metabolic network decomposition algorithm. CMD improves F-HOC based on topological features of the metabolic network. It can identify the single long paths from the peripheral of a metabolic network. CMD has been applied to the decomposition of E.coli metabolic network. The results show it can not only identify the overlapping functional mod-ules and the Pathways in the database, but also reflect the hierarchical structure of function modules through bottom-up merging process with-out missing single long paths on the peripheral of the network.Existing network comparison methods only consider the nodes themselves. MWD developed by us is a novel comparison method that considered both nodes and its topological differences. MWD combines the principal component analysis and the wavelet transform algorithm to compare metabolic networks, and calculate the evolution distance be-tween two species based on the calculated similarity. Applied MWD to analyze metabolic networks from 109 species, the results show this algo-rithm is efficient in network comparison. From the comparison results can reveal the specificity of metabolic networks are provide the mathematical basis for research of the evolution of metabolic network. By the com-parison of the evolutionary distances, which was calculated by the simi-larity of the model organisms and each species, and the Jaccard distance obtained from the approach of set theory, it has shown that the results ob-tained from MWD produces smaller errors and therefore demonstrate the correctness of MWD.The Apriori-based methods for detecting frequent subgraphs in bio-logical networks suffer from high computational complexity and are not suitable for large scale metabolic network. This paper proposed an algo- rithm based on FP-tree structure, MaxFP, which is used to find conserva-tive model in metabolic network. Compared with those Apriori-based methods, the experimental results shows that MaxFP have a higher effi-ciency, and can find more biological significance of frequent subgraphs.This paper has solved some problems effectively which exist in the process of the correlation between topology, function, and evolution of metabolic networks. The algorithms proposed in this paper have high ef-ficiency and are able to attain biologically more meaningful results which are proved to be statistically significant, hence provide guidance to rele-vant biological experiments and study. Moreover, the proposed algo-rithms can be generalized to other complex networks with the similar structures.