Метод сравнительного анализа временных серий наборов данных, заданных в виде множества строк, с использованием графов де Брейна

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

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

   Основные результаты. Разработанный метод анализа временных серий протестирован на двух типах сгенерированных метагеномных данных, заданных в виде множества строк. Показано, что метод позволяет различать геномы организмов, имеющие отличия хотя бы в одном символе на каждые 10 000 символов. Показана высокая (больше 80 %) точность и полнота результатов классификации строк при анализе моделированных сложных данных большого объема, сопоставимых с реальными данными.

   Обсуждение. Предложенный метод позволяет сравнивать метагеномные образцы, заданные в виде множества строк, используя только сами данные и не требуя дополнительной информации. Это дает возможность осуществлять более точный анализ по сравнению с существующими методами, которые сравнивают образцы на основе результатов классификации строк в базах данных таксономической аннотации. Представленные методы могут найти применение в различных областях обработки строковых данных, например для анализа изменений авторского стиля при написании серии текстов.

1. Brown P.F., Della Pietra V.J., Desouza P.V., Lai J.C., Mercer R.L. Classbased n-gram models of natural language // Computational Linguistics. 1992. V. 18. N 4. P. 467–480.

2. Cavnar W.B., Trenkle J.M. N-gram-based text categorization // Proc. of the 3^rd Annual Symposium on Document Analysis and Information Retrieval (SDAIR-94). 1994. P. 161–175.

3. Rajalakshmi R., Aravindan C. Web page classification using n-gram based URL features // Proc. of the Fifth International Conference on Advanced Computing (ICoAC). 2013. P. 15–21. doi: 10.1109/icoac.2013.6921920

4. Riseman E.M., Hanson A.R. A contextual postprocessing system for error correction using binary n-grams // IEEE Transactions on Computers. 1974. V. C-23. N 5. P. 480–493. doi: 10.1109/T-C.1974.223971

5. Sidorov G., Gupta A., Tozer M., Catala D., Catena A., Fuentes S. Rule-based system for automatic grammar correction using syntactic n-grams for English language learning (L2) // Proc. of the 17^th Conference on Computational Natural Language Learning: Shared Task. 2013. P. 96–101.

6. Barrón-Cedeño A., Rosso P. On automatic plagiarism detection based on n-grams comparison // Lecture Notes in Computer Science. 2009. V. 548. P. 696–700. doi: 10.1007/978-3-642-00958-7_69

7. Huang S., Zhang H., Bao E. A Comprehensive review of the de Bruijn graph and its interdisciplinary applications in computing // Engineered Science. 2024. V. 28. P. 1061. doi: 10.30919/es1061

8. 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. doi: 10.1089/cmb.1995.2.291

9. 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. doi: 10.1073/pnas.171285098

10. Compeau P.E.C, Pevzner P.A., Tesler G. How to apply de Bruijn graphs to genome assembly // Nature Biotechnology. 2011. V. 29. N 11. P. 987–991. doi: 10.1038/nbt.2023

11. Nurk S., Meleshko D., Korobeynikov A., Pevzner P.A. metaSPAdes: a new versatile metagenomic assembler // Genome Research. 2017. V. 27. N 5. P. 824–834. doi: 10.1101/gr.213959.116

12. Компо Ф., Певзнер П. Алгоритмы биоинформатики. М.: ДМК-Пресс, 2023. 680 с.

13. Пуассон С.Д. Исследования о вероятности приговоров в уголовных и гражданских делах. Берлин: NG Verlag, 2013. 328 c.

14. 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. doi: 10.1093/bioinformatics/bty630

15. Zou Y., Xue W., Luo G., Deng Z., Qin P., Guo R., et al. 1,520 reference genomes from cultivated human gut bacteria enable functional microbiome analyses // Nature Biotechnology. 2019. V. 37. N 2. P. 179–185. doi: 10.1038/s41587-018-0008-8

16. Ondov B.D., Treangen T.J., Melsted P., Mallonee A.B., Bergman N.H., Koren S., Phillippy A.M. Mash: fast genome and metagenome distance estimation using MinHash // Genome Biology. 2016. V. 17. P. 132. doi: 10.1186/s13059-016-0997-x

17. 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. doi: 10.1002/(SICI)1097-4571(199401)45:1<12::AID-ASI2>3.0.CO;2-L