An efficient approach to the protein structure alignment problem

2015. No. 91.

Batsyn M.V., Kalyagin V.A., Tulyakov D. N.

Задача Структурного Сопоставления Протеинов (ЗССП) заключается в поиске наилучшего сопоставления двух протеинов, заданных их первичными структурами. В задаче определяется наиболее близкая подструктура у двух протеинов. Эта задача полиномиально сводится к Задаче о Максимальной Клике (ЗМК) в графе сопоставления. В данной работе представлен эффективный алгоритм для ЗССП, основанный на нашем алгоритме ILS&MCS (Batsyn et al., 2014) для ЗМК. Чтобы свести задачу сопоставления к ЗМК, мы используем метод DAST, предложенный в работе Malod-Dognin et al. (2010). Основные особенности нашего подхода включают: применение эвристики ILS для вычисления нижней границы и предварительной обработки графа сопоставления для сокращения его размеров; эффективную реализацию алгоритма для больших, но разреженных графов сопоставления, включая начальное выделение памяти и битовое представление матрицы смежности. Вычислительные результаты представлены для известного тестового набора Скольника из 40 протеинов и показывают, предложенный алгоритм более эффективен, чем один из наиболее быстрых подходов для ЗССП – алгоритм ACF (Malod-Dognin et al., 2010).

Ключевые слова: метод ветвей и границ, branch-and-bound algorithm, Protein alignment, сопоставление протеинов

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Методы кластеризации и поиска в сетях большого размера (2015)