Методы классификации объектов в виде наборов строковых данных с применением графов де Брейна тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Иванов Артем Борисович

• Иванов Артем Борисович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Иванов Артем Борисович

Реферат

Synopsis

Введение

Глава 1. Обзор предметной области

1.1. Большие графы в прикладных задачах анализа данных

1.2. Алгоритмы извлечения признаков из графов

1.3. Методы работы с временными сериями графов

1.4. Наборы строковых данных и графы де Брейна

1.5. Сравнительный анализ метагеномных образцов

1.5.1. Данные метагеномного секвенирования

1.5.2. Алгоритмы анализа метагеномных данных

1.6. Задача классификации метагеномных образцов

Выводы по главе

Глава 2. Методы извлечения признаков из больших графов

де Брейна с использованием метаданных об образцах

2.1. Методы извлечения признаков из графа де Брейна на основе подмножества опорных вершин

2.1.1. Метод отбора опорных вершин на основе уникальной представленности в данных

2.1.2. Метод отбора опорных вершин на основе статистически значимых различий в представленности между группами образцов

2.1.3. Метод обхода графа де Брейна и разбиения на подмножества вершин с учетом информации об опорных вершинах

2.2. Методы извлечения признаков из графа де Брейна с раскраше-

ными вершинами

2.2.1. Метод раскраски вершин графа на основе относительной частоты встречаемости к-меров в данных

2.2.2. Метод разбиения раскрашенного графа де Брейна на компоненты

2.3. Вычислительные эксперименты по применению разработанных методов для извлечения признаков из метагеномных данных

2.3.1. Валидация разработанных методов на симулированных метагеномных данных

2.3.2. Диагностирование воспалительных заболеваний кишечника у людей на основе анализа образцов микро-

биоты

2.3.3. Соревнование по метагеномной диагностике воспалительных заболеваний кишечника

2.3.4. Классификация раковых заболеваний кишечника по метагеномным образцам

Выводы по главе

Глава 3. Методы извлечения признаков и сравнительного анализа для временных серий графов

3.1. Метод извлечения признаков для детекции изменений в графе

3.2. Метод анализа наборов временных серий графов для выявления закономерностей в изменениях

3.3. Вычислительные эксперименты по применению разработанных методов для анализа временных серий графов

3.3.1. Валидация разработанных методов на симулированных метагеномных данных

3.3.2. Оценка изменений микробиоты кишечника человека

при фекальной трансплантации

Выводы по главе

Глава 4. Программное средство RECAST для анализа временных

серий графов

4.1. Реализация методов извлечения признаков и анализа временных серий графов де Брейна

4.2. Визуализация изменений в динамическом графе де Брейна для

трех временных точек

Выводы по главе

Глава 5. Программный комплекс MetaFX для классификации объектов в виде наборов строк с применением графов де Брейна и улучшения программы BandageNG

5.1. Программный комплекс MetaFX для классификации объектов

в виде наборов строк с применением графов де Брейна

5.1.1. Реализация методов построения признаков с использованием метаданных

5.1.2. Реализация методов классификации образцов на основе извлеченных признаков

5.1.3. Реализация методов анализа извлеченных признаков и интерпретации классификационных моделей

5.2. Расширение программного средства BandageNG для визуализации извлеченных признаков

Выводы по главе

Заключение

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

Список иллюстраций

Список таблиц

Приложение А. Награды автора, полученные во время работы над

диссертацией

Приложение Б. Акты внедрения результатов работы на практике

и в учебном процессе

Публикации

Реферат

Введение диссертации (часть автореферата) на тему «Методы классификации объектов в виде наборов строковых данных с применением графов де Брейна»

Общая характеристика работы

Актуальность темы исследования

Информация в цифровом виде хранится в различных форматах: в текстовых данных, в виде изображений, аудиофайлов и видеофайлов. Текстовые данные используются как для создания объектов с широким применением: литературные произведения или статьи в сети Интернет, так и для сохранения информации об объектах и их анализа в предметных областях. Такая информация сохраняется в виде наборов строк различной длины в алфавите, который содержит строчные и прописные буквы одного или нескольких языков, цифры и специальные символы. Несмотря на поддержку большого числа специальных символов в современных текстовых редакторах, многие тексты используют ограниченный набор символов. Для анализа строковых данных применяются методы, основанные на извлечении из данных и сравнении слов фиксированной длины - n-грамм (англ. n-gram) [1]. Однако их аннотация и интерпретация является сложной задачей, поэтому для повышения точности сравнительного анализа они объединяются в более крупные признаки с использованием графов.

Модели взвешенных графов применяются для анализа и прогнозирования различных состояний реального мира, например, для систем объектов со структурой, описываемой парными взаимодействиями (рассматриваются связи между двумя объектами без влияния остальных). Под взвешенным графом (англ. weighted graph) понимают граф в виде множества вершин и связывающих их ребер, где каждой вершине или ребру поставлено в соответствие число (или несколько чисел). Взвешенные графы можно разделить на неориентированные, для которых связь между парой объектов является симметричной, и ориентированными, характеризующимися направленными связями на ребрах. Оба вида графов нашли широкое применение. Так, модели ориентированных графов используют в логистике при разработке транспортных маршрутов или в эпидемиологии для моделирования распространения заболеваний. Неориентированные графы активно используются для анализа больших данных взаимодействий в социальных сетях.

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

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

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

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

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

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

ения признаков оценивать их схожесть и упростит дальнейшую обработку данных.

Структура графов, их свойства и параметры в значительной степени зависят от исходных данных и предметной области, для которой они строятся. Аналогично, в зависимости от поставленных задач по анализу данных могут различаться методы для извлечения признаков, которые затем будут использоваться для классификации объектов.

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

Метагеномика - это раздел вычислительной биологии, который изучает в совокупности сообщества микроорганизмов, населяющих определенные экологические ниши, такие как почва [2], водоемы [3], кожные покровы и кишечник человека [4]. Анализ метагеномных данных включает в себя определение видового состава образца, установление функций и роли отдельных таксонов (бактерий, вирусов) во взаимодействиях внутри сообщества и с окружающей средой, а также сравнение образцов между собой. Метагеномный анализ играет важную роль в медицине [5-11], а также используется в животноводстве [12], сельском хозяйстве [13] и экологии [14]. Сравнительная метагеномика исследует сходства и различия метагеномных образцов с целью выявления закономерностей между микробным составом и свойствами окружающей среды или хозяина, из которых данные образцы были получены, например, между образцами водоемов в разные времена года или между здоровыми и больными людьми.

Одним методом анализа метагеномных данных является сборка полных геномов с их последующей аннотацией - определением видового состава образца. Несмотря на наличие эффективных алгоритмов для сборки [15-17], которые используют построение графа де Брейна [18, 19] и разбиение его на компоненты, данная задача является сложной в связи с природой данных, их комплексностью (образец является смесью геномов многих видов) и зашумленностью. Сборка генома на 90 % из метагеномного образца требует в среднем десятикратного покрытия при секвенировании [20], но большой объем получаемых данных трудно обрабатывать, а стоимость ультраглубокого секвенирования не позволяет использовать его повсеместно. Аннотация применяется с целью установить видовой состав микроорганизмов в образце, однако она ограничена неполнотой баз данных, существующей из-за неизученной части мира микробов и их быстрой естественной эволюции в настоящем времени. При этом данные, полученные со стандартной глубиной секвенирования, позволяют обнаруживать только виды с относительной представленностью больше одного процента в образце, что приводит к потере большой доли информации о разнообразии слабо представленных

видов [21]. Другим методом анализа метагеномных данных является обработка, фильтрация, классификация и аннотация «сырых данных» - прочтений, поступающих из секвенатора. Такой метод позволяет учитывать всю извлеченную из образца информацию и не зависит от баз данных, однако требует разработки эффективных алгоритмов.

Для работы с данными секвенирования используются строковые и графовые алгоритмы. Во многих алгоритмах первым шагом при анализе прочтений является их разбиение на k-меры - подстроки фиксированной длины к (значение может варьироваться, но типичными являются значения 21 и 31). Затем из полученного множества k-меров строится граф де Брейна [18, 19]. Это ориентированный граф с петлями и мультиребрами, в котором вершинам сопоставляются k-меры, а ребра соединяют вершины, у которых суффикс длины (k-1) вершины начала ребра совпадает с префиксом длины (k-1) вершины конца ребра. Таким образом каждому ребру однозначно сопоставляется (к+1)-мер. Кроме того, такой граф является взвешенным, поскольку вместе с k-мером ребру можно присвоить численное значение - частоту встречаемости данного k-мера в исходных данных.

Графы де Брейна применяются в различных областях математики и информационных технологий: в теории информации и кодирования для генерации псевдослучайных последовательностей [22], для исправления ошибок в энергонезависимой беговой памяти (racetrack memory) [23] и для разработки шаблонов при позиционировании осязательных интерфейсов ввода [24]; в теории клеточных автоматов для определения их обратимости [25, 26]; в теории распределенных сетей для построения связей беспроводных сенсоров [27] и дизайне распределенных хэш-таблиц [28]. Однако самое масштабное применение граф де Брейна нашел в алгоритмах геномной и метагеномной сборки [15-17,29-31]. Во многих программах используется как непосредственно сама структура, так и ее вариации - сжатый граф де Брейна [32] и граф А-Брейна [33].

Сложность анализа метагеномных данных состоит также в их объеме. С одной стороны, каждый образец метагеномного секвенирования занимает 5-10 Гб дискового пространства. Помимо необходимости хранить все данные и результаты вычислений на жестком диске, работа с такими данными требует существенного объема оперативной памяти для обработки даже 100 образцов, поскольку большинство алгоритмов требует одновременной обработки всех данных для сравнительного анализа и извлечения признаков. С другой стороны, типичное число образцов в исследованиях находится в диапазоне от 100 до 200 из-за сложности сбора данных, особенно если речь идет о работе с данными метагеномов людей, например пациентов с определенным заболеванием. Таким образом, возникает проблема большого числа признаков, которые могут быть извлечены из данных, и малого числа образцов, что является критической проблемой для методов классификации объектов с помощью машинного обучения.

Поэтому актуальной является задача разработки методов классификации объектов с применением графов де Брейна, в том числе и больших (108 —1010 вер-

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

Таким образом, развитие методов классификации объектов с применением графов де Брейна для извлечения признаков приведет к ускорению обработки и повышению интерпретируемости и релевантности результатов анализа объектов в виде наборов строковых данных.

Степень разработки проблемы

Анализ графов и извлечение из них признаков используются для решения широкого спектра задач. Основы применения теории графов в социальных науках и сетевых взаимодействиях были заложены Ф. Харари [34, 35]. В работах М.В. Коломееца представлены варианты использования графов в социальных сетях для анализа социальных взаимодействий [36], мониторинга безопасности [37] и детекции пользователей-ботов [38].

Задачами кластеризации вершин графа и извлечения признаков из графовых данных занимаются многие исследователи. В работах С. Шеффер [39-41] разработаны методы кластеризации графов и извлечения локальных кластеров для больших графов, описываются области применения алгоритмов и применимость различных метрик для оценки качества получаемых кластеров. В работах [42, 43] предложены методы для извлечения признаков из наборов графов с использованием топологической сортировки вершин и метода ветвей и границ, однако их применимость показана только для графов размером меньше 50 вершин.

Теория последовательностей и графов де Брейна была разработана нидерландским математиком Н. де Брейном [44]. В дальнейшем она была применена к различным разделам дискретной математики, комбинаторики, алгебры и теории графов [45, 46]. Так, последовательности де Брейна используются для анализа регистров сдвига с линейной обратной свзяью [47-49]. В работах Э. Гамби [5052] последовательности де Брейна применяются для построения эффективных кодов в системах беспроводной передачи информации.

В работах М. Уотермана и П. Певзнера были сформулированы принципы и методология применения графов де Брейна в задачах вычислительной биологии: сборки геномов из коротких последовательностей [53-57]. Помимо сборки референсных последовательностей из геномов и метагеномов с использованием графов де Брейна, в задачах сравнения метагеномных последовательностей используются алгоритмы на основе к-меров - подстроках длины к. Некоторые алгоритмы позволяют эффективно манипулировать к-мерами и использовать их для

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

2Непротиворечие известным фактам и важность новых признаков для дальнейших исследований.

оценки похожести исходных образцов [58-60]. Другие алгоритмы используют статистические тесты для отбора подмножества к-меров, ключевых для разбиения исходных образцов на категории [61, 62]. Однако данные методы позволяют только провести сравнение образцов, но не включают дальнейшую интерпретацию полученных признаков, что ограничивает возможности их использования для анализа биологических и медицинских данных.

к-меры используются не только в области вычислительной биологии. Для данных, которые представляются в виде множества строк, например текстов, используются методы сравнения, основанные на разбиении текста на слова фиксированной длины - п-граммы (англ. п^гат) [1]. Они являются обобщением для к-меров и используются при работе с данными в виде текстов на естественном языке. п-граммы применяются для сравнения текстов [63], ранжирования документов в сети Интернет [64], исправления опечаток [65, 66] и обнаружения плагиата [67]. Однако интерпретация признаков в виде п-грамм является сложной задачей в связи с их короткой длиной (как правило, от двух до 10 символов). Отдельные п-граммы не обладают смыслом с точки зрения естественного языка. Однако если с помощью графов де Брейна объединить п-граммы в более длинные последовательности, то можно получить признаки, осмысленные с точки зрения предметной области, например, ключевые слова или словосочетания.

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

Извлекаемые признаки в значительной степени влияют на дальнейший анализ и результаты работы классификационных моделей [68]. Оценка вклада каждого признака в результирующую точность модели может производиться с помощью информационных критериев (дивергенция Кульбака-Лейблера [69], индекс Джини-Симпсона [70]) при работе с деревьями решений и их композициями. Также для оценки важности признака может использоваться теоретико-игровой подход [71]. Кроме отбора признаков на основе их значимости, используются методы построения признаков в виде комбинаций исходных признаков [72-74]. Однако, для составления новых признаков в виде композиций исходных признаков требуется перебор функций (линейные, полиномиальные, экспоненциальные) и их параметров. В то же время комбинации признаков могут быть невалидными с точки зрения предметной области и затруднять интерпретируемость модели.

На момент начала исследований автором (в 2019 году) не существовало методов классификации объектов в виде наборов строковых данных, основанных на извлечении признаков из больших графов де Брейна, которые сочетали бы в себе использование метаданных на этапе построения признаков и интерпретируемость извлекаемых признаков в соответствии с предметной областью исследования. К концу диссертационного исследования появился пример извлечения признаков и определения взаимодействий между структурами РНК [75] на основе использования графа де Брейна, однако данный подход использует граф специального вида, который не позволяет обобщить решение и интерпретировать получаемые результаты в общем случае.

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

Для достижения цели в диссертации решаются следующие задачи:

- исследование текущего состояния предметной области, уточнение задачи и способов оценки результатов;

- формализация постановки задачи извлечения признаков из графа де Брейна;

- разработка методов извлечения признаков из графа де Брейна с учетом метаданных об образцах, которые могут быть использованы на этапе построения и анализа графа;

- разработка метода извлечения признаков для анализа динамических графов в виде серий графов, полученных как мгновенные снимки состояния графа в определенные моменты времени;

- проектирование и реализация программного комплекса, включающего разработанные методы извлечения признаков для анализа динамических графов в виде серий графов;

- проектирование и реализация программного комплекса, включающего разработанные методы извлечения признаков с учетом метаданных и модели машинного обучения для классификации образцов из наборов данных, заданных множеством строк;

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

Теоретическая значимость работы определяется расширением набора методов извлечения признаков из статических и динамических графов де Брейна с использованием не только самой структуры графов, но и дополнительных метаданных об исследуемых образцах, которые могут быть сопоставлены с графом. Полученные методы применимы для анализа наборов (до 100) больших (миллиарды вершин) графов де Брейна.

Практическую значимость работы определяют:

- открытый код разработанного программного комплекса MetaFX, который доступен к переиспользованию по адресу https://github.com/ctlab/metafx;

- применимость разработанных методов для анализа метагеномных данных;

- апробация разработанного метода извлечения признаков для оценки его применимости при диагностировании заболеваний человека по анализу микробиоты кишечника;

- внедрение результатов в научно-исследовательскую работу в ФГБУ ФНКЦ ФХМ ИМ. Ю.М. ЛОПУХИНА ФМБА РОССИИ при выполнении проекта РНФ «Микробиота кишечника и ответ на иммунотерапию злокачественных опухолей: от воспроизводимых биомаркеров к модуляции эффекта» для улучшения качества предсказания ответа на иммунотерапию злокачественных опухолей по анализу данных метагеномного секвенирования;

- использование результатов в учебном процессе в Институте биоинформатики для улучшения качества подготовки специалистов в областях разработки программного обеспечения, анализа данных и биоинформатики;

- использование результатов в учебном процессе в магистратуре Университета ИТМО «Биоинформатика и системная биология» для улучшения качества подготовки специалистов в областях анализа больших данных и разработки программного обеспечения.

Положения, выносимые на защиту, обладающие научной новизной, а также имеющие важное практическое значение:

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

2. Метод классификации изменений в наборах строковых данных, представленных графом де Брейна, отличающийся тем, что с целью повышения точности анализа динамики процессов, представленных этими наборами данных, применяется попарное сравнение образцов на уровне указанных графов.

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

Научной новизной обладают первые два положения, а третье - имеет важное практическое значение.

Методы исследования. В работе использованы методы анализа графов, методы теории вероятности и математической статистики, методы машинного обучения и методы проведения экспериментальных исследований.

Достоверность научных результатов обусловлена корректным использованием методов, обоснованием постановки задач, экспериментальными исследованиями разработанных и реализованных методов. Результаты классификации метагеномных образцов, полученные разработанными методами на сгенерированных тестовых данных, согласуются с исходным разбиением образцов на классы. Результаты, полученные на реальных данных, согласуются также с опубликованными ранее исследованиями [76-83].

Соответствие паспорту специальности.

Диссертация соответствует двум пунктам паспорта специальности 2.3.8. «Информатика и информационные процессы (технические науки)»:

Седьмой пункт паспорта специальности: «Разработка методов обработки, группировки и аннотирования информации, в том числе, извлеченной из сети интернет, для систем поддержки принятия решений, интеллектуального поиска, анализа». Были разработаны, обоснованы и протестированы методы извлечения признаков для анализа наборов данных, заданных множеством строк, на основе результатов обработки и аннотирования информации с помощью экспертных метаданных расположенных в базах данных в сети интернет. Извлекаемые признаки используются при обучении классификационных моделей для определения категории объектов, например для определения статуса пациента при анализе метагеномных данных, и могут использоваться при построении рекомендательной системы принятия медицинских решений.

Тринадцатый пункт паспорта специальности: «Разработка и применение методов распознавания образов, кластерного анализа, нейро-сетевых и нечетких технологий, решающих правил, мягких вычислений при анализе разнородной информации в базах данных». Был разработан программный комплекс, который использует методы кластерного анализа и решающих правил, для анализа и классификации объектов, заданных множеством строк. При этом для извлечения признаков используется разнородная информация об объектах: строковые последовательности и табличные метаданные о численных и категориальных признаках.

Список литературы диссертационного исследования кандидат наук Иванов Артем Борисович, 2025 год

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

1. Brown P. F., Della Pietra V. J., Desouza P. V., Lai J. C., Mercer R. L. Class-based n-gram models of natural language // Computational linguistics. 1992. Т. 18, № 4. С. 467-480.

2. Fierer N. Embracing the unknown: disentangling the complexities of the soil microbiome // Nature Reviews Microbiology. 2017. Т. 15, № 10. С. 579-590.

3. 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. Т. 8, № 10. С. 1920-1934.

4. Human Microbiome Project Consortium . Structure, function and diversity of the healthy human microbiome // Nature. 2012. Т. 486, № 7402. С. 207-214.

5. 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. Т. 8, № 2. e01023-22.

6. Ivanova V., Chernevskaya E., Vasiluev P., Ivanov A., Tolstoganov I., Shafranskaya D., Ulyantsev V., Korobeynikov A., Razin S., Beloborodova N. [и др.]. Hi-CmetagenomicsintheICU: exploring clinically relevant features of gut microbiome in chronically critically ill patients // Frontiers in microbiology. 2022. Т. 12. С. 770323.

7. 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. Т. 6, № 4. С. 10-1128.

8. Lloyd-Price J., Arze C., Ananthakrishnan A. N., Schirmer M., Avila-Pacheco J., Poon T. W.,AndrewsE.,AjamiN. J.,BonhamK. S.,Brislawn C. J. [и др.]. Multi-omics of the gut microbial ecosystem in inflammatory bowel diseases // Nature. 2019. Т. 569, № 7758. С. 655-662.

9. Jie Z., Xia H., Zhong S.-L., Feng Q., Li S., Liang S., Zhong H., Liu Z., Gao Y., Zhao H. [и др.]. The gut microbiome in atherosclerotic cardiovascular disease // Nature communications. 2017. Т. 8, № 1. С. 845.

10. Yu J., Feng Q., Wong S. H., Zhang D., Liang Q. yi, Qin Y., Tang L., Zhao H., Stenvang J., Li Y [и др.]. Metagenomic analysis of faecal microbiome as a tool towards targeted non-invasive biomarkers for colorectal cancer // Gut. 2017. Т. 66, № 1. С. 70-78.

11. Qin J., Li Y, Cai Z., Li S., Zhu J., Zhang F., Liang S., Zhang W., Guan Y., Shen D. [и др.]. A metagenome-wide association study of gut microbiota in type 2 diabetes // Nature. 2012. Т. 490, № 7418. С. 55-60.

12. Li F, Hitch T. C., Chen Y, Creevey C. J., Guan L. L. Comparative metagenomic and metatranscriptomic analyses reveal the breed effect on the rumen microbiome and its associations with feed efficiency in beef cattle // Microbiome. 2019. Т. 7. С. 1-21.

13. Clagnan E., Costanzo M., Visca A., Di Gregorio L., Tabacchioni S., Colantoni E., Sevi F., Sbarra F., Bindo A., Nolfi L. [и др.]. Culturomics-and metagenomics-based insights into the soil microbiome preservation and application for sustainable agriculture // Frontiers in Microbiology. 2024. Т. 15. С. 1473666.

14. Guo J., Li J., Chen H., Bond P. L., Yuan Z. Metagenomic analysis reveals wastewater treatment plants as hotspots of antibiotic resistance genes and mobile genetic elements // Water research. 2017. Т. 123. С. 468-478.

15. Nurk S., Meleshko D., Korobeynikov A., Pevzner P. A. metaSPAdes: a new versatile metagenomic assembler// Genome research. 2017. Т. 27, № 5. С. 824834.

16. Kolmogorov M., Bickhart D. M., Behsaz B., Gurevich A., Rayko M., Shin S. B., Kuhn K., Yuan J., Polevikov E., Smith T. P. [и др.]. metaFlye: scalable long-read metagenome assembly using repeat graphs // Nature Methods. 2020. Т. 17, № 11. С. 1103-1110.

17. 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. Т. 40, № 7. С. 1075-1081.

18. Huang S., Zhang H., Bao E. A Comprehensive Review of the de Bruijn Graph and Its Interdisciplinary Applications in Computing // Engineered Science. 2023. Т. 28. С. 1061.

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

20. Meyer F., Fritz A., Deng Z.-L., Koslicki D., Lesker T. R., Gurevich A., Robertson G., Alser M., Antipov D., Beghini F. [и др.]. Critical assessment of metagenome interpretation: the second round of challenges // Nature methods. 2022. Т. 19, № 4. С. 429-440.

21. 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. Т. 10. С. 1277.

22. Yang B., Mandal K., Aagaard M. D., Gong G. Efficient composited de Bruijn sequence generators // IEEE Transactions on Computers. 2017. Т. 66, № 8. С. 1354-1368.

23. Parkin S. S., Hayashi M., Thomas L. Magnetic domain-wall racetrack memory // science. 2008. T. 320, № 5873. C. 190-194.

24. Makarov D. A., Yashunsky A. On a construction of easily decodable sub-de Bruijn arrays // Journal of Applied and Industrial Mathematics. 2019. T. 13. C. 280-289.

25. Wolfram S. Computation theory of cellular automata // Communications in mathematical physics. 1984. T. 96, № 1. C. 15-57.

26. Sutner K. De Bruijn graphs and linear cellular automata // Complex Systems. 1991. T. 5, № 1. C. 19-30.

27. Lu C., Hu D. A fault-tolerant routing algorithm for wireless sensor networks based on the structured directional de Bruijn graph // Cybernetics and Information Technologies. 2016. T. 16, № 2. C. 46-59.

28. Datta A., Girdzijauskas S., Aberer K. On de Bruijn routing in distributed hash tables: there and back again // Proceedings. Fourth International Conference on Peer-to-Peer Computing, 2004. Proceedings. IEEE. 2004. C. 159-166.

29. Mahadik K., Wright C., Kulkarni M., Bagchi S., Chaterji S. Scalable genomic assembly through parallel de bruijn graph construction for multiple k-mers // Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics. 2017. C. 425-431.

30. Rautiainen M., Marschall T. MBG: Minimizer-based sparse de Bruijn Graph construction //Bioinformatics. 2021. T. 37, № 16. C. 2476-2478.

31. Ekim B., Berger B., Chikhi R. Minimizer-space de Bruijn graphs: Whole-genome assembly of long reads in minutes on a personal computer // Cell systems. 2021. T. 12, № 10. C. 958-968.

32. Li D., Liu C.-M, Luo R., Sadakane K., Lam T.-W. MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph // Bioinformatics. 2015. T. 31, № 10. C. 1674-1676.

33. Pevzner P. A., Tang H., Tesler G. De novo repeat classification and fragment assembly // Proceedings of the eighth annual international conference on Research in computational molecular biology. 2004. C. 213-222.

34. Harary F., Norman R. Z. Graph theory as a mathematical model in social science. 1953.

35. Barnes J. A., Harary F. Graph theory in network analysis // Social networks. 1983. T. 5, № 2. C. 235-244.

36. Kolomeets M., Chechulin A., Kotenko I. V. Social networks analysis by graph algorithms on the example of the VKontakte social network. // J. Wirel. Mob. Networks Ubiquitous Comput. Dependable Appl. 2019. T. 10, № 2. C. 55-75.

37. Kolomeec M., Chechulin A., Pronoza A., Kotenko I. V. Technique of Data Visualization: Example of Network Topology Display for Security Monitoring. // J. Wirel. Mob. Networks Ubiquitous Comput. Dependable Appl. 2016. T. 7, № 1. C. 58-78.

38. Kolomeets M., Chechulin A., Kotenko I. V. Bot detection by friends graph in social networks. // J. Wirel. Mob. Networks Ubiquitous Comput. Dependable Appl. 2021. T. 12, № 2. C. 141-159.

39. Schaeffer S. E. Stochastic local clustering for massive graphs // Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer. 2005. C. 354360.

40. Sima J., Schaeffer S. E. On the NP-completeness of some graph cluster measures // International Conference on Current Trends in Theory and Practice of Computer Science. Springer. 2006. C. 530-537.

41. Schaeffer S. E. Graph clustering // Computer science review. 2007. T. 1, № 1. C. 27-64.

42. Yan X., Han J. gspan: Graph-based substructure pattern mining // 2002 IEEE International Conference on Data Mining, 2002. Proceedings. IEEE. 2002. C. 721-724.

43. Kong X., Yu P. S. Semi-supervised feature selection for graph classification // Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010. C. 793-802.

44. De Bruijn N. G. A combinatorial problem // Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam. 1946. T. 49, № 7. C. 758-764.

45. Ralston A. De Bruijn sequences—a model example of the interaction of discrete mathematics and computer science // Mathematics Magazine. 1982. T. 55, № 3. C. 131-143.

46. Rosenfeld V. R. Enumerating de Bruijn sequences // MATCH Communications in Mathematical and in Computer Chemistry. 2002. T. 45. C. 71-83.

47. Li M., Lin D. De Bruijn sequences, adjacency graphs, and cyclotomy // IEEE Transactions on Information Theory. 2017. T. 64, № 4. C. 2941-2952.

48. Chee Y. M., Etzion T., Kiah H. M., Marcovich S., Vardy A., Yaakobi E. [h gp.]. Locally-constrained de Bruijn codes: Properties, enumeration, code constructions, and applications // IEEE Transactions on Information Theory. 2021. T. 67, № 12. C. 7857-7875.

49. Li M., Lin D. Partial cycle structure of FSRs and its applications in searching de Bruijn sequences // IEEE Transactions on Information Theory. 2022. T. 69, № 1. C. 598-609.

50. Warty C., Mattigiri S., Gambi E., Spinsante S. De Bruijn sequences as secure spreading codes for wireless communications //2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI). IEEE. 2013. C. 315-320.

51. Spinsante S., Andrenacci S., Gambi E. Binary De Bruijn sequences for DS-CDMA systems: analysis and results // EURASIP Journal on Wireless Communications and Networking. 2011. T. 2011. C. 1-12.

52. Andrenacci S., Gambi E., Pelliccioni G., Spinsante S. De Bruijn sequences analysis through ambiguity functions in a deep-space communication scenario // 2012 IEEE Aerospace Conference. IEEE. 2012. C. 1-10.

53. Idury R. M., Waterman M. S. A new algorithm for DNA sequence assembly // Journal of computational biology. 1995. T. 2, № 2. C. 291-306.

54. Pevzner P. A., Tang H., Waterman M. S. An Eulerian path approach to DNA fragment assembly // Proceedings of the national academy of sciences. 2001. T. 98, № 17. C. 9748-9753.

55. Chaisson M. J., Pevzner P. A. Short read fragment assembly of bacterial genomes // Genome research. 2008. T. 18, № 2. C. 324-330.

56. Compeau P. E., Pevzner P. A., Tesler G. How to apply de Bruijn graphs to genome assembly // Nature biotechnology. 2011. T. 29, № 11. C. 987-991.

57. Bankevich A., Nurk S., Antipov D., Gurevich A. A., Dvorkin M., Kulikov A. S., Lesin V. M., Nikolenko S. I., Pham S., Prjibelski A. D. [h gp.]. SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing // Journal of computational biology. 2012. T. 19, № 5. C. 455-477.

58. Margais G., Kingsford C. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers // Bioinformatics. 2011. T. 27, № 6. C. 764770.

59. 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. T. 17. C. 1-14.

60. Maillet N., Collet G., Vannier T., Lavenier D., Peterlongo P. COMMET: comparing and combining multiple metagenomic datasets // 2014 IEEE international conference on bioinformatics and biomedicine (BIBM). IEEE. 2014. C. 94-98.

61. Rahman A., Hallgrimsdottir I., Eisen M., Pachter L. Association mapping from sequencing reads using k-mers // Elife. 2018. T. 7. e32920.

62. 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. T. 11. C. 2067.

63. Cavnar W. B., Trenkle J. M. [и др.]. N-gram-based text categorization // Proceedings of SDAIR-94, 3rd annual symposium on document analysis and information retrieval. Т. 161175. Ann Arbor, Michigan. 1994. С. 14.

64. RajalakshmiR., Aravindan C. Web page classification using n-gram based URL features //2013 fifth international conference on advanced computing (ICoAC). IEEE. 2013. С. 15-21.

65. Riseman E. M., Hanson A. R. A contextual postprocessing system for error correction using binary n-grams // IEEE Transactions on Computers. 1974. Т. 100, № 5. С. 480-493.

66. 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) // Proceedings of the Seventeenth Conference on Computational Natural Language Learning: Shared Task. 2013. С. 96-101.

67. Barron-Cedeno A., Rosso P. On automatic plagiarism detection based on n-grams comparison // Advances in Information Retrieval: 31th European Conference on IR Research, ECIR 2009, Toulouse, France, April 6-9, 2009. Proceedings 31. Springer. 2009. С. 696-700.

68. Karabulut E. M., Ozel S. A., Ibrikci T. A comparative study on the effect of feature selection on classification accuracy // Procedia Technology. 2012. Т. 1.

С. 323-327.

69. Kullback S. Information theory and statistics. Courier Corporation, 1997.

70. Jost L. Entropy and diversity // Oikos. 2006. Т. 113, № 2. С. 363-375.

71. Lundberg S. M., Lee S.-I. A Unified Approach to Interpreting Model Predictions // Advances in Neural Information Processing Systems 30 / под ред. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett. Curran Associates, Inc., 2017. С. 4765-4774. URL: http: //papers. nips. cc/paper/7062 - a-unified- approach-to - interpreting -model-predictions.pdf.

72. Rodriguez-Lujan I., Huerta R., Elkan C., Cruz C. S. Quadratic programming feature selection // The Journal of Machine Learning Research. 2010. Т. 11. С. 1491-1516.

73. Li Z., Yang Y., Liu J., Zhou X., Lu H. Unsupervised feature selection using nonnegative spectral analysis // Proceedings of the AAAI conference on artificial intelligence. Т. 26. 2012. С. 1026-1032.

74. Guyon I., Weston J., Barnhill S., Vapnik V. Gene selection for cancer classification using support vector machines // Machine learning. 2002. Т. 46. С. 389-422.

75. Wei Y., Zhang Q., Liu L. The improved de Bruijn graph for multitask learning: predicting functions, subcellular localization, and interactions of noncoding RNAs //Briefings inBioinformatics. 2025. Т. 26, № 1. bbae627.

76. O'Riordan K. J., Collins M. K., Moloney G. M., Knox E. G., Aburto M. R., Fulling C., Morley S. J., Clarke G., Schellekens H., Cryan J. F. Short chain fatty acids: microbial metabolites for gut-brain axis signalling // Molecular and Cellular Endocrinology. 2022. Т. 546. С. 111572.

77. Becker A., Schmartz G. P, Groger L., Grammes N., Galata V.'., Philippeit H., Weiland J., Ludwig N., Meese E., Tierling S. [и др.]. Effects of resistant starch on symptoms, fecal markers, and gut microbiota in Parkinson's disease—the RESISTA-PD trial // Genomics, Proteomics and Bioinformatics. 2022. Т. 20, № 2. С. 274-287.

78. Teh J., Berendsen E., Hoedt E., Kang S., Zhang J., Zhang F., Liu Q., Hamilton A., Wilson-O'Brien A., ChingJ. [и др.]. Novel strain-level resolution of Crohn's disease mucosa-associated microbiota via an ex vivo combination of microbe culture and metagenomic sequencing // The ISME Journal. 2021. Т. 15, № 11. С. 3326-3338.

79. Santiago A., Hann A., Constante M., Rahmani S., Libertucci J., Jackson K., Rueda G., Rossi L., Ramachandran R., Ruf W. [и др.]. Crohn's disease proteolytic microbiota enhances inflammation through PAR2 pathway in gnotobiotic mice // Gut Microbes. 2023. Т. 15, № 1. С. 2205425.

80. MaX., Lu X., Zhang W., Yang L., Wang D, Xu J., Jia Y., Wang X., Xie H., Li S. [и др.]. Gut microbiota in the early stage of Crohn's disease has unique characteristics // Gut Pathogens. 2022. Т. 14, № 1. С. 46.

81. Siddiqui M. T., Cresci G. A. The immunomodulatory functions of butyrate // Journal of inflammation research. 2021. С. 6025-6041.

82. Guzior D. V., Quinn R. A. Microbial transformations of human bile acids // Microbiome. 2021. Т. 9, № 1. С. 140.

83. Ha C. W., Martin A., Sepich-Poore G. D., Shi B., Wang Y., Gouin K., Humphrey G., Sanders K., Ratnayake Y., Chan K. S. [и др.]. Translocation of viable gut microbiota to mesenteric adipose drives formation of creeping fat in humans // Cell. 2020. Т. 183, № 3. С. 666-683.

84. Харари Ф. Теория графов // Издательство Мир. 1973.

85. Guze S. Graph theory approach to the vulnerability of transportation networks // Algorithms. 2019. Т. 12, № 12. С. 270.

86. Chang L., NiuX, Liu T., Tang J., Qian C. GNSS/INS/LiDAR-SLAM integrated navigation system based on graph optimization//Remote Sensing. 2019. Т. 11, № 9. С. 1009.

87. Naazare M., Ramos D., Wildt J., Schulz D. Application of graph-based path planning for UAVs to avoid restricted areas // 2019 IEEE international symposium on safety, security, and rescue robotics (SSRR). IEEE. 2019. С. 139-144.

88. RawatR., Mahor V., Chirgaiya S., RathoreA. S. Applications of social network analysis to managing the investigation of suspicious activities in social media platforms // Advances in Cybersecurity Management. Springer, 2021. C. 315— 335.

89. Wilson C., Sala A., Puttaswamy K. P, Zhao B. Y. Beyond social graphs: User interactions in online social networks and their implications // ACM Transactions on the Web (TWEB). 2012. T. 6, № 4. C. 1-31.

90. Lerman K., Hogg T. Using a model of social dynamics to predict popularity of news // Proceedings of the 19th international conference on World wide web. 2010. C. 621-630.

91. Alguliyev R., Aliguliyev R., Yusifov F. Graph modelling for tracking the COVID-19 pandemic spread // Infectious disease modelling. 2021. T. 6. C. 112-122.

92. Netrapalli P, Sanghavi S. Learning the graph of epidemic cascades // ACM SIGMETRICS Performance Evaluation Review. 2012. T. 40, № 1. C. 211-222.

93. Loboda A. A., Artyomov M. N., Sergushichev A. A. Solving generalized maximum-weight connected subgraph problem for network enrichment analysis // Algorithms in Bioinformatics: 16th International Workshop, WABI 2016, Aarhus, Denmark, August 22-24, 2016. Proceedings 16. Springer. 2016. C. 210-221.

94. Emelianova M., Gainullina A., Poperechnyi N., Loboda A., Artyomov M., Sergushichev A. Shiny GATOM: omics-based identification of regulated metabolic modules in atom transition networks // Nucleic acids research. 2022. T. 50, W1. W690-W696.

95. Iturria-Medina Y., Sotero R. C., Canales-Rodríguez E. J., Alemán-Gómez Y., Melie-García L. Studying the human brain anatomical network via diffusion-weighted MRI and Graph Theory // Neuroimage. 2008. T. 40, № 3. C. 10641076.

96. YuQ., DuY., Chen J., SuiJ., Adale T., Pearlson G. D., Calhoun V.D. Application of graph theory to assess static and dynamic brain connectivity: Approaches for building brain graphs // Proceedings of the IEEE. 2018. T. 106, № 5. C. 886906.

97. Saraiya P, Lee P, North C. Visualization of graphs with associated timeseries data // IEEE Symposium on Information Visualization, 2005. INFOVIS 2005. IEEE. 2005. C. 225-232.

98. Lacasa L., Luque B., Ballesteros F., Luque J., Nuno J. C. From time series to complex networks: The visibility graph // Proceedings of the National Academy of Sciences. 2008. T. 105, № 13. C. 4972-4975.

99. Stephen M., Gu C., Yang H. Visibility graph based time series analysis // PloS one. 2015. T. 10, № 11. e0143015.

100. Mishra K., Basu S., Maulik U. Graft: A graph based time series data mining framework // Engineering Applications of Artificial Intelligence. 2022. T. 110. C. 104695.

101. Lee J. D., Maggioni M. Multiscale analysis of time series of graphs // International Conference on Sampling Theory and Applications (SampTA). Citeseer. 2011.

102. Shoubridge P, KraetzlM., Wallis W., Bunke H. Detection of abnormal change in a time series of graphs // Journal of Interconnection Networks. 2002. T. 3, 01n02. C. 85-101.

103. Tamames J., Cobo-Simón M., Puente-Sánchez F. Assessing the performance of different approaches for functional and taxonomic annotation of metagenomes//BMCgenomics. 2019. T. 20. C. 1-16.

104. Maimon O. Z., Rokach L. Data mining with decision trees: theory and applications. T. 81. World scientific, 2014.

105. Matthews B. W. Comparison of the predicted and observed secondary structure of T4 phage lysozyme // Biochimica et Biophysica Acta (BBA)-Protein Structure. 1975. T. 405, № 2. C. 442-451.

106. Khachatryan L., Xiang Y., Ivanov A., Glaab E., Graham G., Granata I., Giordano M., Maddalena L., Piccirillo M., Manipur I. [h gp.]. Results and lessons learned from the sbv IMPROVER metagenomics diagnostics for inflammatory bowel disease challenge // Scientific Reports. 2023. T. 13, № 1. C. 6303.

107. Wood D. E., LuJ., Langmead B. Improved metagenomic analysis with Kraken 2 // Genome biology. 2019. T. 20. C. 1-13.

108. Franzosa E. A., Sirota-Madi A., Avila-Pacheco J., Fornelos N., Haiser H. J., Reinker S., Vatanen T., Hall A. B., Mallick H., McIver L. J. [h gp.]. Gut microbiome structure and metabolic activity in inflammatory bowel disease // Nature microbiology. 2019. T. 4, № 2. C. 293-305.

109. Lo Sasso G., Khachatryan L., Kondylis A., Battey J. N., Sierro N., Danilova N. A., Grigoryeva T. V., Markelova M. I., Khusnutdinova D. R., Laikov A. V. [h gp.]. Inflammatory bowel disease-associated changes in the gut: focus on Kazan patients // Inflammatory bowel diseases. 2021. T. 27, № 3. C. 418-433.

110. The Integrative HMP (iHMP) Research Network Consortium. The Integrative Human Microbiome Project // Nature. 2019. T. 569, № 7758. C. 641-648.

111. Goloshchapov O. V., Olekhnovich E. I., Sidorenko S. V., Moiseev I. S., Kucher M. A., Fedorov D. E., Pavlenko A. V., Manolov A. I., Gostev V. V., Veselovsky V. A. [h gp.]. Long-term impact of fecal transplantation in healthy volunteers //BMC microbiology. 2019. T. 19. C. 1-13.

112. Lee S. T., Kahn S. A., Delmont T. O., Shaiber A., Esen O. C., Hubert N. A., Morrison H. G., Antonopoulos D. A., Rubin D. T., Eren A. M. Tracking microbial colonization in fecal microbiota transplantation experiments via genome-resolved metagenomics//Microbiome. 2017. T. 5. C. 1-10.

113. VriezeA., Van NoodE., Holleman F., SalojarviJ., KootteR. S., BartelsmanJ. F., Dallinga-Thie G. M., Ackermans M. T., Serlie M. J., Oozeer R. [h gp.]. Transfer of intestinal microbiota from lean donors increases insulin sensitivity in individuals with metabolic syndrome // Gastroenterology. 2012. T. 143, № 4. C. 913-916.

114. VoigtA. Y., Costea P. I., Kultima J. R., Li S. S., ZellerG., Sunagawa S., BorkP. Temporal and technical variability of human gut metagenomes // Genome biology. 2015. T. 16. C. 1-12.

115. WickR. R., SchultzM. B., ZobelJ., HoltK. E. Bandage: interactive visualization of de novo genome assemblies // Bioinformatics. 2015. T. 31, № 20. C. 33503352.

116. Aksland C. T., Bixel T. W., Raymond L. C., Rottmayer M. A., Alleyne A. G. Graph-based electro-mechanical modeling of a hybrid unmanned aerial vehicle for real-time applications // 2019 American Control Conference (ACC). IEEE. 2019. C. 4253-4259.

117. Mislove A., Marcon M., Gummadi K. P, Druschel P, Bhattacharjee B. Measurement and analysis of online social networks // Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. 2007. C. 29-42.

118. Ganesh A., Massoulie L., Towsley D. The effect of network topology on the spread of epidemics // Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. T. 2. IEEE. 2005. C. 14551466.

119. Chang L., Yu J. X., Qin L., Lin X., Liu C., Liang W. Efficiently computing k-edge connected components via graph decomposition // Proceedings of the 2013 ACM SIGMOD international conference on management of data. 2013. C. 205216.

120. Henderson K., Gallagher B., Eliassi-Rad T., Tong H., Basu S., Akoglu L., Koutra D., Faloutsos C., Li L. Rolx: structural role extraction & mining in large graphs // Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 2012. C. 1231-1239.

121. Lin J., Keogh E., Lonardi S., Chiu B. A symbolic representation of time series, with implications for streaming algorithms // Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. 2003. C. 2-11.

122. Sanger F., Nicklen S., Coulson A. R. DNA sequencing with chain-terminating inhibitors //Proceedings of the national academy of sciences. 1977. T. 74, № 12. C. 5463-5467.

123. Bentley D. R., Balasubramanian S., Swerdlow H. P, Smith G. P, Milton J., Brown C. G., Hall K. P, Evers D. J., Barnes C. L., Bignell H. R. [h gp.]. Accurate whole human genome sequencing using reversible terminator chemistry // nature. 2008. T. 456, № 7218. C. 53-59.

124. Illumina, Inc. Illumina sequencing technology. URL: https://www.illumina. com/science/technology/next-generation-sequencing/sequencing-technology. html (gara o6p. 29.03.2025).

125. Rothberg J. M., Hinz W., Rearick T. M., Schultz J., Mileski W., Davey M., Leamon J. H., Johnson K., Milgrew M. J., EdwardsM. [h gp.]. An integrated semiconductor device enabling non-optical genome sequencing // Nature. 2011. T. 475, № 7356. C. 348-352.

126. Clarke J., Wu H.-C., Jayasinghe L., Patel A., Reid S., Bayley H. Continuous base identification for single-molecule nanopore DNA sequencing // Nature nanotechnology. 2009. T. 4, № 4. C. 265-270.

127. Eid J., Fehr A., Gray J., Luong K., Lyle J., Otto G., Peluso P, Rank D., Baybayan P, Bettman B. [h gp.]. Real-time DNA sequencing from single polymerase molecules // Science. 2009. T. 323, № 5910. C. 133-138.

128. Ounit R., Wanamaker S., Close T. J., Lonardi S. CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers // BMC genomics. 2015. T. 16. C. 1-13.

129. Kim D., Song L., Breitwieser F. P., Salzberg S. L. Centrifuge: rapid and sensitive classification of metagenomic sequences//Genome research. 2016. T. 26, № 12. C. 1721-1729.

130. Blanco-Miguez A., Beghini F., Cumbo F., Mclver L. J., Thompson K. N., Zolfo M., Manghi P., Dubois L., Huang K. D., Thomas A. M. [h gp.]. Extending and improving metagenomic taxonomic profiling with uncharacterized species usingMetaPhlAn4 //Nature Biotechnology. 2023. T. 41, № 11. C. 1633-1644.

131. Beghini F., Mclver L. J., Blanco-Miguez A., Dubois L., Asnicar F., Maharjan S., MailyanA., Manghi P., ScholzM., Thomas A. M. [h gp.]. Integrating taxonomic, functional, and strain-level profiling of diverse microbial communities with bioBakery 3 // elife. 2021. T. 10. e65088.

132. Suzek B. E., Wang Y., Huang H., McGarvey P. B., Wu C. H., Consortium U. UniRef clusters: a comprehensive and scalable alternative for improving sequence similarity searches // Bioinformatics. 2015. T. 31, № 6. C. 926-932.

133. Caspi R., Billington R., Keseler I. M., Kothari A., Krummenacker M., Midford P. E., Ong W. K., Paley S., Subhraveti P., Karp P. D. The MetaCyc database of metabolic pathways and enzymes-a 2019 update // Nucleic acids research. 2020. T. 48, № D1. C. D445-D453.

134. Namiki T., Hachiya T., Tanaka H., Sakakibara Y. MetaVelvet: an extension of Velvet assembler to de novo metagenome assembly from short sequence reads // Proceedings of the 2nd ACM conference on bioinformatics, computational biology andbiomedicine. 2011. C. 116-124.

135. Afiahayati, Sato K., Sakakibara Y. MetaVelvet-SL: an extension of the Velvet assembler to a de novo metagenomic assembler utilizing supervised learning // DNA research. 2015. T. 22, № 1. C. 69-77.

136. Liang K.-c., Sakakibara Y. MetaVelvet-DL: a MetaVelvet deep learning extension for de novo metagenome assembly // BMC bioinformatics. 2021. T. 22, Suppl 6. C. 427.

137. Peng Y., Leung H. C., Yiu S.-M., Chin F. Y. IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth // Bioinformatics. 2012. T. 28, № 11. C. 1420-1428.

138. Alneberg J., Bjarnason B. S., De Bruijn I., Schirmer M., Quick J., Ijaz U. Z., LahtiL.,LomanN.J.,AnderssonA. F., Quince C. Binningmetagenomic contigs by coverage and composition // Nature methods. 2014. T. 11, № 11. C. 11441146.

139. Wu Y.-W., Simmons B. A., Singer S. W. MaxBin 2.0: an automated binning algorithm to recover genomes from multiple metagenomic datasets // Bioinformatics. 2016. T. 32, № 4. C. 605-607.

140. KangD. D, Li F., KirtonE., Thomas A., EganR., AnH., Wang Z. MetaBAT 2: an adaptive binning algorithm for robust and efficient genome reconstruction from metagenome assemblies // PeerJ. 2019. T. 7. e7359.

141. Kokot M., Diugosz M., Deorowicz S. KMC 3: counting and manipulating k-mer statistics//Bioinformatics. 2017. T. 33, № 17. C. 2759-2761.

142. BroderA. Z. On the resemblance and containment of documents // Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171). IEEE. 1997. C. 21-29.

143. Zhang C., Zheng W., Freddolino P. L., Zhang Y. MetaGO: Predicting Gene Ontology of non-homologous proteins through low-resolution protein structure prediction and protein-protein network mapping // Journal of molecular biology. 2018. T. 430, № 15. C. 2256-2265.

144. Ulyantsev V. I., Kazakov S. V, Dubinkina V. B., Tyakht A. V., Alexeev D. G. MetaFast: fast reference-free graph-based comparison of shotgun metagenomic data//Bioinformatics. 2016. T. 32, № 18. C. 2760-2767.

145. Breiman L. Random forests // Machine learning. 2001. T. 45. C. 5-32.

146. Chen T., Guestrin C. Xgboost: A scalable tree boosting system // Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016. C. 785-794.

147. Freund Y., SchapireR. E. A decision-theoretic generalization of on-line learning and an application to boosting // Journal of computer and system sciences. 1997. T. 55, № 1. C. 119-139.

148. Friedman J. H. Greedy function approximation: a gradient boosting machine // Annals of statistics. 2001. C. 1189-1232.

149. Montgomery D. C., Peck E. A., Vining G. G. Introduction to linear regression analysis. John Wiley & Sons, 2021.

150. Pedregosa F., Varoquaux G., Gramfort A., Michel V., Thirion B., Grisel O., BlondelM.,Prettenhofer P., WeissR., Dubourg V. [ugp.]. Scikit-learn: Machine learning in Python // the Journal of machine Learning research. 2011. T. 12. C. 2825-2830.

151. Bakir-Gungor B., HacilarH., JabeerA.,Nalbantoglu O. U., Aran O., Yousef M. Inflammatory bowel disease biomarkers of human gut microbiota selected via different feature selection methods // PeerJ. 2022. T. 10. e13205.

152. Chicco D. Ten quick tips for machine learning in computational biology // BioData mining. 2017. T. 10, № 1. C. 35.

153. Chicco D. , Jurman G. The advantages of the Matthews correlation coefficient (MCC) over F1 score and accuracy in binary classification evaluation // BMC genomics. 2020. T. 21. C. 1-13.

154. Pearson K. X. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling // The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 1900. T. 50, № 302. C. 157-175.

155. Yates F. Contingency tables involving small numbers and the x 2 test // Supplement to the Journal of the Royal Statistical Society. 1934. T. 1, № 2. C. 217-235.

156. Mann H. B., Whitney D. R. On a test of whether one of two random variables is stochastically larger than the other // The annals of mathematical statistics. 1947. C. 50-60.

157. Dunn O. J. Multiple comparisons among means // Journal of the American statistical association. 1961. T. 56, № 293. C. 52-64.

158. Gourle H., Karlsson-Lindsjo O., Hayer J., Bongcam-Rudloff E. Simulating Illumina metagenomic data with InSilicoSeq // Bioinformatics. 2019. T. 35, №3. C. 521-522.

159. Kaplan G. G., Windsor J. W. The four epidemiological stages in the global evolution of inflammatory bowel disease // Nature reviews Gastroenterology & hepatology. 2021. T. 18, №1.C. 56-66.

160. He Q., Gao Y., Jie Z., Yu X, Laursen J. M.., Xiao L., Li Y., Li L., Zhang F., Feng Q. [h gp.]. Two distinct metacommunities characterize the gut microbiota in Crohn's disease patients // Gigascience. 2017. T. 6, № 7. gix050.

161. Qin J., Li R., Raes J., Arumugam M., Burgdorf K. S., Manichanh C., Nielsen T., Pons N., Levenez F., Yamada T. [hgp.]. A human gut microbial gene catalogue established by metagenomic sequencing//Nature. 2010. T. 464, № 7285. C. 5965.

162. Lewis J. D., ChenE. Z., Baldassano R. N., OtleyA. R., Griffiths A. M., LeeD., Bittinger K., Bailey A., Friedman E. S., Hoffmann C. [h gp.]. Inflammation, antibiotics, and diet as environmental stressors of the gut microbiome in pediatric Crohn's disease // Cell host & microbe. 2015. T. 18, № 4. C. 489500.

163. Feng Q., Liang S., Jia H., Stadlmayr A., Tang L., Lan Z., Zhang D., Xia H., Xu X., Jie Z. [h gp.]. Gut microbiome development along the colorectal adenoma-carcinoma sequence // Nature communications. 2015. T. 6, № 1. C. 6528.

164. Thomas A. M., Manghi P., Asnicar F., Pasolli E., Armanini F., Zolfo M., Beghini F., Manara S., Karcher N., Pozzi C. [h gp.]. Metagenomic analysis of colorectal cancer datasets identifies cross-cohort microbial diagnostic signatures and a link with choline degradation // Nature medicine. 2019. T. 25, № 4. C. 667-678.

165. Yachida S., Mizutani S., Shiroma H., Shiba S., Nakajima T., Sakamoto T., Watanabe H., Masuda K., Nishimoto Y., Kubo M. [h gp.]. Metagenomic and metabolomic analyses reveal distinct stage-specific phenotypes of the gut microbiota in colorectal cancer // Nature medicine. 2019. T. 25, № 6. C. 968976.

166. Poisson S.-D. Recherches sur la probabilité des jugements en matière criminelle et en matière civile: précédées des règles générales du calcul des probabilités. Paris : Bachelier, 1837. C. 415.

167. Olekhnovich E. I., VasilyevA. T., Ulyantsev VI., KostryukovaE. S., TyakhtA. V. MetaCherchant: analyzing genomic context of antibiotic resistance genes in gut microbiota //Bioinformatics. 2018. T. 34, № 3. C. 434-444.

168. GrüningB., DaleR., SjödinA., Chapman B. A., Rowe J., Tomkins-Tinch C. H., Valieris R., Köster J., Team B. Bioconda: sustainable and comprehensive software distribution for the life sciences // Nature methods. 2018. T. 15, № 7. C. 475-476.

169. The joblib developers. The joblib library. 29.03.2025. DOI: https://doi.org/10. 5281/zenodo.14915601. URL: https://github.com/joblib/joblib.

170. Minka T. Automatic choice of dimensionality for PCA // Advances in neural information processing systems. 2000. T. 13.

171. Altschul S. F.', Gish W., Miller W., Myers E. W., Lipman D. J. Basic local alignment search tool // Journal of molecular biology. 1990. T. 215, № 3. C. 403-410.

Список иллюстраций

Р. 1 Пример графа де Брейна, построенного по двум строкам с к = 4. Цветом вершин отмечена принадлежность к-меров строкам. Справа представлены все к-меры и их частота встречаемости ... 22 Р.2 Схема извлечения признаков из групп образцов, заданных множеством строк, с использованием графа де Брейна (А). На основе извлеченных признаков обучается классификационная модель, которая затем используется для разметки новых образцов (Б) . . . 24 Р.3 Схема извлечения признаков на основе раскраски вершин графа

де Брейна................................ 26

Р.4 Результаты работы моделей случайного леса в задаче трехклассо-вой классификации. А) Точность (accuracy) лучшего метода для пары обучающий набор (группировка, выделен шрифтом внизу) и тестовый набор (столбцы, разные цвета); Б) Разница точности между классификаторами обученными на признаках из лучшего метода MetaFX и на основе таксономических признаков; В) Выбранный лучший метод для каждой пары обучающий-тестовый

набор.................................. 29

Р. 5 Схема разбиения данных временной серии из трех графов на категории ................................. 30

Р.6 Разбиение на категории итогового состояния после трансплантации микробиоты. По горизонтальной оси отложено время в днях с момента процедуры, по вертикальной - относительная доля классифицированных прочтений ..................... 32

Р.7 Схема модулей, реализованных в библиотеке MetaFX....... 34

5.1 An example of a de Bruijn graph constructed from two reads with k = 4. The colour of the vertices indicates the presence of k-mers in reads.

All k-mers and their frequency of occurrence are presented on the right 48

5.2 Feature extraction pipeline from string dataset samples using a de Bruijn graph (A). Based on the extracted features, a classification

model is trained, which is then used to classify unlabelled samples (B) 50

5.3 Feature extraction pipeline from coloured de Bruijn graph....... 51

5.4 Random forest three-class classification results. A) Accuracy of the best method for the train set (grouping, highlighted in bold) and test set (columns, different colours); B) Difference in accuracy between classifiers trained on features from the best MetaFX method and on taxonomic features; C) Selected best method for each train-test dataset

pair ................................... 54

5.5 Diagram of partitioning three-graph time series data into categories . . 55

5.6 Categorization of the reads in final sample after microbiota transplantation. The X-axis represents the time in days since the procedure, and

the Y-axis represents the relative proportion of classified reads .... 56

S.7

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Modules implemented in MetaFX library ...............

(А) Пример графа разделенного на три компоненты на основе численных значений в вершинах. (Б) Пример реберно 3-связного графа, удаление красных ребер ведет к образованию двух компонент

связности ................................

(А) Пример графа де Брейна, построенного по двум прочтениям с к = 4. Цветом вершин отмечена принадлежность k-меров прочтениям. Справа представлены все k-меры и их частота встречаемости. (Б) Соответствующий ему сжатый граф де Брейна.....

Схема работы алгоритма метагеномной сборки ...........

Схема работы программы Mash для сравнения образцов на основе

k-меров .................................

Пример визуализации дерева решений ................

Схема извлечения признаков из групп метагеномных образцов с использованием графа де Брейна (А). На основе извлеченных признаков обучается классификационная модель, которая затем используется для разметки новых образцов (Б) ............

Схема отбора уникальных k-меров для каждого класса образцов, которые присутствуют хотя бы в G образцах данного класса . . . Схема отбора опорных k-меров, относительная представленность которых в образцах статистически значимо различается между

группами образцов ...........................

Блок-схема модулей и потоков данных, объединяющая методы извлечения признаков из раздела 2.1 ..................

Схема построения графа де Брейна с раскрашенными вершинами Схема построения графа де Брейна с раскрашенными вершинами Качество классификации методом логистической регрессии на признаках различных методов из набора Franzosa по метрике accuracy в постановке: А) трехклассовая задача: БК, ЯК, здоровые; Б) двухклассовая задача: БК и ЯК ...............

Итоговое ранжирование методов, предложенных участниками для решения первого (часть А) и второго (часть Б) заданий соревнования MEDIC............................

Результаты работы моделей случайного леса в задаче трехклассо-вой классификации. А) Точность лучшего метода для пары обучающий набор (группировка, выделен шрифтом внизу) и тестовый набор (столбцы, разные цвета); Б) Разница точности между лучшим методом MetaFX и методом на основе таксономических признаков; В) Выбранный лучший метод для каждой пары

обучающий-тестовый набор .....................

Схема метода извлечения признаков для сравнения двух образцов Пример классификации прочтения как частично обнаруженного при обнаружении при одном значении k ...............

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

Схема разбиения данных временной серии из трех графов на категории .................................

(А) чувствительность (recall) и (Б) точность (precision) обнаружения штаммов из исследуемого и модифицируюшего объекта, сосуществующих в итоговом объекте. Схожесть референсных последовательностей приведена как частота совпадений по оси абсцисс ...................................

(А) чувствительность (recall) и (Б) точность (precision) обнаружения видов из исследуемого и модифицируюшего объекта, сосуществующих в итоговом объекте. Сложность по числу видов отмечена цветом, средняя глубина покрытия указана на оси абсцисс Относительная частота встречаемости видов в образцах для низкой (low), средней (medium) и высокой (high) сложности .....

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

Распределение генов устойчивости к антибиотикам по категориям прочтений в образцах донора (DONOR), реципиента до трансплантации микробиоты (Pre-FMT) и реципиента после трансплантации (Post-FMT) ...........................

Схема конвейра анализа временной серии метагеномных образцов на основе программы ReadsClassifier: (А) - классификация прочтений донора, (Б) - классификация прочтений реципиента до трансплантации, (В-Д) - классификация прочтений реципиента после трансплантации ....................

Примеры визуализации и раскраски графов итоговой временной точки образца для последовательностей гена устойчивости к транспорту антимикробных пептидов через клеточную стенку (А)

и устойчивости к тетрациклинам (Б).................

Схема модулей, реализованных в библиотеке MetaFX .......

Пример входного файла со списком расположений файлов образцов и их категориями .........................

Пример вызова справочной информации для метода stats . . . Пример структуры директории с результатами запуска программы metafx unique.........................

Пример визуализации близости образцов после применения метода PCA ................................

Пример текстового описания модели и визуализации случайного

леса деревьев решений ........................

Пример визуализации модели случайного леса и графа де Брейна с синхронизированным выделением признаков ...........

32 Пример запуска программы BandageNG в мультиграфовом режиме. (А) Меню загрузки папки с файлами графов; (Б) иерархия папок с графами в файловой системе. Будут загружены только выделенные файлы с расширением gfa................ 154

33 Пример визуализации семи графов де Брейна в мультиграфовом режиме в приложении BandageNG. Зеленым цветом выделен исследуемый признак, для которого строился контекст ........ 155

Список таблиц

Р.1 Результаты экспериментальных исследований сравнения трех разработанных методов и таксономической аннотации на сгенерированных данных .......................... 27

Р.2 Качество классификации образцов при различных методах извлечения признаков по метрике MCC .................. 27

5.1 Experimental results comparing three developed methods and taxo-

nomic annotation on generated data .................. 52

5.2 Samples classification quality for different feature extraction methods

using the MCC metric .......................... 53

1 Четыре категории результатов двухклассовой классификации ... 90

2 Параметры сгенерированных наборов тестовых метагеномов . . . 104

3 Результаты экспериментальных исследований сравнения трех разработанных методов и таксономической аннотации на сгенерированных данных .......................... 105

4 Основные характеристики метагеномных наборов данных по воспалительным заболеваниям кишечника ............... 106

5 Качество классификации образцов при различных методах извлечения признаков по метрике MCC. Применена модель логистической регрессии и кросс-валидация с пятью повторениями. Полужирным шрифтом выделено значение лучшего метода для каждого набора данных и задачи ...................... 108

6 Качество по метрике MCC классификации образцов с помощью логистической регрессии при обучении на признаках из набора данных Franzosa. Полужирным шрифтом выделено значение лучшего метода извлечения признаков для каждого тестового набора данных и задачи ......................... 109

7 Качество по метрике MCC классификации образцов с помощью логистической регрессии при обучении на признаках из набора данных Lo Sasso. Полужирным шрифтом выделено значение лучшего метода извлечения признаков для каждого тестового набора данных и задачи ............................ 109

8 Качество по метрике MCC классификации образцов с помощью логистической регрессии при обучении на признаках из набора данных Lloyd-Price. Полужирным шрифтом выделено значение лучшего метода извлечения признаков для каждого тестового набора данных и задачи ......................... 109

9 Качество по метрике accuracy классификации образцов с помощью случайного леса при обучении на признаках из набора данных Franzosa. Полужирным шрифтом выделено значение лучшего метода извлечения признаков для каждого тестового набора данных и задачи ............................ 111

10 Качество по метрике accuracy классификации образцов с помощью случайного леса при обучении на признаках из набора данных Lo Sasso. Полужирным шрифтом выделено значение лучшего метода извлечения признаков для каждого тестового набора данных и задачи ............................ 111

11 Качество по метрике accuracy классификации образцов с помощью случайного леса при обучении на признаках из набора данных Lloyd-Price. Полужирным шрифтом выделено значение лучшего метода извлечения признаков для каждого тестового набора данных и задачи ............................ 111

12 Основные характеристики метагеномных наборов данных по раковым заболеваниям кишечника ................... 114

13 Сравнение четырех решений для разбиения прочтений на категории в методе извлечения признаков из двух образцов одной временной серии .............................. 121

14 Входные параметры программы ReadsClassifier....... 131

15 Входные параметры программы TripleReadsClassifier . . 132

16 Входные параметры программы FMTVisualiser ........ 136

17 Входные параметры программы RecipientVisualiser . . . . 138

18 Общие входные параметры методов unique, colored и stats

в библиотеке MetaFX ......................... 144

19 Входные параметры метода feature_analysis в библиотеке MetaFX ................................. 151

Приложение А. Награды автора, полученные во время работы над

диссертацией

- Победитель конкурса грантов для студентов вузов, расположенных на территории Санкт-Петербурга, аспирантов вузов, отраслевых и академических институтов, расположенных на территории Санкт-Петербурга в 2023 и 2024 годах.

- Лучший устный доклад на конференции молодых ученых «Геномика, метагеномика и молекулярная биология микроорганизмов» в рамках проекта «Атлас микробных сообществ Российской Федерации» в 2023 году.

- Победитель международного соревнования по метагеномной диагностике воспалительных заболеваний кишечника MEDIC (Metagenomic Diagnosis for Inflammatory Bowel Disease Challenge -https://www.intervals.science/resources/sbv-improver/medic) в двух номинациях: анализ сырых данных секвенирования и анализ обработанных данных, 2020 год.

ПРАВИТЕЛЬСТВО САНКТ-ПЕТЕРБУРГА

серия ПСП № 24027

ПОБЕДИТЕЛЬ КОНКУРСА ГРАНТОВ САНКТ-ПЕТЕРБУРГА ДЛЯ СТУДЕНТОВ, АСПИРАНТОВ, МОЛОДЫХ УЧЕНЫХ, МОЛОДЫХ КАНДИДАТОВ НАУК 2024 Г.

Национальный исследовательский университет ИТМО

|4

« Губернатор Санкт-Петербурга

А.Д.Беглов

ПРАВИТЕЛЬСТВО САНКТ-ПЕТЕРКУРГА

ДИПЛОМ

серия ПСП № 23205

ПОБЕДИТЕЛЬ КОНКУРСА ГРАНТОВ САНКТ-ПЕТЕРБУРГА ДЛЯ СТУДЕНТОВ, АСПИРАНТОВ, МОЛОДЫХ УЧЕНЫХ, МОЛОДЫХ КАНДИДАТОВ НАУК 2023 Г.

Ш

Национальный исследовательский университет ИТМО

Губернатор Санкт-Петербурга 71г ¿Г А.Д.Беглов

Сертификат

182

Свидетельствует о том, что

выступил с лучшим устным докладом на конференции молодых ученых «Геномика, метагеномика и молекулярная биология микроорганизмов», проведенной в рамках проекта «Атлас микробных сообществ Российской Федерации» 23-24 сентября 2023 года

Skoltech

Laboratory

of Metagenome Analysis

Проект

«Атлас микробных сообществ Российской Федерации» выполняется при поддержке гранта Министерства науки и высшего образования Российской Федерации (Соглашение №075-10-2021-114 от 11.10.2021 г.)

Исаев. А.Б. к. б. н., руководитель проекта

Dear Artem IVANOV,

Your team1 is entitled to a USD 2,000 prize, as a best-performer team in the Sub-challenge 1, of the sbv IMPROVER Metagenomics Diagnosis for IBD Challenge (MEDIC), organized by Philip Morris Product SA, Neuchatel, Switzerland. In order to enable you and your team to take advantage of this prize, please complete and sign this document and return a scanned copy, in pdf format, by September 30, 2020 to the email address below.

My signature below confirms that:

• As Team Leader, I certify that I informed, accurately and in writing, all the other team members of this letter and of all its content, and that, before signing it, I obtained all the necessary written confirmations from them.

• Myself and all my team members allow the organizers to publish their names and affiliations on www.pmiscience.com, and www.intervals.science websites, and in any further announcements and documents related to sbv IMPROVER.

• I certify that - in accepting this prize, granting the rights set forth herein and the monetary prize - none of the members of my team is in conflict with the policies of any organization(s) to which they are affiliated or bound, or with the laws and policies of the countries they live in.

• I have read, understood and accepted the Challenge Rules.

Name: Affiliation: Place, Date:

Signature:

Once filled out and signed, please return this document in scan copy to: [e-mail]

Dear Artem IVANOV,

Your team1 is entitled to a USD 2,000 prize, as a best-performer team in the Sub-challenge 2, of the sbv IMPROVER Metagenomics Diagnosis for IBD Challenge (MEDIC), organized by Philip Morris Product SA, Neuchatel, Switzerland. In order to enable you and your team to take advantage of this prize, please complete and sign this document and return a scanned copy, in pdf format, by September 30, 2020 to the email address below.

My signature below confirms that:

• As Team Leader, I certify that I informed, accurately and in writing, all the other team members of this letter and of all its content, and that, before signing it, I obtained all the necessary written confirmations from them.

• Myself and all my team members allow the organizers to publish their names and affiliations on www.pmiscience.com, and www.intervals.science websites, and in any further announcements and documents related to sbv IMPROVER.

• I certify that - in accepting this prize, granting the rights set forth herein and the monetary prize - none of the members of my team is in conflict with the policies of any organization(s) to which they are affiliated or bound, or with the laws and policies of the countries they live in.

• I have read, understood and accepted the Challenge Rules.

Name: Affiliation: Place, Date:

Signature:

Once filled out and signed, please return this document in scan copy to: [e-mail]

Приложение Б. Акты внедрения результатов работы на практике и в

учебном процессе

- Акт о внедрении результатов диссертации в проекте РНФ «Микробио-та кишечника и ответ на иммунотерапию злокачественных опухолей: от воспроизводимых биомаркеров к модуляции эффекта», реализуемом в ФГБУ ФНКЦ ФХМ ИМ. Ю.М. ЛОПУХИНА ФМБА РОССИИ.

- Акт об использовании результатов диссертации в учебном процессе в Институте биоинформатики.

- Акт об использовании результатов диссертации в учебном процессе в Университете ИТМО.

ФЕДЕРАЛЫ гое медико-биологическое агентство

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ

ФЕДЕРАЛЬНЫЙ НАУЧНО-КЛИНИЧЕСКИЙ ЦЕНТР ФИЗИКО-ХИМИЧЕСКОЙ

МЕДИЦИНЫ ИМ. АКАДЕМИКА Ю. М, ЛОПУХИНА ФЕДЕРАЛЬНОГО МЕДИКО-БИОЛОГИЧЕСКОГО АГЕНТСТВА

(ФГБУ ФНКЦ ФХМ им, Ю.М, Лопухина ФМБА России)

АКТ о внедрении

«ЪО» .гдхя 20'Й г. № А9.г

результатов диссертационного исследования Иванова Артема Борисовича на тему «Методы классификации объектов в виде наборов строковых данных с применением графов де Брсйна»

Настоящий акт подтверждает то, что результаты научно-исследовательской работы, выполненной Ивановым А.Б, н рамках диссертационного исследования на тему «Методы классификации объектов в виде наборов строковых данных е применением графив де Брейна», успешно внедрены в проекте РНФ «Микробиота кишечника и ответ на иммунотерапию злокачественных опухолей: от воспроизводимых биомаркеров к модуляции эффекта», реализуемом в ФГБУ ФНКЦ ФХМ ИМ. Ю.М. ЛОПУХИНА ФМБА РОССИИ. Разработанный Ивановым А.Б. программный комплекс Ме1аГХ <Мр5;//ш11шЬ.сот/сМаЬ/те1а5^ применяется для анализа данных метагеномного секвенирования с целью улучшить качество предсказания ответа на иммунотерапию злокачественных опухолей. Использование программы позволило получить значимые результаты, что может внести вклад в создание технологий предсказания исхода лечения онкологических заболеваний.

Руководитель проекта к.б.н., старший научный сотрудник лаборатории клеточной биологии

Олехнович Е.И.

Генеральный директор ФГБУ ФНКЦ ФХМ им. Ю.М. д.б.н., профессор, член-корр.

Лагарькова М.А.

ИНСТИТУТ БИОИНФОРМАТИКИ

от 05.06.2025

АКТ

об использовании в учебном процессе результатов диссертационного исследования Иванова Артема Борисовича на тему «Методы классификации объектов в виде наборов строковых данных с применением графов де Брейна»

Настоящий акт подтверждает, что результаты научно-исследовательской работы, выполненной Ивановым А.Б. в рамках диссертационного исследования на тему «Методы классификации объектов в виде наборов строковых данных с применением графов де Брейна», используются в учебном процессе Института биоинформатики на программах профессиональной переподготовки и повышения квалификации.

Разработанный Ивановым А.Б. программный комплекс Ме1аВ< для извлечения признаков из метагеномных графов де Брейна используется в качестве шаблона для обучения разработке программ анализа биологических данных, а также для обучения работе с метагеномными данными. Использование программного комплекса позволяет поэтапно воспроизводить процесс разработки программного обеспечения (ПО) для естественно-научных задач и обучает анализировать промежуточные результаты обработки данных метагеномного секвенирования, что позволяет улучшить качество подготовки специалистов в областях разработки ПО, анализа данных и биоинформатики.

Указанные результаты включены в следующие учебные программы:

• Программа профессиональной переподготовки «Биоинформатика для биологов» в рамках курса «Алгоритмы в биоинформатике» в 2023-2025 годах.

• Программа повышения квалификации «Интенсив по анализу данных N05» в рамках курса «Анализ метагеномных данных» в 2023 году.

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

Куратор образовательных программ

Яворская М.В. Бондарева О.В.

ИНСТИТУТ БИОИНФОРМАТИКИ

ВЮ^РМЕ

[e-mail]

КАНТЕМИРОВСКАЯ УЛ. 2А, ОФИС 420,197342, САНКТ-ПЕТЕРБУРГ, РОССИЯ

188

1/iTMO

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное автономное образовательное учреждение высшегообразовэния <■ Национальный исследовательский университет ИТМО» (Университет ИТМО)

Кронверкский пр-т, д. 49, лит. А, Санкт-Петербург, Россия. 137101 Тм.'(812Нв0-00-00 od^itmo.ru | itmo.ru

АКТ

об использовании в учебном процессе результатов диссертационного исследования Иванова Артема Борисовича на тему «Методы классификации объектов в виде наборов строковых данных с

Настоящий акт подтверждает, что результаты научно-исследовательской работы, выполненной Ивановым Артемом Борисовичем в рамках диссертационного исследования на тему «Методы классификации объектов в виде наборов строковых данных с применением графов де Брейна», используются в учебном процессе Университета ИТМО на магистерской программе «Биоинформатика и системная биология» института прикладных компьютерных наук.

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

Указанные результаты включены в следующие курсы:

1. Курс «Дискретная математика» в 2021-2025 годах.

2. Курс «Алгоритмы в биоинформатике» в 2023-2025 годах.

применением графов де Брейна»

Директор ИПКН

Кузнецов A.M.

Публикации автора по теме диссертации приведены ниже

1. 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. Т. 6, № 4. С. 10-1128.

2. Khachatryan L., Xiang Y, Ivanov A., Glaab E., Graham G., Granata I., Giordano M., Maddalena L., Piccirillo M., Manipur I. [и др.]. Results and lessons learned from the sbv IMPROVER metagenomics diagnostics for inflammatory bowel disease challenge // Scientific Reports. 2023. Т. 13, № 1. С. 6303.

3. 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. Т. 8, № 2. e01023-22.

4. Zakharevich N., Morozov M., Kanaeva V., Filippov M., Zyubko T., Ivanov A., Ulyantsev V., Klimina K., Olekhnovich E. Systemic metabolic depletion of gut microbiome undermines responsiveness to melanoma immunotherapy // Life Science Alliance. 2024. Т. 7, № 5.

5. Ivanova V., Chernevskaya E., Vasiluev P, Ivanov A., Tolstoganov I., Shafranskaya D., Ulyantsev V., Korobeynikov A., Razin S., Beloborodova N. [и др.]. Hi-C metagenomics in the ICU: exploring clinically relevant features of gut microbiome in chronically critically ill patients // Frontiers in microbiology. 2022. Т. 12. С. 770323.

6. Kaplina A., Zaikova E., Ivanov A., Volkova Y., Alkhova T., Nikiforov V., Latypov A., Khavkina M., Fedoseeva T., Pervunina T. [и др.]. Intestinal microbiome changes in an infant with right atrial isomerism and recurrent necrotizing enterocolitis: A case report and review of literature // World Journal of Clinical Cases. 2022. Т. 10, № 29. С. 10583.

Separation of Donor and Recipient Microbial Diversity Allows Determination of Taxonomic and Functional Features of Gut Microbiota Restructuring following Fecal Transplantation

^Evgenii I. Olekhnovich,a Artem B. Ivanov, b Vladimir I.

aFederal Research and Clinical Centre of Physical and Chemical Medicine, Federal Medical and Biological Agency of Russia, Moscow, Russian Federation bITMO University, Saint Petersburg, Russian Federation

Evgenii I. Olekhnovich and Artem B. Ivanov contributed equally. Vladimir I. Ulyantsev and Elena N. Ilina contributed equally to this work. The order of the authors was determined by the agreement of the parties.

ABSTRACT Fecal microbiota transplantation (FMT) is currently used in medicine to treat recurrent clostridial colitis and other intestinal diseases. However, neither the therapeutic mechanism of FMT nor the mechanism that allows the donor bacteria to colonize the intestine of the recipient has yet been clearly described. From a biological point of view, FMT can be considered a useful model for studying the ecology of host-associated microbial communities. FMT experiments can shed light on the relationship features between the host and its gut microbiota. This creates the need for experimentation with approaches to metagenomic data analysis which may be useful for the interpretation of observed biological phenomena. Here, the recipient intestine colonization analysis tool (RECAST) novel computational approach is presented, which is based on the metagenomic read sorting process per their origin in the recipient's post-FMT stool metagenome. Using the RECAST algorithm, taxo-nomic/functional annotation, and machine learning approaches, the metagenomes from three FMT studies, including healthy volunteers, patients with clostridial colitis, and patients with metabolic syndrome, were analyzed. Using our computational pipeline, the donor-derived and recipient-derived microbes which formed the recipient post-FMT stool metagenomes (successful microbes) were identified. Their presence is well explained by a higher relative abundance in donor/pre-FMT recipient metagenomes or other metagenomes from the human population. In addition, successful microbes are enriched with gene groups potentially related to antibiotic resistance, including antimicrobial peptides. Interestingly, the observed reorganization features are universal and independent of the disease.

IMPORTANCE We assumed that the enrichment of successful gut microbes by lantibi-otic/antibiotic resistance genes can be related to gut microbiota colonization resistance by third-party microbe phenomena and resistance to bacterium-derived or host-derived antimicrobial substances. According to this assumption, competition between the donor-derived and recipient-derived microbes as well as host immunity may play a key role in the FMT-related colonization and redistribution of recipient gut microbiota structure.

KEYWORDS gut microbiota, fecal transplantation, antibiotic resistance, colonization resistance, fecal microbiota transplantation, metagenomics