Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Computational Biology and Applied Algorithmics     Display Documents



ID: 536632.0, MPI für Informatik / Computational Biology and Applied Algorithmics
Towards optimal alignment of protein structure distance matrices
Authors:Wohlers, Inken; Domingues, Francisco S.; Klau, Gunnar W.
Language:English
Date of Publication (YYYY-MM-DD):2010
Title of Journal:Bioinformatics
Volume:26
Issue / Number:18
Start Page:2273
End Page:2280
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:MOTIVATION: Structural alignments of proteins are important for identification
of structural similarities, homology detection and functional annotation. The
structural alignment problem is well studied and computationally difficult.
Many different scoring schemes for structural similarity as well as many
algorithms for finding high-scoring alignments have been proposed. Algorithms
using contact map overlap (CMO) as scoring function are currently the only
practical algorithms able to compute provably optimal alignments. RESULTS: We
propose a new mathematical model for the alignment of inter-residue distance
matrices, building upon previous work on maximum CMO. Our model includes all
elements needed to emulate various scoring schemes for the alignment of protein
distance matrices. The algorithm that we use to compute alignments is practical
only for sparse distance matrices. Therefore, we propose a more effective
scoring function, which uses a distance threshold and only positive structural
scores. We show that even under these restrictions our approach is in terms of
alignment accuracy competitive with state-of-the-art structural alignment
algorithms, whereas it additionally either proves the optimality of an
alignment or returns bounds on the optimal score. Our novel method is freely
available and constitutes an important promising step towards truly provably
optimal structural alignments of proteins. AVAILABILITY: An executable of our
program PAUL is available at http://planet-lisa.net/.
Last Change of the Resource (YYYY-MM-DD):2011-01-18
External Publication Status:published
Document Type:Article
Communicated by:Thomas Lengauer
Affiliations:MPI für Informatik/Computational Biology and Applied Algorithmics
Identifiers:LOCALID:C125673F004B2D7B-73BDC324043F9E79C12577E7003F663C-...
URL:http://dx.doi.org/10.1093/bioinformatics/btq420
DOI:10.1093/bioinformatics/btq420
ISSN:1367-4803
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.