Highly Parallel Convolution Method to Compare DNA Sequences with Enforced In/Del and Mutation Tolerance

Abstract

New error tolerant method for the comparison and analysis of symbol sequences is proposed. The method is based on convolution function calculation, where the function is defined over the binary numeric sequences obtained by the specific transformation of original symbol sequence. The method allows highly parallel implementation and is of great value for insertion/delition mutations search. To calculate the convolution function, fast Fourier transform is used in the method implementation.

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