АЛГОРИТМ КУМУЛЯТИВНОГО ВЫЧИСЛЕНИЯ СТАТИСТИКИ ПРЕДСТАВЛЕННОСТИ НАБОРА ГЕНОВ

Исследованы методы анализа представленности наборов генов, широко применяемые для анализа экспрессии генов. Рассмотрена задача кумулятивного вычисления статистики представленности. Для решения этой задачи предложен алгоритм, основанный на применении корневой эвристики. Найдена асимптотическая оценка на время работы алгоритма. Практическая реализация предложенного алгоритма показала ускорение на порядок по сравнению с «наивным» алгоритмом на типичных размерах входных данных. Применение предложенного алгоритма может значительно ускорить выполнение анализа представленности.

1. Mootha V.K., Lindgren C.M., Eriksson K.-F. et al. PGC-1 α-responsive genes involved in oxidative phosphorylation are coordinately downregulated in human diabetes // Nature Genetics. 2003. V. 34. N 3. P. 267–273. doi: 10.1038/ng1180
2. Subramanian A., Tamayo P., Mootha V.K. et al. Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles // Proceedings of the National Academy of Sciences of the United States of America. 2005. V. 102. N 43. P. 15545–15550. doi: 10.1073/pnas.0506580102
3. Maciejewski H. Gene set analysis methods: statistical models and methodological differences // Briefings in Bioinformatics. 2014. V. 15. N 4. P. 504–518. doi: 10.1093/bib/bbt002
4. Tarca A.L., Bhatti G., Romero R. A comparison of gene set analysis methods in terms of sensitivity, prioritization and specificity // PloS ONE. 2013. V. 8. N 11. P. e79217. doi: 10.1371/journal.pone.0079217
5. Yu G., Wang L.-G., Yan G.-R., He Q.-Y. DOSE: an R/Bioconductor package for disease ontology semantic and enrichment analysis // Bioinformatics. 2015. V. 31. N 4. P. 608–609. doi: 10.1093/bioinformatics/btu684
6. Väremo L., Nielsen J., Nookaew I. Enriching the gene set analysis of genome-wide data by incorporating directionality of gene expression and combining statistical hypotheses and methods // Nucleic Acids Research. 2013. V. 41. N 8. P. 4378¬–4391. doi: 10.1093/nar/gkt111
7. Fang Z. GSEAPY: Gene Set Enrichment Analysis in Python [Электронный ресурс]. – Режим доступа: https://github.com/BioNinja/gseapy, свободный. Яз. англ. (дата обращения 07.07.2016).
8. Иванов М. Sqrt-декомпозиция [Электронный ресурс]. – Режим доступа: http://e-maxx.ru/algo/sqrt_decomposition, свободный. Яз. рус. (дата обращения 07.07.2016).
9. Кормен Т. и др. Алгоритмы: построение и анализ. 2-е изд. М.: Вильямс, 2005. 1296 с.
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License