Методы извлечения k-меров и признаков из наборов метагеномных графов де Брейна на основе информации о классах образцов

Иванов Артем Борисович, Шалыто Анатолий Абрамович, Ульянцев Владимир Игоревич

doi:10.17586/2226-1494-2025-25-3-545-553

2025 , ТОМ 25, НОМЕР 3 ( май-июнь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2025-25-3-545-553

УДК 004.02

Методы извлечения k-меров и признаков из наборов метагеномных графов де Брейна на основе информации о классах образцов

Иванов А.Б., Шалыто А.А., Ульянцев В.И.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Иванов А.Б., Шалыто А.А., Ульянцев В.И. Методы извлечения k-меров и признаков из наборов метагеномных графов де Брейна на основе информации о классах образцов // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 3. С. 545–553. doi: 10.17586/2226-1494-2025-25-3-545-553

Аннотация

Введение. Рассмотрена задача сравнительного анализа наборов метагеномных образцов с использованием графов де Брейна. Для повышения точности работы классификационных моделей разработаны методы автоматического извлечения признаков на основе результатов сравнительного анализа метагеномных образцов, экспертных метаданных и статистических тестов. Под признаками в данной работе понимаются связные подграфы графа де Брейна. Методы. Первый метод unique_kmers применяется для извлечения из данных строк длины k (k-меров), которые встречаются только в образцах одного класса. Второй метод stats_kmers применяется для извлечения k-меров, частота встречаемости которых статистически отличается между классами образцов. Для извлечения интерпретируемых признаков разработан третий метод, в котором реализовано выделение подграфов из графов де Брейна на основе опорных вершин, получаемых в результате применения одного из первых двух методов. Анализ данных состоит из двух этапов: вначале применяется метод unique_kmers или stats_kmers для предварительной обработки данных, затем к полученным результатам применяется третий метод для получения интерпретируемых признаков. Основные результаты. Апробация методов проведена на четырех сгенерированных тестовых наборах данных, которые моделируют параметры реальных метагеномных сообществ, такие как наличие похожих видов (штаммов) или разницу в частоте встречаемости бактерии. Разработанные методы были применены для извлечения признаков, которые использовались для классификации образцов из тестовых наборов. Для сравнения в качестве признаков использовались результаты таксономической аннотации образцов с помощью программы Kraken2. Показано, что качество классификации образцов повысилось при применении в классификационных моделях признаков, полученных с помощью предложенных методов, по сравнению с классификационными моделями, обученными на таксономических признаках. Обсуждение. Разработанные методы полезны при сравнительном анализе данных метагеномного секвенирования и могут служить основой систем поддержки принятия решений, например, при диагностировании заболеваний людей на основе данных секвенирования микробиоты кишечника.

Ключевые слова: извлечение признаков, граф де Брейна, k-меры, классификация, метагеномика

Список литературы

Fierer N. Embracing the unknown: disentangling the complexities of the soil microbiome // Nature Reviews Microbiology. 2017. V.15. N 10. P. 579–590. https://doi.org/10.1038/nrmicro.2017.87
Garner R.E., Kraemer S.A., Onana V.E., Fradette M., Varin M.P., Huot Y., Walsh D.A. A genome catalogue of lake bacterial diversity and its drivers at continental scale // Nature Microbiology. 2023. V. 8. N 10. P. 1920–1934. https://doi.org/10.1038/s41564-023-01435-6
Huttenhower C., Gevers D., Knight R., et al. Structure, function and diversity of the healthy human microbiome // Nature. 2012. V. 486. N 7402. P. 207–214. https://doi.org/10.1038/nature11234
Olekhnovich E., Ivanov A., Babkina A., Sokolov A., Ulyantsev V., Fedorov D., Ilina E. Consistent stool metagenomic biomarkers associated with the response to melanoma immunotherapy // Msystems. 2023. V. 8. N 2. https://doi.org/10.1128/msystems.01023-22
Ivanova V., Chernevskaya E., Vasiluev P., Ivanov A., Tolstoganov I., Shafranskaya D., Ulyantsev V., Korobeynikov A., Razin S., Beloborodova N., et al. Hi-C metagenomics in the ICU: exploring clinically relevant features of gut microbiome in chronically critically ill patients // Frontiers in Microbiology. 2022. V. 12. P. 770323. https://doi.org/10.3389/fmicb.2021.770323
Olekhnovich E., Ivanov A., Ulyantsev V., Ilina E. Separation of donor and recipient microbial diversity allows determination of taxonomic and functional features of gut microbiota restructuring following fecal transplantation // Msystems. 2021. V. 6. N 4. P. e00811-21. https://doi.org/10.1128/msystems.00811-21
Lloyd-Price J., Arze C., Ananthakrishnan A.N., Schirmer M., Avila-Pacheco J., Poon T.W., Andrews E., Ajami N.J., Bonham K.S., Brislawn C.J., et al. Multi-omics of the gut microbial ecosystem in inflammatory bowel diseases // Nature. 2019. V. 569. N 7758. P. 655–662. https://doi.org/10.1038/s41586-019-1237-9
Jie Z., Xia H., Zhong S.-L., Feng Q., Li S., Liang S., Zhong H., Liu Z., Gao Y., Zhao H., et al. The gut microbiome in atherosclerotic cardiovascular disease // Nature Communications. 2017. V. 8. P. 845. https://doi.org/10.1038/s41467-017-00900-1
Yu J., Feng Q., Wong S.H., Zhang D., Liang Q., Qin Y., Tang L., Zhao H., Stenvang J., Li Y., et al. Metagenomic analysis of faecal microbiome as a tool towards targeted non-invasive biomarkers for colorectal cancer // Gut. 2017. V. 66. N 1. P. 70–78. https://doi.org/10.1136/gutjnl-2015-309800
Qin J., Li Y., Cai Z., Li S., Zhu J., Zhang F., Liang S., Zhang W., Guan Y., Shen D., et al. A metagenome-wide association study of gut microbiota in type 2 diabetes // Nature. 2012. V. 490. N 7418. P. 55–60. https://doi.org/10.1038/nature11450
Idury R.M., Waterman M.S. A new algorithm for DNA sequence assembly // Journal of Computational Biology. 1995. V. 2. N 2. P. 291–306. https://doi.org/10.1089/cmb.1995.2.291
Pevzner P.A., Tang H., Waterman M.S. An Eulerian path approach to DNA fragment assembly // Proceedings of the National Academy of Sciences of the United States of America. 2001. V. 98. N 17. P. 9748–9753. https://doi.org/10.1073/pnas.171285098
Compeau P.E., Pevzner P.A., Tesler G. How to apply de Bruijn graphs to genome assembly // Nature Biotechnology. 2011. V.29. N 11. P.987–991. https://doi.org/10.1038/nbt.2023
Компо Ф., Певзнер П. Алгоритмы биоинформатики. Москва: ДМКПресс, 2023.680 c.
Nurk S., Meleshko D., Korobeynikov A., Pevzner P.A. metaSPAdes: new versatile metagenomic assembler // Genome Research. 2017. V. 27. N 5. P. 824–834. https://doi.org/10.1101/gr.213959.116
Kolmogorov M., Bickhart D.M., Behsaz B., Gurevich A., Rayko M., Shin S.B., Kuhn K., Yuan J., Polevikov E., Smith T.P., et al. metaFlye: scalable long- read metagenome assembly using repeat graphs // Nature Methods. 2020. V. 17. N 11. P. 103–1110. https://doi.org/10.1038/s41592-020-00971-x
Bankevich A., Bzikadze A.V., Kolmogorov M., Antipov D., Pevzner P.A. Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads // Nature Biotechnology. 2022. V. 40. N 7. P. 1075–1081. https://doi.org/10.1038/s41587-022-01220-6
Meyer F., Fritz A., Deng Z.-L., Koslicki D., Lesker T.R., Gurevich A., Robertson G., Alser M., Antipov D., Beghini F., et al. Critical assessment of metagenome interpretation: the second round of challenges // Nature Methods. 2022. V. 19. N 4. P. 429–440. https://doi.org/10.1038/s41592-022-01431-4
Pereira-Marques J., Hout A., Ferreira R. M., Weber M., Pinto-Ribeiro I., Van Doorn L.-J., Knetsch C. W., Figueiredo C. Impact of host DNA and sequencing depth on the taxonomic resolution of whole metagenome sequencing for microbiome analysis // Frontiers in Microbiology. 2019. V. 10. P. 1277. https://doi.org/10.3389/fmicb.2019.01277
Marçais G., Kingsford C. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers // Bioinformatics. 2011. V. 27. N 6. P. 764–770. https://doi.org/10.1093/bioinformatics/btr011
Ondov B.D., Treangen T.J., Melsted P., Mallonee A.B., Bergman N., Koren S., Phillippy A.M. Mash: fast genome and metagenome distance estimation using MinHash // Genome Biology. 2016. V. 17. P. 132. https://doi.org/10.1186/s13059-016-0997-x
Maillet N., Collet G., Vannier T., Lavenier D., Peterlongo P. COMMET: comparing and combining multiple metagenomic datasets // Proc. of the IEEE international conference on bioinformatics and biomedicine (BIBM). 2014. P. 94–98. https://doi.org/10.1109/BIBM.2014.6999135
Rahman A., Hallgrímsdóttir I., Eisen M., Pachter L. Association mapping from sequencing reads using k-mers // Elife. 2018. V. 7. P. e32920. https://doi.org/10.7554/eLife.32920
Wang Y., Chen Q., Deng C., Zheng Y., Sun F. KmerGO: a tool to identify group-specific sequences with k-mers // Frontiers in Microbiology. 2020. V. 11. P. 2067. https://doi.org/10.3389/fmicb.2020.02067
Greenwood P.E., Nikulin M.S. A Guide to Chi-Squared Testing. John Wiley & Sons, 1996. 304 p.
Крамер Г. Математические методы статистики. М.: Институт компьютерных исследований, 2019. 648 с.
Hettmansperger T.P., McKean J.W. Robust nonparametric statistical methods. CRC press, 2010. 554 p.
Dunn O.J. Multiple comparisons among means // Journal of the American Statistical Association. 1961. V. 56. N 293. P. 52–64. https://doi.org/10.1080/016f21459.1961.10482090
Gourlé H., Karlsson-Lindsjö O., Hayer J., Bongcam-Rudloff E. Simulating Illumina metagenomic data with InSilicoSeq // Bioinformatics. 2019. V. 35.N 3. P. 521–522. https://doi.org/10.1093/bioinformatics/bty630
Wood D.E., Lu J., Langmead B. Improved metagenomic analysis with Kraken 2 // Genome Biology. 2019. V. 20. N 1. P. 257. https://doi.org/10.1186/s13059-019-1891-0
Breiman L. Random forests // Machine Learning. 2001. V. 45. N 1. P. 5–32. https://doi.org/10.1023/A:1010933404324
Pedregosa F.,Varoquaux, G., Gramfort, A., Michel, V., et al. Scikit-learn: Machine learning in Python // Journal of Machine Learning Research. 2011. V. 12. P. 2825–2830.
Buckland M., Gey F. The relationship between recall and precision // Journal of the American Society for Information Science. 1994. V. 45. N 1. P. 12–19. https://doi.org/10.1002/(sici)1097-4571(199401)45:1<12::aid-asi2>3.0.co;2-l

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