procyberВестник кибернетикиProceedings in Cybernetics1999-7604Бюджетное учреждение высшего образования Ханты-Мансийского автономного округа – Югры «Сургутский государственный университет»procyber-239Research ArticleСтатьиАнализ несмещенности и эффективности оценок частот встречаемости сетевых мотивов в статистических методах расчетаAnalysis of Unbiased and Effective Estimates for Network Motifs Frequencies by Statistical Methods of CalculatingЮдинаМ. Н.YudinaM. N.mg-and-all@mail.ruОмский государственный технический университетРоссияOmsk State Technical UniversityRussian Federation20193003202004 (36)3445Copyright © Юдина М.Н., 20202020Юдина М.Н.Yudina M.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestcyber.ru/jour/article/view/239

Рассмотрены статистические методы расчета частот встречаемости сетевых мотивов, в частности метод случайного выбора ребра, метод Верника – Раше, метод случайной выборки каркасов и комбинированный метод случайной выборки каркасов. Выполнен сравнительный анализ по показателям качества исследуемых статистических методов. Для комбинированного метода случайной выборки каркасов выведены математические выражения, позволяющие получить состоятельные, несмещенные и эффективные оценки частот встречаемости 4-мотивов.

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.

статистические методы расчетасетевые мотивынесмещенные эффективные статистические оценкиstatistical methodsnetwork motifsunbiased effective statistical estimatesReferencesMa’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.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.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.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.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.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.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.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.Wernicke S., Rasche F. FANMOD: a Tool for Fast Network Motif Detection // Bioinformatics. 2006. Vol. 22, No. 9. P. 1152–1153.Wernicke S., Rasche F. FANMOD: a Tool for Fast Network Motif Detection // Bioinformatics. 2006. Vol. 22, No. 9. P. 1152–1153.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.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.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.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.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.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.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.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.Wernicke S. A Faster Algorithm for Detecting Network Motifs // Lecture Notes in Bioinformatics. 2005. Vol. 3692. P. 165–177.Wernicke S. A Faster Algorithm for Detecting Network Motifs // Lecture Notes in Bioinformatics. 2005. Vol. 3692. P. 165–177.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.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.Itzhack R., Mogilevski Y., Louzoun Y. An Optimal Algorithm for Counting Network Motifs // Physica A. 2007. Vol. 381. P. 482–490.Itzhack R., Mogilevski Y., Louzoun Y. An Optimal Algorithm for Counting Network Motifs // Physica A. 2007. Vol. 381. P. 482–490.Wernicke S. Comment on “An optimal algorithm for counting networks motifs” // Physica A. 2011. Vol. 390. P. 143–145.Wernicke S. Comment on “An optimal algorithm for counting networks motifs” // Physica A. 2011. Vol. 390. P. 143–145.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.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.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.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.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.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.Jacob P. M., Lapkin A. Statistics of the Network of Organic Chemistry // Reaction Chemistry & Engineering. 2018. No. 3. P. 102–118.Jacob P. M., Lapkin A. Statistics of the Network of Organic Chemistry // Reaction Chemistry & Engineering. 2018. No. 3. P. 102–118.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.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.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.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.Stone L., Simberloff D., Artzy-Randrup Y. Network Motifs and Their Origins // PLoS Computational Biology. 2019. Vol, 15. No. 4. P. e1006749.Stone L., Simberloff D., Artzy-Randrup Y. Network Motifs and Their Origins // PLoS Computational Biology. 2019. Vol, 15. No. 4. P. e1006749.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.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.Albert I., Albert R. Conserved Network Motifs Allow Protein–Protein Interaction Prediction // Bioinformatics. 2004. Vol. 20, No. 18. P. 3346–3352.Albert I., Albert R. Conserved Network Motifs Allow Protein–Protein Interaction Prediction // Bioinformatics. 2004. Vol. 20, No. 18. P. 3346–3352.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.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.Юдина М. Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах // Омск. науч. вестн.. Сер. Приборы, машины и технологии. 2016. Т. 148, № 4. С. 161–165.Юдина М. Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах // Омск. науч. вестн.. Сер. Приборы, машины и технологии. 2016. Т. 148, № 4. С. 161–165.Юдина М. Н. Комплекс программных библиотек для анализа молекулярных сетей клетки // Омск. науч. вестн.. Сер. Приборы, машины и технологии. 2018. Т. 162, № 6. C. 265–217.Юдина М. Н. Комплекс программных библиотек для анализа молекулярных сетей клетки // Омск. науч. вестн.. Сер. Приборы, машины и технологии. 2018. Т. 162, № 6. C. 265–217.

The authors declare that there are no conflicts of interest present.