Быстрая индексация метагеномов
Наиболее популярным решением задачи сравнения метагеномных образцов на данный момент является использование алгоритмов из семейства Unifrac, что, однако, оказывается неэффективно для решения задачи поиска ближайших соседей (NNS, nearest neighbor search) по заданному образцу в больших базах данных.
Целью работы является разработка метода построения поискового индекса для метагеномных образцов, эффективного как с точки зрения времени поиска, так и аппроксимации результатами поиска решений задачи NNS с использованием Unifrac. В ходе работы было обнаружено, что наиболее приближенные значениям Unifrac результаты можно получить, используя дивергенцию ДженсенаШеннона (JSD, Jensen–Shannon divergence) для сравнения индексов kмеров метагеномных образцов. Для упрощения решения NNS предложен приближенный метод поиска соседей с использованием расстояний JSD. Указанный метод основывается на применении аналога техники multidimensional scaling (MDS) при помощи генетического алгоритма и построения VPдерева для поиска приближенного решения.
В дальнейшем планируется использовать данный метод для построения поискового индекса на крупных базах метагеномов, а также исследовать возможности улучшить точность аппроксимации результатов NNS при помощи глубоких нейронных сетей.