Analysis Of Topological Characte Ristics And Ide Ntification Of Topological Substructure S In Biological Networks

In the post-genome era,one of the most important goals for bioformatics and computational systems biology study is to understand the functions of genes,non-coding RNAs,proteins and other relevant biomolecules,as well as uncover the underlying mechanisms of biological processes.With the rapid growth of high throughput techniques,a large volume of omics data such as genomics,transcriptomics and protemics data has been generated,which provides new opportunities for studying the functions of biomo lecules.However,how to utilize and analyze these omics data as well as identify valuable information from it still remains a challenge.The biomolecular networks are powerful tools to analyze cell life activities with omics data,and can be really useful to enlighten and promote the research for revealing the underlying mechanisms of biological processes.It can not only explicit ly represent the intricated interactions among biomolecules,but also be helpful to systematically explore the cooperative patterns among them.Therefore,using data mining methods based on graph theory to analyze the topological and functional characteristics of biological networks,as well as design new algorithms to identify important network substructures is of great significance to discover vital regulatory pattens and pathways in bio logical processes.Starting from mult iple types of biological networks,the main work and contribut ions of this thesis are as follows:(1)We analyze the topological characteristics of protein-protein interaction networks,transcriptional regulatory networks,miRNA regulatory networks and co-regulatory networks,including the characteristic path lengt h,the clustering coeffic ients,the degree distribution and the average degree of nearest neighbors and etc.Based on the analysis,we conclude the common characterstics and differences among networks of same type but different species as well as networks of different types,which provide the theoretical basis for proposing appropriate methods to construct corresponding network models and detect meaningful network substructures.(2)By analyzing the interaction densit y of protein-protein interaction networks,we find that proteins of the same age groups tend to interact with each other,while proteins of different age groups avoid to have interactions.Further analysis of the age homogeneity in network motifs show that proteins within network motifs have the same interaction tendency.However,existing network models cannot generate simulated networks with this biological characterist ic.Here we propose a new network evolut ionary model based on network motifs.Comparing with other network simulat ion models,the motif-based model can not only capture the topological characteristics of protein-protein interaction networks such as degree distribution,characteristic path legnth and etc.,but also generate the same interaction density as real protein interaction networks.The analysis of evolutionary mechanisms of the network topological characteristics lays the theoretical foundation for the following funct ional module discovery and network motif identification.(3)Existing algorithms to identify miRNA regulatory modules in miRNA regulatory networks often have high time complexity,and fail to integrate transcriptional regualtory and protein-protein interaction data.Here we propose a new algorithm to identify miRNA regulatory modules called Mirsynergy.We first construct the reliable disease-specific miRNA regulatory networks based on LASSO with miRNA/mRNA expression data as well as sequence-based miRNA-mRNA relationship predictions;we then propose a two-stage clustering algorithm based on neighborhood expansion.Comparing with other miRNA regulatory module discovery algorithms,Mirsynergy has lower time complexity,and the modules identified by Mirsynergy are more significantly enriched in biological processes and canonic al pathways.The surviva l analys is reveals several prognostically promising regulatory modules.(4)The performance of Mirsynergy in detecting regulatory modules in sparse miRNA regulatory networks is generally good,whereas in dense networks its performance is relative ly poor.We propose a novel algorit hm called BCM to detect regulatoy modules in dense regulatory networks based on bicliques merging.BCM algorithm first enumerates all the maximal bicliques of specified size,then the statistical significance of each bicliques is evaluated by a random network ensemble.The bicliques that are statistically significant than a certain cutoff are merged iterative ly by a greedy-based strategy.Comparing with Mirsynergy,the modules identified by BCM are more densely connected,and the miRNA/mRNA within these modules have higher negative correlation coefficients.The survival analysis as well as the breast cancer subtype analys is also reveals several prognostically promising regulatory modules.(5)The network motif discovery problem in co-regulatory networks has much higher time complexity due to the existence of mult iple types of nodes.Moreover,the randomizat ion process of co-regulatory networks is often insufficient.We propose a new algorithm to identify co-regulatory network motifs called CoMoFinder.By adding node type restrictions as well as leveraging parallelism,CoMoFinder significantly reduces the computational time of the subgraph enumeration process.We further promote the efficiency of CoMoFinder by separating the subgraph isomorphic classification process from the subgraph enumeration process.Moreover,we adopt a mult i-layer strategy based on edge-switch to randomize the sub-networks in order to fully shuffle the co-regulatory networks.Comparing with existing algorithms,CoMoFinder not only has higher accuracy but also is more robust.Besides,it s time complexity is much lower than other algorithms.Further analys is shows that the co-regulatory network motifs are significantly enriched in more biological processes and canonical pathways than general co-regulatory subgraphs.