Protein β-sheet prediction using an efficient dynamic programming algorithm. (October 2017)

• Record Type: Journal Article
• Authors: Sabzekar, Mostafa; Naghibzadeh, Mahmoud; Eghdami, Mahdie; Aydin, Zafer
• Is Part Of: Computational biology and chemistry. Volume 70(2017)
• Page Start: 142
• Page End: 155
• Publication Date: 2017-10
• Subjects: β-sheet structure prediction -- Dynamic programming -- Repetitive calculation -- Sheet-tree -- Grouping-tree; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2017.08.011
• Languages: English
• ISSNs: 1476-9271

Abstract

Graphical abstract: Highlights: Protein β-sheet prediction is one of the most critical intermediate steps towards the prediction of its 3D structure. The proposed algorithm utilizes a dynamic programming approach to reduce the time complexity of the problem. It is designed in such a way that we can remove many nodes which will not be reused at higher levels of the tree. It can be applicable to predict β-sheet structure of proteins with higher number of β-strands. Abstract: Predicting the β-sheet structure of a protein is one of the most important intermediate steps towards the identification of its tertiary structure. However, it is regarded as the primary bottleneck due to the presence of non-local interactions between several discontinuous regions in β-sheets. To achieve reliable long-range interactions, a promising approach is to enumerate and rank all β-sheet conformations for a given protein and find the one with the highest score. The problem with this solution is that the search space of the problem grows exponentially with respect to the number of β-strands. Additionally, brute-force calculation in this conformational space leads to dealing with a combinatorial explosion problem with intractable computational complexity. The main contribution of this paper is to generate and search the space of the problem efficiently to reduce the time complexity of the problem. To achieve this, two tree structures, called sheet-tree and grouping-tree, are proposed. They model the search space by breaking it into sub-problems. Then, an advanced dynamic programming is proposed that stores the intermediate results, avoids repetitive calculation by repeatedly uses them efficiently in successive steps and reduces the space of the problem by removing those intermediate results that will no longer be required in later steps. As a consequence, the following contributions have been made. Firstly, more accurate β-sheet structures are found by searching all possible conformations, and secondly, the time complexity of the problem is reduced by searching the space of the problem efficiently which makes the proposed method applicable to predict β-sheet structures with high number of β-strands. Experimental results on the BetaSheet916 dataset showed significant improvements of the proposed method in both execution time and the prediction accuracy in comparison with the state-of-the-art β-sheet structure prediction methods Moreover, we investigate the effect of different contact map predictors on the performance of the proposed method using BetaSheet1452 dataset. The source code is available athttp://www.conceptsgate.com/BetaTop.rar .