Repository logoGCRIS

Scopus İndeksli Yayınlar Koleksiyonu

Permanent URI for this collectionhttps://hdl.handle.net/20.500.12573/395

Browse

Filters

2017 - 201912020 - 20241

Settings

Language: search.filters.language.enSubject: search.filters.subject.Dynamic Programming

Search Results

Now showing 1 - 2 of 2
  • Article
    Citation - WoS: 7
    Citation - Scopus: 11
    Protein Β-Sheet Prediction Using an Efficient Dynamic Programming Algorithm
    (Elsevier Sci Ltd, 2017-10) Sabzekar, Mostafa; Naghibzadeh, Mahmoud; Eghdami, Mandie; Aydin, Zafer
    Predicting the beta-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 beta-sheets. To achieve reliable long-range interactions, a promising approach is to enumerate and rank all beta-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 beta-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 beta-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 beta-sheet structures with high number of beta-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 beta-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 at http://www.conceptsgate.com/BetaTop.rar. (C) 2017 Elsevier Ltd. All rights reserved.
  • Article
    Citation - WoS: 29
    Citation - Scopus: 31
    A Simulation-Based Approximate Dynamic Programming Approach to Dynamic and Stochastic Resource-Constrained Multi-Project Scheduling Problem
    (Elsevier, 2024) Satic, U.; Jacko, P.; Kirkbride, C.
    We consider the dynamic and stochastic resource -constrained multi -project scheduling problem which allows for the random arrival of projects and stochastic task durations. Completing projects generates rewards, which are reduced by a tardiness cost in the case of late completion. Multiple types of resource are available, and projects consume different amounts of these resources when under processing. The problem is modelled as an infinite -horizon discrete -time Markov decision process and seeks to maximise the expected discounted long -run profit. We use an approximate dynamic programming algorithm (ADP) with a linear approximation model which can be used for online decision making. Our approximation model uses project elements that are easily accessible by a decision -maker, with the model coefficients obtained offline via a combination of Monte Carlo simulation and least squares estimation. Our numerical study shows that ADP often statistically significantly outperforms the optimal reactive baseline algorithm (ORBA). In experiments on smaller problems however, both typically perform suboptimally compared to the optimal scheduler obtained by stochastic dynamic programming. ADP has an advantage over ORBA and dynamic programming in that ADP can be applied to larger problems. We also show that ADP generally produces statistically significantly higher profits than common algorithms used in practice, such as a rule -based algorithm and a reactive genetic algorithm.