Optimization Methods For Key Genes Selection Based On Mutual Information Network

With the development of gene chip technology, the focus of biology research has been changed to the understanding of the operation mechanism from the organization structure and functions of a whole biological system, rather than the single genes. Especially, rapid acquisition of high-throughput data source brings many challenges to the biologists. For example, how to detect or identify the key genes and functional gene modules in some specific process based on the massive amounts of data has become an important part of the research areas in bioinformatics. The main purpose of this thesis is to investigate the method of identifying the key genes and gene modules based on the mutual information relevant network of genes, where two optimization models and related algorithms are discussed.In this thesis the basis of our investigation is the mutual information relevant network of genes constructed on the gene data downloaded from GEO data bank in NCBI. The main contents of this thesis are as follows.I) Rank aggregation method and algorithms for selecting key genes:Firstly, given two expression data profiles from experimental and control sample groups, we construct two networks and consider the different ranks of genes with respect to three different structural parameters of the network:node strength, betweenness and clustering coefficient. Next, we make use of rank aggregation model and its algorithms to integrate the different ranks to a final "super-list", and from this, select key genes. In the end, we use the expression profiles of yeast Saccharomyces cerevisiae to test the effectiveness of our method.II) Evolutionary game theory and maximum clique algorithm for identifying functional gene modules:The concept of evolutionary stable strategy, known as a refinement of Nash equilibrium, suggests that evolutionary forcers select against mutant individuals. In gene relevant networks, this concept can be viewed as a good characterization of gene modules. Based on this idea, the problem of extracting evolutionary stable strategy-clusters is first cast into the problem of finding a maximum clique in the network. Then, this problem is modeled as a quadratic program, and the algorithm for finding the strict local maximal cliques (i.e., gene modules in gene networks) is given based on the KKT conditions. Finally, we annotate the genes in the modules obtained to test the effectiveness of the method by making use of the data of kidney cancer.