An efficient approach to the protein structure alignment problem

Институт прикладной математики им. М.В. Келдыша Российской академии наук, 2015. No. 91.

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

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

Ключевые слова: Protein alignment, branch-and-bound algorithm