УДК 006.72

БЫСТРОДЕЙСТВУЮЩИЙ АЛГОРИТМ ПОЛНОГЕНОМНОГО ПОИСКА АССОЦИАЦИЙ НА ОСНОВЕ АНАЛИЗА ПАР ОБЪЕКТОВ

Л.В. Уткин, И.Л. Уткина

Аннотация


Предложен простой быстродействующий алгоритм полногеномного поиска ассоциаций для оценки основного и эпистатического эффекта влияния маркеров или единичных нуклеотидных полиморфизмов (SNP). Основная идея, лежащая в основе алгоритма, заключается в сравнении генотипов пар объектов популяции и сравнении соответствующих значений фенотипа. В алгоритме используется интуитивное предположение, что изменения аллелей, соответствующих важным SNP у пары объектов, приводят к большому различию значений фенотипа этих индивидуумов. Алгоритм основан на рассмотрении пар индивидуумов вместо SNP или пар SNP. Основным преимуществом алгоритма является то, что он слабо зависит от количества SNP в матрице генотипов. В основном он зависит от количества объектов, которое, как правило, очень мало по сравнению с количеством SNP. Другое важное преимущество алгоритма заключается в том, что он позволяет без дополнительных вычислений обнаруживать эпистатический эффект, рассматриваемый как взаимодействие генов. Алгоритм также может использоваться в случае, когда фенотип принимает только два значения (схема случай–контроль). Кроме того, алгоритм может быть достаточно просто расширен с анализа двоичной матрицы генотипов на случай количественного анализа экспрессии генов. Численные эксперименты с реальными наборами данных, состоящими из популяций удвоенных гаплоидных линий ячменя, иллюстрируют преимущество предлагаемого алгоритма по сравнению со стандартными алгоритмами полногеномного поиска ассоциаций с вычислительной точки зрения, особенно для обнаружения эпистатического эффекта. Пути для повышения эффективности предлагаемого алгоритма также обсуждаются в статье.

Ключевые слова


полногеномный поиск ассоциаций; ANOVA; машинное обучение; эпистаз; SNP; метрика расстояния

Полный текст:

PDF (English)

Литература


  1. Mieth B., Kloft M., Rodríguez J.A., Sonnenburg S., Vobruba R., Morcillo-Suárez C., Farré X., Marigorta U.M., Fehr E., Dickhaus T., Blanchard G. Combining multiple hy-pothesis testing with machine learning increases the statistical power of genome-wide as-sociation studies // Scientific reports, 6, Article number: 36671, pp. 1-14, 2016.
  2. Koo C.L., Liew M.J., Mohamad M.S., Salleh A.H.M. Review for Detecting Gene-Gene Interactions Using Machine Learning Methods in Genetic Epidemiology // BioMed Re-search International, vol. 2013, Article ID 432375, 13 pages, 2013.
  3. Yang J., Lee S.H., Goddard M.E., Visscher P.M. Genome-wide complex trait analysis (GCTA): methods, data analyses, and interpretations // Genome-wide association studies and genomic prediction, pp.215-236, 2013.
  4. Korte A., Farlow A. The advantages and limitations of trait analysis with GWAS: a re-view // Plant Methods, 9(29), pp. 1-9 2013.
  5. Chandrashekar G., Sahin F. A survey on feature selection methods // Computers & Electrical Engineering, 40(1), pp. 16-28, 2014.
  6. Kim T.K. Understanding one-way ANOVA using conceptual figures // Korean Journal of Anesthesiology, 70(1), pp. 22-26, 2017.
  7. Dimou N.L., Tsirigos K.D., Elofsson A., Bagos P.G. GWAR: robust analysis and meta-analysis of genome-wide association studies // Bioinformatics, 33(10), pp. 1521-1527, 2017.
  8. Duan W., Zhao Y., Wei Y., Yang S., Bai J., Shen S., Du M., Huang L., Hu Z. A fast algo-rithm for Bayesian multi-locus model in genome-wide association studies // Molecular Genetics and Genomics, 292(4), pp. 923-934, 2017.
  9. Franberg M., Strawbridge R.J., Hamsten A. , de Faire U., Lagergren J., Sennblad B. Fast and general tests of genetic interaction for genome-wide association studies // PLOS Computational Biology, 13(6): e1005556, 2017.
  10. Wang S., He S., Yuan F., Zhu X. Tagging SNP-set selection with maximum information based on linkage disequilibrium structure in genome-wide association studies // Bioin-formatics, 33(14), pp.2078-2081, 2017.
  11. Lander E.S., Botstein D. Mapping Mendelian factors underlying quantitative traits using RFLP linkage maps // Genetics, 121(1), pp. 185-199, 1989.
  12. James G., Witten D., Hastie T., Tibshirani R. An introduction to statistical learning // Springer, New York, 2013
  13. Wray N.R., Yang J., Hayes B.J., Price A.L., Goddard M.E., Visscher P.M. Pitfalls of predicting complex traits from SNPs // Nature Reviews. Genetics, 14(7), p.507-515, 2013.
  14. Hayes B. Overview of statistical methods for genome-wide association studies (GWAS) // Methods in Molecular Biology, 1019, pp. 149-169, 2013.
  15. Visscher P.M., Wray N.R., Zhang Q., Sklar P., McCarthy M.I., Brown M.A., Yang J. 10 Years of GWAS Discovery: Biology, Function, and Translation // The American Journal of Human Genetics, 101(6), pp. 5-22, 2017.
  16. Bühlmann P. High-dimensional statistics, with applications to genome-wide association studies // EMS Surveys in Mathematical Sciences, 4(1), pp.45-75, 2017.
  17. Uppu S, Krishna A, Gopalan R. A review of machine learning and statistical approaches for detecting SNP interactions in high-dimensional genomic data // IEEE/ACM Transac-tions on Computational Biology and Bioinformatics, PP(99), pp. 1545-5963, 2016.
  18. Li J., Zhong W., Li R., Wu R. Boost: A fast algorithm for detecting gene-gene interactions in genome-wide association studies // The Annals of Applied Statistics, 8(4), pp. 2292-2318, 2014.
  19. Zhang X., Zou F., Wang W. FastANOVA: an efficient algorithm for genome-wide associ-ation study // Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 821-829. ACM, 2008.
  20. Zhang X., Zou F., Wang W. FastChi: an effcient algorithm for analyzing gene-gene inter-actions // Proceedings of the Pacific Symposium on Biocomputing, volume 14, pages 528-539. PMC, 2009.
  21. Zhang X., Pan F., Xie Y., Zou F., Wang W. COE: a general approach for efficient ge-nome-wide two-locus epistasis test in disease association study // Research in Computa-tional Molecular Biology, pages 253-269. Springer, Berlin Heidelberg, 2009.
  22. Zhang X., Huang S., Zou F., Wang W. TEAM: efficient two-locus epistasis tests in human genome-wide association study // Bioinformatics, 26(12), pp. i217-i227, 2010.
  23. Zhang Y., Liu J.S. Bayesian inference of epistatic interactions in case-control studies // Nature Genetics, 39(9), pp. 1167-1173, 2007.
  24. Li J., Malley J.D., Andrew A.S., Karagas M.R., Moore J.H. Detecting gene-gene interac-tions using a permutation-based random forest method // BioData Mining, 9(1), pp.14-30, 2016.
  25. Moore J.H., Andrews P.C. Epistasis Analysis Using Multifactor Dimensionality Reduction // Epistasis. Methods in Molecular Biology (Methods and Protocols), Humana Press, New York, NY, 2015.
  26. Bocianowski J. Estimation of epistasis in doubled haploid barley populations considering interactions between all possible marker pairs // Euphytica, 196(1), pp. 105-115, 2014.
  27. Zhou Z., Liu G., Su L. A new approach to detect epistasis utilizing parallel implementation of ant colony optimization by MapReduce framework // International Journal of Computer Mathematics, 93(3), pp. 511-523, 2016.
  28. Ma L., Clark A.G., Keinan A. Gene-based testing of interactions in association studies of quantitative traits // PLoS genetics, 9(2), pp. e1003321-12, 2013.
  29. Niel C., Sinoquet C., Dina C., Rocheleau G. A survey about methods dedicated to epista-sis detection // Frontiers in Genetics, 6, article 285, pp. 1-19, 2015
  30. Achlioptas P., Scholkopf B., Borgwardt K. Two-locus association mapping in subquadratic time // Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 726-734. ACM, 2011.
  31. Chutimanitsakun Y., Nipper R.W., Cuesta-Marcos A., Cistue L., Corey A., Filichkina T., Johnson E.A., Hayes P.M. Construction and application for QTL analysis of a restriction site associated DNA (rad) linkage map in barley // BMC Genomics, 12, pp. 4, pp. 1-13, 2011.
  32. Cistue L., Cuesta-Marcos A., Chao S., Echavarri B., Chutimanitsakun Y., Corey A., Fil-ichkina T., Garcia-Marino N., Romagosa I., Hayes P.M. Comparative mapping of the Oregon Wolfe barley using doubled haploid lines derived from female and male gametes // Theoretical and applied genetics, 122(7), pp. 1399-1410, 2011.
  33. Hayes P.M., Blake T., Chen T.H.H., Tragoonrung S., Chen F., Pan A., Liu B. Quantitative trait loci on barley (Hordeum vulgare L.) chromosome 7 associated with components of winterhardiness // Genome, 36(1), pp. 66-71, 1993.
  34. Hayes P., Chen F., Corey A., Pan A., Chen T.H., Baird E., Powell W., Thomas W., Waugh R., Bedo Z., Karsai I., Blake T., Oberthur L. The Dicktoo x Morex population // Plant Cold Hardiness, pages 77-87. Springer US, 1997.
  35. Pan A., P.M. Hayes, F. Chen, T.H.H. Chen, T. Blake, S. Wright, I. Karsai, Z. Bedo. Genetic analysis of the components of winterhardiness in barley (Hordeum vulgare L.) // Theoretical and Applied Genetics, 89(7-8), pp. 900-910, 1994.
  36. Close T.J., Bhat P.R., Lonardi S., Wu Y., Rostoks N., Ramsay L., Druka A., Stein N., Svensson J.T., Wanamaker S., Bozdag S., Roose M.L., Moscou M.J., Chao S., Varshney R.K., Szucs P., Sato K., Hayes P.M., Matthews D.E., Kleinhofs A., Muehlbauer G.J., DeYoung J., Marshall D.F., Madishetty K., Fenton R.D., Condamine P., Graner A., Waugh R. Development and implementation of high-throughput SNP genotyping in bar-ley // BMC Genomics, 10, pp. 582, pp. 1-13, 2009.
  37. Breiman L. Bagging predictors // Machine Learning, 24(2), pp. 123-140, 1996.
  38. Ho T.K. The random subspace method for constructing decision forests // IEEE Transac-tions on Pattern Analysis and Machine Intelligence, 20(8), pp. 832-844, 1998.


Лев Владимирович Уткин - д-р техн. наук, профессор, профессор кафедры телематики (при ЦНИИ РТК) института прикладной математики и механики, Санкт-Петербургский политехнический университет Петра Великого (СПбПУ).
Область научных интересов: интеллектуальный анализ данных, представление неопределенности, принятие решений при неполной информации, теория надежности, биоинформатика.
Число научных публикаций: 344.

Адрес (E-mail): lev.utkin@gmail.com
Почтовый адрес: Политехническая, 29, Санкт-Петербург, 195251
URL: http://levvu.narod.ru
Телефон: +7(812)552-6521


Ирина Львовна Уткина - магистрант, Сколковский институт науки и технологий (Сколтех), лаборант-исследователь научно-исследовательского комплекса «Нанобиотехнологии», Санкт-Петербургский политехнический университет Петра Великого (СПбПУ).
Область научных интересов: биофизика, биоинформатика, математическая статистика.
Число научных публикаций: 4.

Адрес (E-mail): ira.l.utkina@gmail.com
Почтовый адрес: Политехническая, 29, Санкт-Петербург, 195251
Телефон: +7(977)821-0425




DOI: http://dx.doi.org/10.15622/sp.58.1