More Web Proxy on the site http://driver.im/

Article

MapReduce-Based Pattern Finding Algorithm Applied in Motif Detection for Prescription Compatibility Network

Authors:

Xiaohong Jiang,

Xiangyu ZhangAuthors Info & Claims

APPT '09: Proceedings of the 8th International Symposium on Advanced Parallel Processing Technologies

Pages 341 - 355

https://doi.org/10.1007/978-3-642-03644-6_27

Published: 21 August 2009 Publication History

Abstract

Network motifs are basic building blocks in complex networks. Motif detection has recently attracted much attention as a topic to uncover structural design principles of complex networks. Pattern finding is the most computationally expensive step in the process of motif detection. In this paper, we design a pattern finding algorithm based on Google MapReduce to improve the efficiency. Performance evaluation shows our algorithm can facilitates the detection of larger motifs in large size networks and has good scalability. We apply it in the prescription network and find some commonly used prescription network motifs that provide the possibility to further discover the law of prescription compatibility.

References

[1]

Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network Motifs: Simple Building Block of Complex Networks. Science 5594, 824-827 (2002).

[2]

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979).

[3]

Dean, J., Ghemawat, S.: MapReduce: Simplified data processing on large clusters. In: ACM OSDI (2004).

[4]

Kuramochi, M., Karypis, G.: Finding Frequent Patterns in a Large Sparse Graph. In: Data Mining and Knowledge Discovery, vol. 5810, pp. 243-271. Springer, Heidelberg (2005).

[5]

Yan, X., Han, J.: gSpan: Graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, 2002. ICDM 2002. Proceedings, pp. 721-724. IEEE Press, Maebashi City (2002).

[6]

Inokucbi, A., Wasbio, T., Motoda, H.: Complete mining of frequent patterns from graphs: Mining graph data. Machine Learning 50(3), 321-354 (2003).

[7]

Hong, M., Zhou, H., Wang, W., Shi, B.: An efficient algorithm of frequent connected subgraph extraction. In: Whang, K.-Y., Jeon, J., Shim, K., Srivastava, J. (eds.) PAKDD 2003. LNCS, vol. 2637, pp. 40-51. Springer, Heidelberg (2003).

[8]

Yan, X., Hart, J.: CloseGraph: Mining closed frequent patterns. In: The 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2003), pp. 286-295. ACM, Washington (2003).

[9]

Huan, J., Wang, W., Prins, J.: Efficient mining of frequent subgraph in the presence of isomorphism. In: 2003 International Conference on Data Mining (ICDM), Melbourne, pp. 549-552. IEEE, Florida (2003).

[10]

Gudes, E., Shimony, S.E., Vanetik, N.: Discovering frequent graph patterns using disjoint paths. IEEE Transactions on Knowledge and Data Engineering 18(11), 1441-1456 (2006).

[11]

Yoshida, K., Motoda, H., Indurkhya, N.: Graph-based induction as a unified learning framework. Journal of Applied Intelligence 4, 297-328 (1994).

[12]

Cook, J., Holder, L.: Substructure discovery using minimum description length and background knowledge. J. Artificial Intelligence Research, 231-255 (1994).

[13]

Schreiber, F., Schwöbbermeyer, H.: Frequent Concepts and Pattern Detection for the Analysis of Motifs in Networks. In: Priami, C., Merelli, E., Gonzalez, P., Omicini, A. (eds.) Transactions on Computational Systems Biology III. LNCS (LNBI), vol. 3737, pp. 89-104. Springer, Heidelberg (2005).

[14]

Chen, J., Hsu, W., Lee, M.-L., Ng, S.-K.: Nemofinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs. In: KDD, pp. 106-115 (2006).

[15]

Chen, C., Yan, X., Zhu, F., Han, J.: gApprox: Mining frequent approximate patterns from a massive network. In: Perner, P. (ed.) ICDM 2007. LNCS (LNAI), vol. 4597, pp. 445-450. Springer, Heidelberg (2007).

[16]

Chu, C., Kim, S.K., Lin, Y., Yu, Y.Y., Bradski, G.: Map-Reduce for Machine Learning on Multicore. NIPS (2006).

[17]

Chang, E., Zhu, K., Wang, H., Bai, H., Li, J., Qiu, Z., Cui, H.: PSVM: Parallelizing Support Vector Machines on Distributed Computers. NIPS (2007).

[18]

Wu, Z., Zhou, X., Liu, B., Chen, J.: Text Mining for Finding Functional Community of Related Genes using TCM Knowledge. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. LNCS (LNAI), vol. 3202, pp. 459-470. Springer, Heidelberg (2004).

[19]

Ying, T., Guo-fu, Y., Gui-bing, L., Jian-ying, C.: Mining Compatibility Rules from Irregular Chinese Traditional Medicine Database by Apriori Agorithm. Journal of Southwest Jiaotong University (English Edition) 15, 288-292 (2007).

[20]

Xuezhong, Z., Zhaohui, W.: Distributional Character Clustering for Chinese Text Categorization. In: Zhang, C., Guesgen, H.W., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 575-584. Springer, Heidelberg (2004).

[21]

Xiao, H., Liang, X., Lu, P., Chan, C.: New method for analysis of Chinese herbal complex prescription and its application. Chinese Science Bulletin 44, 1164-1172 (1999).

[22]

Feng, Y., Wu, Z., Zhou, X., Zhou, Z., Fan, W.: Knowledge discovery in traditional Chinese medicine: State of the art and perspectives. Artificial Intelligence in Medicine. 38(3), 219-236 (2006).

[23]

Chang, Y.-H., Lin, H.-J., Li, W.-C.: Clinical evaluation of the traditional Chinese prescription Chi-Ju-Di-Huang-Wan for Dry Eye. Phytotherapy Research 19(4), 349-354 (2005).

[24]

Kuramochi, M., Karypis, G.: An efficient algorithm for discovering frequent subgraphs. Technical Report 02-026, Department of Computer Science, University of Minnesota (2002).

[25]

Fujing, D.: Prescription: for the Specialty of Chinese Traditional Medicine. Shanghai Publishing House of Science and Technology Press, Shanghai (2006).

Cited By

Ribeiro PParedes PSilva MAparicio DSilva F(2021)A Survey on Subgraph CountingACM Computing Surveys10.1145/343365254:2(1-36)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3433652
Peng ZWang TLu WHuang HDu XZhao FTung A(2018)Mining frequent subgraphs from tremendous amount of small graphs using MapReduceKnowledge and Information Systems10.1007/s10115-017-1104-756:3(663-690)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10115-017-1104-7
Fehér PAsztalos MVajk TMészáros TLengyel L(2017)Detecting subgraph isomorphism with MapReduceThe Journal of Supercomputing10.1007/s11227-016-1885-673:5(1810-1851)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s11227-016-1885-6
Show More Cited By

Recommendations

CMfinder---a covariance model based RNA motif finding algorithm

Motivation: The recent discoveries of large numbers of non-coding RNAs and computational advances in genome-scale RNA search create a need for tools for automatic, high quality identification and characterization of conserved RNA motifs that can be ...
In silico analysis of motifs in promoters of Differentially Expressed Genes in rice (Oryza sativa L.) under anoxia

The aim of this study was to characterise the molecular mechanisms of transcriptional regulation of Differentially Expressed Genes (DEGs) in rice coleoptiles under anoxia by identifying motifs that are common in the promoter region of co-regulated ...
A deterministic motif finding algorithm with application to the human genome

Motivation: We present a novel algorithm, MaMF, for identifying transcription factor (TF) binding site motifs. The method is deterministic and depends on an indexing technique to optimize the search process. On common yeast datasets, MaMF performs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APPT '09: Proceedings of the 8th International Symposium on Advanced Parallel Processing Technologies

August 2009

476 pages

ISBN:9783642036439

Editors:
Yong Dou
National University of Defense Technology, Department of Computer Science, Changsha, P.R.China 410073
,
Ralf Gruber
Lausanne (EPFL), Ecole Polytechnique Fédérale de ,Dépt. Physique, LAUSANNE, Switzerland 1015
,
Josef M. Joller
Technik Rapperswil, HSR - Hochschule für, RAPPERSWIL , SCHWEIZ 8640

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 August 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ribeiro PParedes PSilva MAparicio DSilva F(2021)A Survey on Subgraph CountingACM Computing Surveys10.1145/343365254:2(1-36)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3433652
Peng ZWang TLu WHuang HDu XZhao FTung A(2018)Mining frequent subgraphs from tremendous amount of small graphs using MapReduceKnowledge and Information Systems10.1007/s10115-017-1104-756:3(663-690)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10115-017-1104-7
Fehér PAsztalos MVajk TMészáros TLengyel L(2017)Detecting subgraph isomorphism with MapReduceThe Journal of Supercomputing10.1007/s11227-016-1885-673:5(1810-1851)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s11227-016-1885-6
Yan XZhang JXun YQin X(2017)A parallel algorithm for mining constrained frequent patterns using MapReduceSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1930-z21:9(2237-2249)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s00500-015-1930-z
Abdelhamid EAbdelaziz IKalnis PKhayyat ZJamour FWest J(2016)ScalemineProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014986(1-12)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014986
Talukder NZaki M(2016)A distributed approach for graph mining in massive networksData Mining and Knowledge Discovery10.1007/s10618-016-0466-x30:5(1024-1052)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10618-016-0466-x
Aridhi Sd'Orazio LMaddouri MMephu Nguifo E(2015)Density-based data partitioning strategy to approximate large-scale subgraph miningInformation Systems10.1016/j.is.2013.08.00548:C(213-223)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.is.2013.08.005
Hill SSrichandan BSunderraman RRanka SKahveci TSingh M(2012)An iterative MapReduce approach to frequent subgraph mining in biological datasetsProceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine10.1145/2382936.2383055(661-666)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2382936.2383055

View Options

View options

Figures

Tables

Media

View Table of Conten