Extracting Complete Subnets And Mapping Them In The Biology Networks

Nowadays with the technology and experimental means development, kinds of molecular biology networks have been constructed. It is very important to study topology structures of biology networks which can guide our research of molecular structures, function and evolutionary conservation. Furthermore, the structure of complete subnet is one of the most important topology for our research and it most likely reveals our interesting problems.According to the graph theory, the problem of finding the maximum complete subnet is a NP-complete problem. Through utilizing biological basis of scale-free network characteristics, applying the dynamic programming algorithm thinking, and using two specific algorithms, we can quickly extract all complete subnets in a network. At last we match all these subnets and establish the mapping relations in them.We download the data of DIP (Database of Interacting Proteins) which provides the yeast (Saccharomyces cerevisiae) protein-protein interaction network (2007/4/1 version). Then we extract all the complete subnets in the interaction network. The maximum complete subnet has 10 protein nodes. According to the mapping relationships of complete subnets, we forecast eight new important interactions which are confirmed by dataset of BioGrid (2007/6/1 version) and other papers. Thus the size of maximum complete graph is extended from 10 to 14 and we promote the DIP dataset (DIP dataset of 2007/6/3 version still does not contain interactions of our forecast).We submit some complete subnets to KEGG (Kyoto Encyclopedia of Genes and Genomes), which can study the function furthermore. To two different biology network of one species, network characteristics and protein complexes can be found after we have extracted the total complete subnets. For the biological networks of two different species, the conservation of evolution can be studied from the system level after we have matched and mapped these complete subnets. It is a very good character to complete subnets. Therefore, our method will have broad prospects of application.