SSA: Subset sum approach to protein β-sheet structure prediction. (October 2021)

• Record Type: Journal Article
• Authors: Eghdami, Mahdie; Naghibzadeh, Mahmoud
• Is Part Of: Computational biology and chemistry. Volume 94(2021)
• Publication Date: 2021-10
• Subjects: Brute force approach with pruning -- Cardinality of the search space -- Protein β-sheet conformation; 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.2021.107552
• Languages: English
• ISSNs: 1476-9271

Abstract

Graphical abstract: Highlights: Calculation of the search space cardinality of protein β-sheet prediction, as performed for the first time. Usage of the subset sum approach for systematic and efficient generation of protein β-sheet's topology. Improvement in the performance of protein β-sheet prediction. Improvement in the execution time of β-sheet prediction. Demonstration of the possibility of parallel execution of the proposed predictor. Abstract: The three-dimensional structures of proteins provide their functions and incorrect folding of its β-strands can be the cause of many diseases. There are two major approaches for determining protein structures: computational prediction and experimental methods that employ technologies such as Cryo-electron microscopy. Due to experimental methods's high costs, extended wait times for its lengthy processes, and incompleteness of results, computational prediction is an attractive alternative. As the focus of the present paper, β-sheet structure prediction is a major portion of overall protein structure prediction. Prediction of other substructures, such as α-helices, is simpler with lower computational time complexities. Brute force methods are the most common approach and dynamic programming is also utilized to generate all possible conformations. The current study introduces the Subset Sum Approach (SSA) for the direct search space generation method, which is shown to outperform the dynamic programming approach in terms of both time and space. For the first time, the present work has calculated both the state space cardinality of the dynamic programming approach and the search space cardinality of the general brute force approaches. In regard to a set of pruning rules, SSA has demonstrated higher efficiency with respect to both time and accuracy in comparison to state-of-the-art methods.