Паршуков Даниил Леонидович

Группа 22126
Руководитель: Девятериков Антон Павлович

Текст ВКР

Аннотация

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

На основе проведённого анализа разработана программно-алгоритмическая система на языке C++, выполненная в виде разделяемой библиотеки. Реализация воспроизводит полную функциональность алгоритма: работу с номенклатурой PANGO, модели с одной и двумя точками разрыва, процедуру уточнения границ рекомбинации и сравнение моделей по критерию Акаике. Проведено экспериментальное сравнение с эталонной реализацией на наборе из 1393 линий PANGO для SARS-CoV-2. Разработанная система показывает ускорение в среднем в 1.6 раза, а на наиболее сложных случаях (две точки разрыва) до 2.0 раз. Среднее время анализа одной линии составляет 477 мс против 784 мс в эталонной версии.