Analysis of Unbiased and Effective Estimates for Network Motifs Frequencies by Statistical Methods of Calculating
Abstract
The article describes statistical methods for calculating network motifs frequency of occurrences. In particular, the Edge Sampling method, the method by S. Wernicke and F. Rasche, the method of random sampling of frames and the mixed method of random sampling of frames are analyzed. A comparative analysis of the quality indicators of the investigated statistical methods is done. For the mixed method of random sampling of frames, the mathematical expressions that allow obtaining consistent, unbiased, and effective estimates of frequencies for the 4-motifs are derived.
References
1. Ma’ayan А. Jenkins S. L, Neves S., Hasseldine A., Grace E., Dubin-Thaler B., Eungdamrong N. J., Weng G., Ram P. T., Rice J. J., Kershenbaum A, Stolovitzky G. A., Blitzer R. D., Iyengar R. Formation of Regulatory Patterns During Signal Propagation in a Mammalian Cellular Network // Science. 2005. Vol. 310. P. 1078–1083.
2. Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U. Network Motifs: Simple Building Blocks of Complex Networks // Science. 2002. Vol. 594, No. 298. P. 824–827.
3. Smoly I. Y. Lerman E., Ziv-Ukelson M., Yeger-Lotem E. MotifNet: A Web-Server for Network Motif Analysis // Bioinformatics. 2017. Vol. 33, No. 12. P. 1907–1909.
4. Schreiber F. Schwobbermeyer H. Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks // Transactions on Computational Systems Biology III. 2005. Vol. 3737. P. 89–104.
5. Wernicke S., Rasche F. FANMOD: a Tool for Fast Network Motif Detection // Bioinformatics. 2006. Vol. 22, No. 9. P. 1152–1153.
6. Chen J., Hsu W., Lee M. L., Ng S.-K. NeMoFinder: Dissecting Genome-Wide Protein-Protein Interactions with Meso-Scale Network Motifs // Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia, Pennsylvania, USA, 2006. P. 106–115.
7. Kashani Z. R., Ahrabian H., Elahi E., Nowzari-Dalini A., Ansari E. S., Asadi S., Mohammadi S., Schreiber F., Masoudi-Neja A. Kavosh: a New Algorithm for Finding Network Motifs // BMC Bioinformatics. 2009. No. 10. P. 318.
8. Meira L. A. A., Máximo V. R., Fazenda Á. L., da Conceição A.F. acc-Motif: Accelerated Network Motif Detection // IEEE/ACM Transactions on Computational Biology and Bioinformatics. Vol. 11, No. 5. P. 853–862.
9. Kashtan N. Itzkovitz S., Milo R., Alon U. Efficient Sampling Algorithm for Estimating Subgraph Concentrations and Detecting Network Motifs // Bioinformatics. 2004. Vol. 20, No. 11. P. 1746–1758.
10. Wernicke S. A Faster Algorithm for Detecting Network Motifs // Lecture Notes in Bioinformatics. 2005. Vol. 3692. P. 165–177.
11. Ray A., Holder L., Bifet A. Efficient Frequent Subgraph Mining on Large Streaming Graphs // Intelligent Data Analysis. 2019. Vol. 23, No. 1. P. 103–132.
12. Itzhack R., Mogilevski Y., Louzoun Y. An Optimal Algorithm for Counting Network Motifs // Physica A. 2007. Vol. 381. P. 482–490.
13. Wernicke S. Comment on “An optimal algorithm for counting networks motifs” // Physica A. 2011. Vol. 390. P. 143–145.
14. Yudina M. N. Assessment of Accuracy in Calculations of Network Motif Concentration by Rand ESU algorithm // Journal of Physics: Conference Series. 2019. Vol. 1260. P. 022012.
15. Yudin E. B., Zadorozhnyi V. N. Statistical Approach to Calculation of Number of Network Motifs // Proceedings – International Siberian Conference on Control and Communications, SIBCON. Omsk, 2015. P. 1–4.
16. Yudina M. N., Zadorozhnyi V. N., Yudin E. B. Mixed Random Sampling of Frames Method for Counting Number of Motifs // Journal of Physics: Conference Series. 2019. Vol. 1260. P. 022013.
17. Jacob P. M., Lapkin A. Statistics of the Network of Organic Chemistry // Reaction Chemistry & Engineering. 2018. No. 3. P. 102–118.
18. Menon A., Krdzavac N. B., Kraft M. From Database to Knowledge Graph – Using Data in Chemistry // Current Opinion in Chemical Engineering. 2019. Vol. 26. P. 33–37.
19. Dey A. K., Gel Y. R., Poor H. V. What Network Motifs Tell us About Resilience and Reliability of Complex Networks // Proceedings of the National Academy of Sciences. 2019. Vol. 116, No. 39. P. 19368–19373.
20. Stone L., Simberloff D., Artzy-Randrup Y. Network Motifs and Their Origins // PLoS Computational Biology. 2019. Vol, 15. No. 4. P. e1006749.
21. Jain D., Patgiri R. Network Motifs: A Survey // 3rd International Conference on Advances in Computing and Data Sciences, ICACDS 2019. Ghazibad; India; April 2019. Vol. 1046. P. 80–91.
22. Albert I., Albert R. Conserved Network Motifs Allow Protein–Protein Interaction Prediction // Bioinformatics. 2004. Vol. 20, No. 18. P. 3346–3352.
23. Müller I. E , Rubens J. R., Jun T., Graham D., Xavier R., Lu T. K. Gene Networks that Compensate for Crosstalk with Crosstalk // Nature Communications. 2019. Vol. 10. 8 p.
24. Юдина М. Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах // Омск. науч. вестн.. Сер. Приборы, машины и технологии. 2016. Т. 148, № 4. С. 161–165.
25. Юдина М. Н. Комплекс программных библиотек для анализа молекулярных сетей клетки // Омск. науч. вестн.. Сер. Приборы, машины и технологии. 2018. Т. 162, № 6. C. 265–217.
Review
For citations:
Yudina M.N. Analysis of Unbiased and Effective Estimates for Network Motifs Frequencies by Statistical Methods of Calculating. Proceedings in Cybernetics. 2019;(4 (36)):34-45. (In Russ.)
Views:
179
Email this article 