Datalogisk Institut, DIKU > Forskning > Algorithms and Programming Languages (APL) > Computational Biology
Computational Biology
Contact person: Pawel Winter pawel@diku.dk
Bioinformatics and Computational Biology are interdisciplinary fields that apply techniques of computer science, applied mathematics, statistics, and biochemistry to solve biological problems. Following the definitions of National Institute of Health (USA), bioinformatics is ''research, development, or application of computational tools and approaches for expanding the use of biological, medical, behavioral or health data, including those to acquire, store, organize, archive, analyze, or visualize such data.'' Computational biology is concerned with ''development and application of dataanalytical and theoretical methods, mathematical modelling and computational simulation techniques to the study of biologial, behavioral, and social systems.''
[Protein Folding] [Computational Geometry and Proteins] [Evolutionary Trees]
Protein Folding and Structure Prediction
The protein folding (PF) has mesmerised researchers all over the world for decades. Proteins are relatively large molecules made of linear sequences of amino acids (small molecules, 20 different kinds). Proteins typically consist of 100500 amino acids. Upon creation, linear sequences of (known) amino acids fold into 3d structures with their surfaces determining the functions. Normally, identical sequences of amino acids fold to the same 3d structures. Folding is extremely fast (within milliseconds to seconds). Even though a considerable knowledge of molecular dynamics governing the folding of amino acid sequences ia available, researchers have not been able to completely understand the folding process. Complex energy interrelations between amino acids (including amino acids far apart in the linear sequences) also make it very difficult to simulate folding for all but very short proteins.
Instead of investigating PF, many groups are currently working on protein structure prediction (PSP). Here, the research focus is on predicting final folded 3d structures of proteins while disregarding folding processes. The vast number of degrees of freedom in linear sequences and in amino acids, makes also this problem very difficult. The reason for this is of course that the number of ways a chain of amino acids can twist and turn around each other is so vast that finding the correct 3d structure is indeed like looking for a needle in a hay stack. Reducing the number of degrees of freedom (by simplifying the linear sequences, by limiting the positions of amino acids to prespecified apropriately chosen grid positions, and by simplifying the objective functions), various optimization techniques have been applied.
Recent Theses
Glennie Helles
Searching for the native structures of proteins
Ph.D. Thesis, Dept. of Computer Science, Univ. of Copenhagen (2010)
Rasmus Fonseca
Ab initio protein structure prediction using Bezier curve representation
M.Sc. Thesis, Dept. of Computer Science, Univ. of Copenhagen (2009)
Best Danish Computer Science M.Sc. Thesis Award (2009)
Martin Paluszewski
Algorithms for protein structure prediction
Ph.D. Thesis, Dept. of Computer Science, Univ. of Copenhagen (2008)
Ranking Beta Sheet Topologies of Proteins
Abstract: One of the main reasons why ab initio protein structure predictors do not perform very well is their inability to reliably identify longrange interactions between amino acids. To achieve reliable longrange interactions, all potential pairings of betastrands (betatopologies) of a given protein are enumerated. The betatopologies are enumerated such that it is certain that the native betatopology is among the enumerated. [full abstract]
Rasmus Fonseca, Glennie Helles and Pawel Winter 
Protein Structure Prediction Using Bee Colony Optimization Heuristic
Predicting the native structure of proteins is one of the most challenging problems in molecular biology. The goal is to determine the threedimensional structure from the onedimensional amino acid sequence. De novo prediction algorithms seek to do this by developing a representation of the proteins structure, an energy potential and some optimization algorithm that finds the structure with minimal energy. Bee Colony Optimization (BCO) is a relatively new approach to solving optimization problems based on the foraging behaviour of bees. Several variants of BCO have been suggested in the literature. We have devised a new variant that unifies the existing and is much more flexible with respect to replacing the various elements of the BCO. In particular, this applies to the choice of the local search as well as the method for generating scout locations and performing the waggle dance. We apply our BCO method to generate good solutions to the protein structure prediction problem. The results show that BCO generally finds better solutions than simulated annealing which so far has been the metaheuristic of choice for this problem.
Rasmus Fonseca, Martin Paluszewski and Pawel Winter 
Improving Search for Low Energy Protein Structures with an Iterative Niche Genetic Algorithm
In attempts to predict the tertiary structure of proteins we use almost exclusively metaheuristics. However, despite known differences in performance of metaheuristics for different problems, the effect of the choice of metaheuristic has received precious little attention in this field. Particularly parallel implementations have been demonstrated to generally outperform their sequential counterparts, but they are nevertheless used to a much lesser extent for protein structure prediction. In this work we focus strictly on parallel algorithms for protein structure prediction and propose a parallel algorithm, which adds an iterative layer to the traditional niche genetic algorithm. We implement both the traditional niche genetic algorithm and the parallel tempering algorithm in a fashion that allows us to compare the algorithms and look at how they differ in performance. The results show that the iterative niche algorithm converges much faster at lower energy structures than both the traditional niche genetic algorithm and the parallel tempering algorithm.
Glennie Helles 
Predicting Dihedral Angle Probability Distributions
BACKGROUND: Predicting the threedimensional structure of a protein from its amino acid sequence is currently one of the most challenging problems in bioinformatics. The internal structure of helices and sheets is highly recurrent and help reduce the search space significantly. However, random coil segments make up nearly 40% of proteins and they do not have any apparent recurrent patterns, which complicates overall prediction accuracy of protein structure prediction methods. Luckily, previous work has indicated that coil segments are in fact not completely random in structure and flanking residues do seem to have a significant influence on the dihedral angles adopted by the individual amino acids in coil segments. In this work we attempt to predict a probability distribution of these dihedral angles based on the flanking residues. While attempts to predict dihedral angles of coil segments have been done previously, none have, to our knowledge, presented comparable results for the probability distribution of dihedral angles. RESULTS: In this paper we develop an artificial neural network that uses an inputwindow of amino acids to predict a dihedral angle probability distribution for the middle residue in the inputwindow. The trained neural network shows a significant improvement (468%) in predicting the most probable bin (covering a 30 degrees x 30 degrees area of the dihedral angle space) for all amino acids in the data set compared to baseline statistics. An accuracy comparable to that of secondary structure prediction ( approximately 80%) is achieved by observing the 20 bins with highest output values. CONCLUSION: Many different protein structure prediction methods exist and each uses different tools and auxiliary predictions to help determine the native structure. In this work the sequence is used to predict local context dependent dihedral angle propensities in coilregions. This predicted distribution can potentially improve tertiary structure prediction methods that are based on sampling the backbone dihedral angles of individual amino acids. The predicted distribution may also help predict local structure fragments used in fragment assembly methods. Glennie Helles and Rasmus FonsecaPredicting dihedral angle probability distributions for protein coil residues from primary sequence using neural networks BMC Bioinformatics 10, No. 338 (2009) 13 p. 
A Comparative Study of the Reported Performance of Ab Initio Protein Structure Prediction Algorithms
Protein structure prediction is one of the major challenges in bioinformatics today. Throughout the past five decades, many different algorithmic approaches have been attempted, and although progress has been made the problem remains unsolvable even for many small proteins. While the general objective is to predict the threedimensional structure from primary sequence, our current knowledge and computational power are simply insufficient to solve a problem of such high complexity. Some prediction algorithms do, however, appear to perform better than others, although it is not always obvious which ones they are and it is perhaps even less obvious why that is. In this review, the reported performance results from 18 different recently published prediction algorithms are compared. Furthermore, the general algorithmic settings most likely responsible for the difference in the reported performance are identified, and the specific settings of each of the 18 prediction algorithms are also compared. The average normalized r.m.s.d. scores reported range from 11.17 to 3.48. With a performance measure including both r.m.s.d. scores and CPU time, the currently bestperforming prediction algorithm is identified to be the ITASSER algorithm. Two of the algorithmic settingsprotein representation and fragment assemblywere found to have definite positive influence on the running time and the predicted structures, respectively. There thus appears to be a clear benefit from incorporating this knowledge in the design of new prediction algorithms.
Glennie Helles
Glennie Helles 
Protein Structure Prediction Using Tabu Search and HalfSphere Exposure Measure
Here, we study the reconstruction of a protein's C_alpha trace solely from a CN vector or a pair of up/down vectors (HSE vector). This problem could become important for de novo structure prediction when the vectors are predicted. We define potential functions based on the HSE or CNvectors and minimize them using two metaheuristics: Monte Carlo simulation (MCS) and tabu search (TS). MCS has been widely used for protein structure prediction, and TS has been applied with great success to many optimization problems, but has rarely been used for protein structure prediction.
Martin Paluszewski, Thomas Hamelryck and Pawel Winter 
Branch and Bound Algorithm for Protein Structure Prediction Using Efficient Bounding
We propose a new discrete model which makes use of secondary structure information and propose a novel branch and bound algorithm for finding global minimum structures. The energy function is very simple while structures obtained are of very high quality compared to the native structure of the protein. The model only depends on the position of C_alphaatoms and is based on predictable contact and halfsphereexposure numbers. The success of the branch and bound algorithm comes from the simplicity of the energy function which allows for efficient lower bound calculations of the energy.
Martin Paluszewski and Pawel Winter 
Computational Geometry and Proteins
Adjustable Chain Trees
A modified version of chain trees that adjust themselves to the changing conformations of folding proteins is introduced. Computational results indicate that the number of intersection checks of bounding volumes is substantially reduced both in connection with the clash tests and the free energy calculations.
Pawel Winter and Rasmus Fonseca

Protein Packing Quality Using Delaunay Complexes
Rasmus Fonseca, Pawel Winter and Kevin Karplus
Protein Packing Quality Using Delaunay Complexes
Proc. of 8th Int. Symp. on Voronoi Diagrams in Science and Engineering, ISVD'11, Qingdao, China (2011)
Alpha Shapes and Proteins
Abstract: We provide a unified description of (weighted) alphashapes, betashapes and the corresponding simplicial complexes. We discuss their applicability to various proteinrelated problems. We also discuss filtrations of alphashapes and touch upon related persistence issues. We claim that the full potential of alphashapes and related geometrical constructs in proteinrelated problems yet remains to be realized and verified. We suggest parallel algorithms for (weighted) alphashapes, and we argue that future use of filtrations and kinetic variants for larger proteins will need such implementations.
Pawel Winter, Henrik Sterner and Peter Sterner
Henrik Sterner and Peter Sterner 
Evolutionary Trees
Evolutionary trees, also called phylogenetic trees show the evolutionary interrelationships between various species. In recent years, due to the explosion of available data, species are typically represented by appropriate DNA or protein sequences.
There is surprising number of diiferent methods that have been used to determine evolutionary trees. They can be subdivided into four main groups. Parsimony methods are based on the Occam's razor principle: Whem given the choice between two explanations, choose the simpler one. In evolutionary trees, this usually amounts to looking for a tree with fewest number of evolutionary changes between interrelated species. Maximum likelihood methods are based on probabilistic models of evolution. Given such a model, the likelihood that a tree with given topology is the sought evolutionary tree, can be calculated. The tree with the maximum likelihood is of course selected as the evolutionary tree. Consensus methods attempt to find evolutionary trees for all species using trees for (usually small) subsets of species (which are much easier to determine for biologists)). Finally, distance methods are based on appropriately defined distances between species (for example appropriate edit distances between pairs of DNA or protein sequences). Once distances are given, the problem reduces to that of determining a minimum cost tree satisfying some side constraints.
Research on evolutionary trees at DIKU focused so far on distance methods. In particular, our group suggested a novel distancebased approach. Species are represented by points in an appropriately chosen highdimensional space such that the distances beetween points correspond to distances between DNA or protein sequences. Multidimensional scaling is used to determine the locations of points. Once located, the problems reduces to that of finding minimal Steiner tree for the points (possibly with appropriate side constraints). Initial work suggests that the approach has some potential. Exploiting our indepth knowledge of the Steiner tree problem here at DIKU may prove essential for making this approach a useful alternative to such distance methods as neighbor joining. This ongoing research has been carried out in cooperation with Dorin Thomas and Marcus Brazil from the Dept. of Engineering, Univ. of Melbourne.
M. Brazil, D.A. Thomas, B.K. Nielsen, P. Winter, C. WulffNilsen and M. ZachariasenA novel approach to phylogenetic tress: ddimensional geometric Steiner trees
Networks 53 (2009) 104111 [doi] [pdf]
[top]