Iterative non-sequential protein structural alignment

Saeed Salem, Mohammed J. Zaki*

Computer Science Department, Rensselaer Polytechnic Institute, 110 8th st. Troy, NY 12180, USA. zaki@cs.rpi.edu

Proc LSS Comput Syst Bioinform Conf. August, 2008. Vol. 7, p. 183-194. Full-Text PDF

*To whom correspondence should be addressed.

Structural similarity between proteins gives us insights on the evolutionary relationship between proteins which have low sequence similarity. In this paper, we present a novel approach called STSA for non-sequential pair-wise structural alignment. Starting from an initial alignment, our approach iterates over a two-step process, a superposition step and an alignment step, until convergence. Given two superposed structures, we propose a novel greedy algorithm to construct both sequential and non-sequential alignments. The quality of STSA alignments is evident in the high agreement it has with the reference alignments in the challenging-to-align RPIC set. Moreover, on a dataset of 4410 protein pairs selected from the CATH database, STSA has a high sensitivity and high specificity values and is competitive with state-of-the-art alignment methods and gives longer alignments with lower rmsd. The STSA software along with the data sets will be made available on line at http://www.cs.rpi.edu/~zaki/software/STSA.