Logo des Repositoriums
 

Aligning protein structures using distance matrices and combinatorial optimization

Kurzanzeige
dc.contributor.authorWohlers, Inken
dc.contributor.authorPetzold, Lars
dc.contributor.authorDomingues, Francisco S.
dc.contributor.authorKlau, Gunnar W.
dc.contributor.editorGrosse, Ivo
dc.contributor.editorNeumann, Steffen
dc.contributor.editorPosch, Stefan
dc.contributor.editorSchreiber, Falk
dc.contributor.editorStadler, Peter
dc.date.accessioned2019-02-20T09:48:30Z
dc.date.available2019-02-20T09:48:30Z
dc.date.issued2009
dc.description.abstractStructural alignments of proteins are used to identify structural similarities. These similarities can indicate homology or a common or similar function. Several, mostly heuristic methods are available to compute structural alignments. In this paper, we present a novel algorithm that uses methods from combinatorial optimization to compute provably optimal structural alignments of sparse protein distance matrices. Our algorithm extends an elegant integer linear programming approach proposed by Caprara et al. for the alignment of protein contact maps. We consider two different types of distance matrices with distances either between Cα atoms or between the two closest atoms of each residue. Via a comprehensive parameter optimization on HOMSTRAD alignments, we determine a scoring function for aligned pairs of distances. We introduce a negative score for non-structural, purely sequence-based parts of the alignment as a means to adjust the locality of the resulting structural alignments. Our approach is implemented in a freely available software tool named PAUL (Protein structural Alignment Using Lagrangian relaxation). On the challenging SISY data set of 130 reference alignments we compare PAUL to six state-of-the-art structural alignment algorithms, DALI, MATRAS, FATCAT, SHEBA, CA, and CE. Here, PAUL reaches the highest average and median alignment accuracies of all methods and is the most accurate method for more than 30% of the alignments. PAUL is thus a competitive tool for pairwise high-quality structural alignment.en
dc.identifier.isbn978-3-88579-251-2
dc.identifier.pissn1617-5468
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/20308
dc.language.isoen
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofGerman conference on bioinformatics 2009
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-157
dc.titleAligning protein structures using distance matrices and combinatorial optimizationen
dc.typeText/Conference Paper
gi.citation.endPage43
gi.citation.publisherPlaceBonn
gi.citation.startPage33
gi.conference.date28th to 30th September 2009
gi.conference.locationHalle-Wittenberg
gi.conference.sessiontitleRegular Research Papers

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild
Name:
33.pdf
Größe:
621.21 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

P157 - GCB 2009 - German Conference on Bioinformatics 2009