Graph querying, graph motif mining and the discovery of...

Details Graph querying, graph motif mining and the discovery of... Graph querying, graph motif mining and the discovery of...

2011-04-26

2011-04-26

Kim, Charles (Department: 2157)

Data processing: database and file management or data structures

Database and file access

Record, file, and data search and comparisons

C711S161000, C711S162000

Reexamination Certificate

active

07933915

ABSTRACT:
A method for analyzing, querying, and mining graph databases using subgraph and similarity querying. An index structure, known as a closure tree, is defined for topological summarization of a set of graphs. In addition, a significance model is created in which the graphs are transformed into histograms of primitive components. Finally, connected substructures or clusters, comprising paths or trees, are detected in networks found in the graph databases using a random walk technique and a repeated random walk technique.

REFERENCES:
Lee et al. “STRG-Index: Spatio-Temporal Region Graph indexing for Large Video Databases, SIGMOD 2005 Jun. 14-16, 2005” pp. 718-729.
Yan et al. “CloseGraph: Mining Closed Frequent Graph Patterns SIGKDD 2003 Aug. 2003 pp. 286-295”.
Weston et al. “Protein Ranking: From Local to Global Structure in the Protein Similarity Network” PNAS 27 vol. 101, No. 17, Apr. 27, 2004 pp. 6559-6563.
Sun et al. “Relevance Search and Anomaly Detection in Bipartite Graphs, SIGKDD Explorations, vol. 7, Issue 2, pp. 48-55”.
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, Oct. 2002.
Huahai He and Ambuj K. Singh. GraphRank: Statistical modeling and mining of significant subgraphs in the feature space. Technical report, department of computer science, University of California at Santa Barbara, 2006.
D. J. Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Seminaire de Probabilites XVII, pp. 243-297. 1983. Lecture Notes in Math. 986.
V. Arnau, S. Mars, and I. Marin. Iterative cluster analysis of protein interaction data. Bioinformatics, 21(3):364-378, 2005.
S. Asthana, O. D. King, F. D. Gibbons, and F. P. Roth. Predicting protein complex membership using probabilistic network reliability. Genome Research, 14:1170-1175, May 2004.
G. D. Bader and C. W. V. Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(2), 2003.
J. S. Bader. Greedily building protein networks with confidence. Bioinformatics, 19(15):1869-1874, 2003.
P. M. Bowers, M. Pellegrini, M. J. Thompson, J. Fierro, T. O. Yeates, and D. Eisenberg. Prolinks: a database of protein functional linkages derived from coevolution. Genome Biology, 5(5):R35, 2004.
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30:107-117, 1998.
T. Can, O. C, amo.glu, and A. K. Singh. Analysis of protein-protein interaction networks using random walks. In Proceedings of the 5th ACM SIGKDD Workshop on Data Mining in Bioinformatics, Chicago, Aug. 2005.
M. A. Collart. Global control of gene expression in yeast by the Ccr4—Not complex. Gene, 313:1-16, 2003.
G. M. D. Corso. Estimating an eigenvector by the power method with a random start. SIAM J. Matrix Anal. Appl., 18(4):913-937, 1997.
A. C. Gavin, M. Bosche, R. Krause, P. Grandi, M. Marzioch, A. Bauer, J. Schultz, J. M. Rick, A. M. Michon, and C. M. Cruciat. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature, 415:141-147, 2002.
Y. Ho, A. Gruhler, A. Heilbut, G. D. Bader, L. Moore, S. L. Adams, A. Millar, P. Taylor, K. Bennett, and K. Boutilier. Systematic identification of protein complexes inSaccharomyces cerevisiaeby mass spectrometry. Nature, 415:180-183, 2002.
Hu, X. Yan, Y. Huang, J. Han, and X. J. Zhou. Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics, 21(Suppl. 1):i213-i221, 2005.
T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki. A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Natl. Acad. Sci., 98:4569-4574, 2001.
R. Jansen, H. Yu, D. Greenbaum, Y. Kluger, N. J. Krogan, S. Chung, A. Emili, M. Snyder, J. F. Greenblatt, and M. Gerstein. A bayesian networks approach for predicting protein-protein interactions from genomic data. Science, 302:449-453, Oct. 2003.
G. R. G. Lanckriet, M. Deng, N. Cristianini, M. I. Jordan, and W. S. Noble. Kernel-based data fusion and its application to protein function prediction in yeast. In Proceedings of PSB, 2004.
E. Larschan and F. Winston. TheSaccharomyces cerevisiaeSrb8-Srb11 complex functions with the SAGA complex during Gal4-activated transcription. Mol Cell Biol, 25(1):114-123, 2005.
I. Lee, S. V. Date, A. T. Adai, and E. M. Marcotte. A probabilistic functional network of yeast genes. Science, 306:1555-1558, Nov. 2004.
S. Letovsky and S. Kasif. Predicting protein function from protein/protein interaction data: a probabilistic approach. Bioinformatics, 19:i197-i204, 2003.
L. Lovasz. Random walks on graphs: A survey. Combinatorics, Paul Erdos is Eighty, 2:353-398, 1996.
V. Maytal-Kivity, R. Piran, E. Pick, K. Hofmann, and M. H. Glickman. COP9 signalosome components play a role in the mating pheromone response ofS. cerevisiae. EMBO reports, 3(12):1215-1221, 2002.
H. W. Mewes, C. Amid, R. Arnold, D. Frishman, U. Guldener, G. Mannhaupt, M. Munsterkotter, P. Pagel, N. Strack, V. Stumpfien, J. Warfsmann, and A. Ruepp. MIPS: analysis and annotation of proteins from whole genomes. Nucleic Acids Research, 32:D41-D44, 2004.
A. Y. Ng, A. X. Zheng, and M. I. Jordan. Link analysis, eigenvectors, and stability. In International Joint Conference on Artificial Intelligence (IJCAI), 2001.
C. J. Roberts et al. Signaling and circuitry of multiple MAPK pathways revealed by a matrix of global gene expression profiles. Science, 287:873-880, 2000.
D. Scholtens, M. Vidal, and R. Gentleman. Local modeling of global interactome networks. Bioinformatics, 21(17):3548-3557, 2005.
H.-J. Schuller. Transcriptional control of nonfermentative metabolism in the yeastSaccharomyces cerevisiae. Curr Genet, 43:139-160, 2003.
J. Scott, T. Ideker, R. M. Karp, and R. Sharan. Efficient algorithms for detecting signaling pathways in protein interaction networks. In Proceedings of RECOMB, 2005.
K. Tsuda and W. S. Noble. Learning kernels from biological networks by maximizing entropy. Bioinformatics, 20(S1):i326-i333, 2004.
P. Uetz, G. Cagney, T. A. Mansfield, R. Judson, J. R. Knight, D. Lockshon, V. Narayan, M. Srinivasan, and P. Pochart. A comprehensive analysis of protein-protein interactions inSaccharomyces cerevisiae. Nature, 403:623-627, 2000.
C. von Mering, L. J. Jensen, B. Snel, S. D. Hooper, M. Krupp, M. Foglierini, N. Jouffre, M. A. Huynen, and P. Bork. STRING: known and predicted protein-protein associations, integrated and transferred across organisms. Nucleic Acids Research, 33:D433-D437, 2005.
C. von Mering, R. Krause, B. Snel, M. Cornell, S. G. Oliver, S. Fields, and P. Bork. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 417:399-403, May 2002.
J. Weston, A. Elisseeff, D. Zhou, C. S. Leslie, and W. S. Noble. Protein ranking: From local to global structure in the protein similarity network. Proc. Natl. Acad. Sci., 101:6559-6563, 2004.
P. Y. Wu et al. Molecular architecture of theS. cerevisiaeSAGA complex. Mol Cell, 15(2):199-208, 2004.
Y. Yamanishi, J.-P. Vert, and M. Kanehisa. Protein network inference from multiple genomic data: a supervised approach. Bioinformatics, 20(S1):i363-i370, 2004.
S. Berretti, A. D. Bimbo, and E. Vicario. Efficient matching and indexing of graph models in content-based retrieval. In IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 23, 2001.
E. Rahm and P. Bernstein. A survey of approaches to automatic schema matching. VLDB J. 10(4): 334-350 (2001).
J. Lee, J. Oh, and S. Hwang. STRG-index: Spatio-temporal region graph indexing for large video databases. In SIGMOD Conference, 2005.
KEGG. http://www.genome.ad.jp/kegg/.
National Cancer Institute. http://dtp.nci.nih.gov/.
H. Berman et al. The protein data bank. Nucleic Acids Research, (28):235-242, 2000.
S. White and P. Smyth. Algorithms for estimating relative importance in networks. In Proc. SIGKDD, 2003.
Gene Ontology. http://www.geneontology.org/.
MeSH. http://www.nlm.nih.gov/mesh/.
D.

Affiliated with

Also associated with

Rating

Graph querying, graph motif mining and the discovery of... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Graph querying, graph motif mining and the discovery of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph querying, graph motif mining and the discovery of... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2623730