• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Препринт

An efficient approach to the protein structure alignment problem

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).