Сравнение последовательностей символов методом Шайдурова с применением технологии MPI для распараллеливания

Резюме: В статье изложен новый метод сравнения символьных последовательностей для задач биоинформатики, не использующий выравнивания и не содержащий свободных параметров. Метод основан на вычислении свёртки специально получаемых из символьных последовательностей бинарных последовательностей с помощью быстрого преобразования Фурье и допускающий крупномодульное распараллеливание. В работе обсуждается применение технологии MPI для эффективной реализации данного метода. Приведены оценки ускорения параллельной реализации при решении прикладных задач.

Ключевые слова: полином, выравнивание, мутация, вставка/выпадение, инверсия, технология MPI, крупномодульное распараллеливание

A.A. Molyavko, E.D. Karepova, M.G. Sadovsky

Simbol sequences comparison with Shaidurov’s method using MPI technology to parallel comuting

Summary: The paper presents the novel highly efficient method to compare two symbol sequences free from alignment meth- odology and having no free parameters; the method is illustrated with several classic bioinformatics problems. The method is based on a convolution calculation of two binary sequences; these latter are specially derived from nucleotide symbol sequences. The approach could be implemented for a comparison of symbol sequences from any finite alphabet. The convolution computation is based on fast Fourier transform. The method allows a coarse grained parallelism. Here we show MPI technology implementation to the parallelism of the computations. Some estimations for efficiency of the method followed from parallelism implementation are provided and discussed.

Keywords: polynomial, alignment, mutation, deletion/insertion, inversion, mpi, coarsegrained parallelism.

DOI:10.34219/2078-8320-2022–13-4-80-84