Proteins comparison through probabilistic optimal structure local alignment

Multiple local structure comparison helps to identify common structural motifs or conserved binding sites in 3D structures in distantly related proteins. Since there is no best way to compare structures and evaluate the alignment, a wide variety of techniques and different similarity scoring schemes have been proposed. Existing algorithms usually compute the best superposition of two structures or attempt to solve it as an optimization problem in a simpler setting (e.g. considering contact maps or distance matrices). Here, we present PROPOSAL (PROteins comparison through Probabilistic Optimal Structurelocal ALignment), a stochastic algorithm based on iterative sampling for multiple local alignmentof protein structures. Our method can efficiently find conserved motifs across a set of proteinstructures. Only the distances between all pairs of residues in the structures are computed.To show the accuracy and the effectiveness of PROPOSAL we tested it on a few families ofprotein structures. We also compared PROPOSAL with two state-of-the-art tools for pairwiselocal alignment on a dataset of manually annotated motifs.PROPOSAL is available as a Java 2D standalone application or a command line program athttp://ferrolab.dmi.unict.it/proposal/proposal.html.