Towards optimal alignment of protein structure distance matrices

• DOI: 10.1093/bioinformatics/btq420
• Publication Date: 2010-07-18T00:34:14Z
• Authors: Inken Wohlers; Francisco S. Domi...; Gunnar W. Klau
• Keywords: 0301 basic medicine; 03 medical and health sciences; Models, Chemical; Protein Conformation; Humans; Proteins; Sequence Alignment; Algorithms; Software

Abstract Motivation: Structural alignments of proteins are important for identification structural similarities, homology detection and functional annotation. The alignment problem is well studied computationally difficult. Many different scoring schemes similarity as many algorithms finding high-scoring have been proposed. Algorithms using contact map overlap (CMO) function currently the only practical able to compute provably optimal alignments. Results: We propose a new mathematical model inter-residue distance matrices, building upon previous work on maximum CMO. Our includes all elements needed emulate various protein matrices. algorithm that we use sparse Therefore, more effective function, which uses threshold positive scores. show even under these restrictions our approach in terms accuracy competitive with state-of-the-art algorithms, whereas it additionally either proves optimality an or returns bounds score. novel method freely available constitutes promising step towards truly proteins. Availability: An executable program PAUL at http://planet-lisa.net/ Contact: [e-mail] Supplementary information: data Bioinformatics online.