Back to Search
Start Over
Structural alignment of protein descriptors – a combinatorial model
- Source :
- BMC Bioinformatics
- Publication Year :
- 2016
- Publisher :
- Springer Science and Business Media LLC, 2016.
-
Abstract
- Background Structural alignment of proteins is one of the most challenging problems in molecular biology. The tertiary structure of a protein strictly correlates with its function and computationally predicted structures are nowadays a main premise for understanding the latter. However, computationally derived 3D models often exhibit deviations from the native structure. A way to confirm a model is a comparison with other structures. The structural alignment of a pair of proteins can be defined with the use of a concept of protein descriptors. The protein descriptors are local substructures of protein molecules, which allow us to divide the original problem into a set of subproblems and, consequently, to propose a more efficient algorithmic solution. In the literature, one can find many applications of the descriptors concept that prove its usefulness for insight into protein 3D structures, but the proposed approaches are presented rather from the biological perspective than from the computational or algorithmic point of view. Efficient algorithms for identification and structural comparison of descriptors can become crucial components of methods for structural quality assessment as well as tertiary structure prediction. Results In this paper, we propose a new combinatorial model and new polynomial-time algorithms for the structural alignment of descriptors. The model is based on the maximum-size assignment problem, which we define here and prove that it can be solved in polynomial time. We demonstrate suitability of this approach by comparison with an exact backtracking algorithm. Besides a simplification coming from the combinatorial modeling, both on the conceptual and complexity level, we gain with this approach high quality of obtained results, in terms of 3D alignment accuracy and processing efficiency. Conclusions All the proposed algorithms were developed and integrated in a computationally efficient tool descs-standalone, which allows the user to identify and structurally compare descriptors of biological molecules, such as proteins and RNAs. Both PDB (Protein Data Bank) and mmCIF (macromolecular Crystallographic Information File) formats are supported. The proposed tool is available as an open source project stored on GitHub (https://github.com/mantczak/descs-standalone). Electronic supplementary material The online version of this article (doi:10.1186/s12859-016-1237-9) contains supplementary material, which is available to authorized users.
- Subjects :
- Models, Molecular
0301 basic medicine
Protein structure database
Combinatorial optimization
Time Factors
Theoretical computer science
Computer science
Structural alignment
Protein Data Bank (RCSB PDB)
Sequence alignment
Biochemistry
Structural genomics
03 medical and health sciences
Structural bioinformatics
Protein structure
Structural Biology
Amino Acid Sequence
Databases, Protein
Molecular Biology
Time complexity
Native structure
Peptide sequence
chemistry.chemical_classification
030102 biochemistry & molecular biology
Protein molecules
Methodology Article
Applied Mathematics
Biomolecule
Structural comparison
Proteins
A protein
computer.file_format
Protein Data Bank
Protein tertiary structure
Computer Science Applications
030104 developmental biology
chemistry
DNA microarray
Sequence Alignment
computer
Algorithms
Macromolecule
Subjects
Details
- ISSN :
- 14712105
- Volume :
- 17
- Database :
- OpenAIRE
- Journal :
- BMC Bioinformatics
- Accession number :
- edsair.doi.dedup.....fdf937b9931b9ff555b2fa4f1ea75736