7–11 Oct 2024
Asia/Novosibirsk timezone

Свёртка генетических последовательностей с применением быстрого преобразования Фурье

Speaker

Анна Андреевна Шехова (ИВМ СО РАН)

Description

В работе [1] был предложен метод сравнения генетических последовательностей и поиска в них совпадающих участков, принципиально отличный от самого распространённого в данной области метода выравнивания. Суть предложенного метода заключается в преобразовании каждой генетической последовательности в набор бинарных и вычислении свёрток последних. Ускорение работы достигается за счёт применения быстрого преобразования Фурье. Данный подход применим не только к генетическим текстам, но и к символьным произвольной природы.
При сравнении двух символьных последовательностей результатом его работы является целочисленная последовательность, каждое значение которой равно числу совпадающих символов во всевозможных наложениях исходных последовательностей вне зависимости от того, где расположены эти совпадения. Анализ этой последовательности позволит определить наличие значимых совпадений и их локализацию. Было разработано несколько подходов для решения данных задач.
Первая группа направлена на выделение значимых наложений с помощью а) статистических оценок, б) преобразования алфавита исходных последовательностей и в) алгоритма подсчёта совпадающих в наложении подстрок на основе свёртки одной и той же пары строк при меняющемся алфавите. Вторая группа алгоритмов локализации основывается на а) дихотомии и б) использовании весовой функции при вычислении свёртки.

Список используемой литературы:
[1] Highly Parallel Convolution Method to Compare DNA Sequences with Enforced In/Del and Mutation Tolerance / V. Shaidurov, E. Karepova, M. Sadovsky, A. Molyavko // Lecture Notes in Computer Science. – 2020. – Vol. 12108 LNBI. – P. 472-481. – DOI 10.1007/978-3-030-45385-5_42.

Секция конференции Биоинформатика и системная компьютерная биология

Primary authors

Presentation materials

There are no materials yet.