September 2009

September 17, 2009 (Thursday)

The problem I'm working on is to calculate or estimate the number of n-edge subgraph in a larger graph, which can be used for Bonferroni correction for my multiple hypothesis testing problem. I've tried to google different keywords ("counting subgraph") in order to find previous methods, and most of the previous studies are kind of related with network motif finding. In brief, I could not find efficient algorithms or tools that can solve the problem I have. In graph motif finding, in order to find over- or under-represented motifs, generally two approaches are used: (1) Explicitly enumerate all n-edge subgraph, then count the frequencies, to see which motifs are abundant or depleted. This approaches is not applicable for large motif finding because of computation time. (2) Another approach I noticed is based on sampling (here is the paper Kashtan N, Itzkovitz S, Milo R, Alon U: Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 2004, 20(11):1746-1758.). Basically, they randomly sample some subgraphs and then estimate the subgraph concentrations. Hence, this method can only estimates the relative abundance of subgraphs, but not the frequencies.