Mining functional associated patterns from biological network data

ABSTRACT

The recent development of high-throughput biological techniques for functional genomics have generated a large quantity of new biological network data. Analyzing these networks provides novel insights in understanding basic mechanisms controlling cellular processes. In this paper, we integrate protein interaction and microarray data and transform the un-weighted protein-protein interaction network to its weighted correspondent. We then present a novel graph mining problem, mining functional associated patterns across the weighted genome-wide network. The central idea of the problem is to detect groups of objects having highly associated with each other in interaction networks, and hypothesize these groups denote function modules. We develop an efficient algorithm, MAPS, which exploits several pruning techniques to mine maximal functional associated patterns. A systematic performance study is reported on protein-protein interaction networks and gene coexpression data. The experimental results show that the proposed method is efficient and has good predictive performance.

REFERENCES

• 1: M. P. Samanta and S. Liang. Predicting protein functions from redundancies in large-scale protein interaction networks. PNAS, 100(22), 2003, 12579--12583.
• 2: C. Brun, F. Chevenet, D. Martin, J. Wojcik, A. Guenoche A, B. Jacq. Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network. Genome Biol., 5(1), 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
association mining, biological networks, weighted graphs