Biomedical subjects

Alena Shmygelska

Publications and source records attributed to Alena Shmygelska.

2 recordsLinked to original sources

PubMed2005

An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem.

BACKGROUND: The protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. Various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including Monte Carlo methods, Evolutionary Algorithms, Tabu Search and hybrid approaches. In our work, we have introduced an ant colony optimisation (ACO) algorithm to address the non-deterministic polynomial-time hard (NP-hard) combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model - the 2-dimensional (2D) and 3-dimensional (3D) hydrophobic-polar (HP) model. RESULTS: We present an improvement of our previous ACO algorithm for the 2D HP model and its extension to the 3D HP model. We show that this new algorithm, dubbed ACO-HPPFP-3, performs better than previous state-of-the-art algorithms on sequences whose native conformations do not contain structural nuclei (parts of the native fold that predominantly consist of local interactions) at the ends, but rather in the middle of the sequence, and that it generally finds a more diverse set of native conformations. CONCLUSIONS: The application of ACO to this bioinformatics problem compares favourably with specialised, state-of-the-art methods for the 2D and 3D HP protein folding problem; our empirical results indicate that our rather simple ACO algorithm scales worse with sequence length but usually finds a more diverse ensemble of native states. Therefore the development of ACO algorithms for more complex and realistic models of protein structure holds significant promise.

Algorithms↗

PubMed2005

Search for folding nuclei in native protein structures.

UNLABELLED: The problem of finding folding nuclei (a set of native contacts that play an important role in folding) along with identifying folding pathways (a time-ordered sequence of folding events) of proteins is one of the most important problems in protein chemistry. Here we propose a novel and simple approach to address this problem as follows: given the topology of the native state, identify native contacts that form folding nuclei based on a graph-theoretical approach that considers effective contact order (effective loop closure) as its objective function. MOTIVATION: A number of computational methods for the prediction of folding nuclei already exists in the literature, but most of them rely on restrictive assumptions about the nature of nuclei or the process of folding. Our motivation is to develop a simple, efficient and robust algorithm to find an ensemble of pathways with the lowest effective contact order and to identify contacts that are crucial for folding. RESULTS: Our approach is different from the previously used methods in that it uses efficient graph algorithms and does not formulate restrictive assumptions about folding nuclei. Our predictions provide more details concerning the protein folding pathway than most other methods in the literature. We demonstrate the success of our approach by predicting folding nuclei for a dataset of proteins for which experimental kinetic data is available. We show that our method compares favourably with other methods in the literature and that its results agree with experimental results. AVAILABILITY: The executable for the proposed algorithm is available at http://www.cs.ubc.ca/~/foldingnuclei.html

Algorithms↗