ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ГЛОБАЛЬНОГО ВЫРАВНИВАНИЯ С ОПТИМАЛЬНЫМ ИСПОЛЬЗОВАНИЕМ ПАМЯТИ

Статья относится к сравнительно молодой и быстро развивающейся науке биоинформатике и представляет еще один алгоритм глобального выравнивания двух нуклеотидных последовательностей. Алгоритмы глобального выравнивания лежат в основе многих метрик в пространствах нуклеотидных последовательностей и используются при построении филогенетических деревьев. Данный алгоритм отличается от известных тем, что он адаптирован к распараллеливанию на многоядерные процессоры и ускорители. В работе выполнена программная реализация алгоритма и приводятся результаты численных экспериментов. Еще одно отличие алгоритма состоит в возможности настраиваться на объем имеющейся памяти. Данный алгоритм использует процедуры двух известных алгоритмов: Хиршберга и Нидлмана-Вунша. Это позволяет достигать максимального быстродействия при заданных ограничениях на используемую память.