• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

An efficient approach to the protein structure alignment problem

Batsyn M.V., Kalyagin V.A., Tulyakov D.
The Protein Structure Alignment Problem (PSAP) consists in finding the best alignment of two proteins defined by their primary structures. It finds the most similar substructure of two proteins. This problem is polynomially reducible to the Maximum Clique Problem (MCP) for the protein alignment graph. In this paper we present an efficient algorithm for the PSAP based on our recent ILS&MCS algorithm (Batsyn et al., 2014) for the MCP. To reduce the alignment problem to the MCP we follow the DAST method introduced by Malod-Dognin et al. (2010). Our main contributions include: applying the ILS heuristic to obtain a lower bound and make preprocessing of an alignment graph to reduce its size; efficient implementation of the algorithm for large but sparse alignment graphs including memory preallocation and bit representation of adjacency matrix. The computational results are provided for the popular Skolnick test set of 40 proteins and show that the suggested algorithm is more efficient than one of the fastest PSAP solvers - the ACF algorithm by Malod- Dognin et al. (2010).