Scientific Computing Seminar

Date:

Friday, July 30, 2004

Time:

1:00pm-2:00pm

Location:

50A-5132

Seminar Speaker:

Hui Xiong
Department of Compter Science
University of Minnesota
http://www.cs.umn.edu/~huix

Title:

Hyperclique Pattern Discovery and Its Application to Protein Functional Module Extraction

Abstract:

Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of support. Also, it tends to generate too many spurious patterns involving objects which are poorly correlated. Instead, we introduce a framework for mining highly-correlated association patterns called hyperclique patterns. In this framework, an objective measure called h-confidence is applied to find hyperclique patterns. An algorithm called hyperclique miner is also proposed to exploit both cross-support and anti-monotone properties of the h-confidence measure for the efficient discovery of hyperclique patterns.

As an application of hyperclique patterns, we present a hyperclique pattern discovery approach for extracting functional modules (hyperclique patterns) from protein complexes. The analysis of hyperclique patterns using the Gene Ontology suggest that proteins within the same hyperclique pattern more likely perform the same function and participate in the same biological process. More interestingly, the 3-D structural view of proteins within a hyperclique pattern reveals that these proteins physically interact with each other. In addition, we observe that several hyperclique patterns corresponding to different functions can participate in the same protein complex as independent modules; and a hyperclique pattern can be involved in different complexes performing different higher-order biological functions. Finally, the results also indicate that our method can facilitate the functional annotation of uncharacterized proteins.

Sponsor of Seminar:

Chris Ding

Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov