Font Size: a A A

Graph Isomorphism Algorithm Based On Feature Compression And Application In Network Motif Discovery

Posted on:2011-01-21Degree:MasterType:Thesis
Country:ChinaCandidate:J L HuFull Text:PDF
GTID:2178330332488461Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Human genome research goes from the structural genomics era into the era of functional genomics. which is also known as "post-genome era". A new study found that the human genome is not a combination of isolated genes and a large number of useless "DAN fragments", but a complex network system. Therefore, the theory of complex networks has become the focus of attention. Network motif discovery is one of the most representative branches.Network motifs are small connected subnetworks that occur in significantly higher frequencies than in random networks. For finding motifs, we have to count the subnetwork frequencies, which conduct graph isomorphism. However, graph isomorphism remains an NP-hard problem. In this paper, we present a new heuristic algorithm based on feature compression, Feature Compression for Graph Isomorphism (FCGI). First, four special topological features of graph are constructed. Then flow-operation method was adept for these features by FCGI to compress them into one canonical label for each kind of graphs. This strategy greatly reduces the node-replacement searching space and the number of comparisons.All the possible adjacency matrix of all kinds of connected graphs was tested in our experiment. And a comparison of performance in classification of feature compression and hierarchical classification was made on the tested synthetic database. The results show that our new algorithms can precisely and effectively solve the graph isomorphism problem for both the directed and undirected graphs. Furthermore, we test the algorithm for motif detection in the gene regulatory network of Saccharomyces cerevisiae. Network motifs which are theoretically and experimentally proved to be of great significance are successfully detected.
Keywords/Search Tags:Graph Isomorphism, Subgraph Isomorphism, Network Motif, Subgraph Search
PDF Full Text Request
Related items