published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

Thesis (Ph. D.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

Thesis (M.S.)--Rochester Institute of Technology, 2009. / Typescript. Includes bibliographical references (leaves 34-36).

Finding wide tunnels in protein structures is an important problem in Structural Bioinformatics with applications in various areas such as drug design. Several algorithms have been proposed for finding wide tunnels in a fixed protein conformation. However, to the best of our knowledge, none of the existing work have considered widening the tunnel, i.e., finding a wider tunnel in an alternative conformation of the given structure. In this thesis we initiate this line of research by proposing a tunnel-widening algorithm which aims to make the tunnel wider by a slight local change in the structure of the protein. Given a fixed conformation of a protein with a point located inside it, we first describe an algorithm to identify the widest tunnel from that point to the outside environment of the protein. Then we try to make the tunnel wider by considering various alternative conformations of the protein. We only consider conformations whose energies are not much higher than the energy of the initial conformation. Among these alternative conformations we select the one with the widest tunnel. However, the alternative conformation with the widest tunnel might not be accessible from the initial structure. Thus, in the next step we develop three algorithms for finding a feasible transition pathway from the initial structure to the alternative conformation, i.e., a sequence of intermediate conformations between the initial structure and the alternative conformation such that the energy values of all these intermediate conformations are close to the energy of the initial structure. We evaluate our tunnel-finding and tunnel-widening algorithms on various proteins. Our experiments show that in most cases we can make the tunnel wider in an alternative conformation. However, there are cases in which we find a wider tunnel in an alternative conformation, but the energy value of the alternative conformation is much higher than the energy of the initial structure. We also implemented our three pathway-finding algorithms and tested them on various instances. Our experiments show that although in most cases we can find a feasible transition pathway, there are cases in which the alternative conformation has energy close to the initial structure, but our algorithms cannot find any feasible pathway from the initial structure to the alternative conformation. Furthermore, there is a trade-off between the running time and accuracy of the three pathway-finding algorithms.

Finding wide tunnels in protein structures is an important problem in Structural Bioinformatics with applications in various areas such as drug design. Several algorithms have been proposed for finding wide tunnels in a fixed protein conformation. However, to the best of our knowledge, none of the existing work have considered widening the tunnel, i.e., finding a wider tunnel in an alternative conformation of the given structure. In this thesis we initiate this line of research by proposing a tunnel-widening algorithm which aims to make the tunnel wider by a slight local change in the structure of the protein. Given a fixed conformation of a protein with a point located inside it, we first describe an algorithm to identify the widest tunnel from that point to the outside environment of the protein. Then we try to make the tunnel wider by considering various alternative conformations of the protein. We only consider conformations whose energies are not much higher than the energy of the initial conformation. Among these alternative conformations we select the one with the widest tunnel. However, the alternative conformation with the widest tunnel might not be accessible from the initial structure. Thus, in the next step we develop three algorithms for finding a feasible transition pathway from the initial structure to the alternative conformation, i.e., a sequence of intermediate conformations between the initial structure and the alternative conformation such that the energy values of all these intermediate conformations are close to the energy of the initial structure. We evaluate our tunnel-finding and tunnel-widening algorithms on various proteins. Our experiments show that in most cases we can make the tunnel wider in an alternative conformation. However, there are cases in which we find a wider tunnel in an alternative conformation, but the energy value of the alternative conformation is much higher than the energy of the initial structure. We also implemented our three pathway-finding algorithms and tested them on various instances. Our experiments show that although in most cases we can find a feasible transition pathway, there are cases in which the alternative conformation has energy close to the initial structure, but our algorithms cannot find any feasible pathway from the initial structure to the alternative conformation. Furthermore, there is a trade-off between the running time and accuracy of the three pathway-finding algorithms.

Thesis (Ph.D.)--Ohio University, June, 2008. / Title from PDF t.p. Includes bibliographical references.

<p>Medical advances often come as a result of understanding the underlying mechanisms of life. Life, in this sense, happens at various scales. A very complex and interesting one is the molecular scale. Understanding life’s mechanistic details at this level will provide the most promising therapies to modern ailments. Because of structure and function’s close relationship, knowledge of macromolecular structure provides invaluable insight into molecular mechanism.</p><p>A major tool used to get structural information at the molecular scale is X-ray crystallography. Such experiments result in an electron density map from which a model is built. Building such a model is a difficult task, especially at low resolu- tion where detailed features in the electron density deteriorate making it difficult to interpret. However, many advances in the field have greatly eased the model build- ing task, in fact, at high resolutions it has become automated. However, human inspection is still required to get a correct solution.</p><p>The largest boon to model building has been the application of structural knowl- edge. A prominent example is bond and dihedral angles. We often know what is absolutely not allowed and often convince ourselves we know everything that is al- lowed. This work focuses on the fuzzy border between allowed and disallowed. The hypothesis is that rare structural conformations exist but one needs to take great care in modeling them.</p><p>This work has two major components – rotamers (protein sidechain conformation)</p><p>and Hoogsteen base pairing in DNA. I first describe methods used to gain empirical knowledge about rotamers and how that knowledge is used in model validation. Part of this knowledge is rotamer-dependent bond angle deviations. I describe how the observation and quantitation of these deviations is used in a novel set of restraints in protein structure refinement. To provide structural context to rare rotamers, I describe where and why some occur.</p><p>My DNA work has focused on Hoogsteen base pairing. I describe a collaborative survey of existing Hoogsteen base pairs in the PDB. Lessons learned during the survey led to the other DNA topic, the detection and correction of mismodeled purines. I identified Hoogsteens in the PDB mismodeled as Watson-Crick base pairs. This work underscores that Hoogsteens are extremely rare but nonetheless do occur.</p><p>The fuzzy borderland between allowed and disallowed is a strange place filled with the most interesting structural features. My work here has focused on this area, bringing into view many rare conformations. Going forward we need to ensure that conformational frequency is taken into account during model building, refinement, and validation.</p> / Dissertation

Algoritmos meméticos são meta-heurísticas evolutivas voltadas intrinsecamente à exploração e incorporação de conhecimentos relacionados ao problema em estudo. Nesta dissertação, foi proposto um algoritmo memético multi populacional baseado em conhecimento para lidar com o problema de predição de estruturas tridimensionais de proteínas voltado à modelagem de estruturas livres de similaridades conformacionais com estruturas de proteínas determinadas experimentalmente. O algoritmo em questão, foi estruturado em duas etapas principais de processamento: (i) amostragem e inicialização de soluções; e (ii) otimização dos modelos estruturais provenientes da etapa anterior. A etapa I objetiva a geração e classificação de diversas soluções, a partir da estratégia Lista de Probabilidades Angulares, buscando a definição de diferentes grupos estruturais e a criação de melhores estruturas a serem incorporadas à meta-heurística como soluções iniciais das multi populações. A segunda etapa consiste no processo de otimização das estruturas oriundas da etapa I, realizado por meio da aplicação do algoritmo memético de otimização, o qual é fundamentado na organização da população de indivíduos em uma estrutura em árvore, onde cada nodo pode ser interpretado como uma subpopulação independente, que ao longo do processo interage com outros nodos por meio de operações de busca global voltadas a características do problema, visando o compartilhamento de informações, a diversificação da população de indivíduos, e a exploração mais eficaz do espaço de busca multimodal do problema O algoritmo engloba ainda uma implementação do algoritmo colônia artificial de abelhas, com o propósito de ser utilizado como uma técnica de busca local a ser aplicada em cada nodo da árvore. O algoritmo proposto foi testado em um conjunto de 24 sequências de aminoácidos, assim como comparado a dois métodos de referência na área de predição de estruturas tridimensionais de proteínas, Rosetta e QUARK. Os resultados obtidos mostraram a capacidade do método em predizer estruturas tridimensionais de proteínas com conformações similares a estruturas determinadas experimentalmente, em termos das métricas de avaliação estrutural Root-Mean-Square Deviation e Global Distance Total Score Test. Verificou-se que o algoritmo desenvolvido também foi capaz de atingir resultados comparáveis ao Rosetta e ao QUARK, sendo que em alguns casos, os superou. Corroborando assim, a eficácia do método. / Memetic algorithms are evolutionary metaheuristics intrinsically concerned with the exploiting and incorporation of all available knowledge about the problem under study. In this dissertation, we present a knowledge-based memetic algorithm to tackle the threedimensional protein structure prediction problem without the explicit use of template experimentally determined structures. The algorithm was divided into two main steps of processing: (i) sampling and initialization of the algorithm solutions; and (ii) optimization of the structural models from the previous stage. The first step aims to generate and classify several structural models for a determined target protein, by the use of the strategy Angle Probability List, aiming the definition of different structural groups and the creation of better structures to initialize the initial individuals of the memetic algorithm. The Angle Probability List takes advantage of structural knowledge stored in the Protein Data Bank in order to reduce the complexity of the conformational search space. The second step of the method consists in the optimization process of the structures generated in the first stage, through the applying of the proposed memetic algorithm, which uses a tree-structured population, where each node can be seen as an independent subpopulation that interacts with others, over global search operations, aiming at information sharing, population diversity, and better exploration of the multimodal search space of the problem The method also encompasses ad-hoc global search operators, whose objective is to increase the exploration capacity of the method turning to the characteristics of the protein structure prediction problem, combined with the Artificial Bee Colony algorithm to be used as a local search technique applied to each node of the tree. The proposed algorithm was tested on a set of 24 amino acid sequences, as well as compared with two reference methods in the protein structure prediction area, Rosetta and QUARK. The results show the ability of the method to predict three-dimensional protein structures with similar foldings to the experimentally determined protein structures, regarding the structural metrics Root-Mean-Square Deviation and Global Distance Total Score Test. We also show that our method was able to reach comparable results to Rosetta and QUARK, and in some cases, it outperformed them, corroborating the effectiveness of our proposal.

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 108-119).

<p>As of late 2009, the Protein Data Bank (PDB) has grown to contain over 70,000 models. This recent increase in the amount of structural data allows for more extensive explication of the governing principles of macromolecular folding and association to complement traditional studies focused on a single molecule or complex. PDB-wide characterization of structural features yields insights that are useful in prediction and validation of the 3D structure of macromolecules and their complexes. Here, these insights lead to a deeper understanding of protein--protein interfaces, full-atom critical assessment of increasingly more accurate structure predictions, a better defined library of RNA backbone conformers for validation and building 3D models, and knowledge-based automatic correction of errors in protein sidechain rotamers. </p><p>My study of protein--protein interfaces identifies amino acid pairing preferences in a set of 146 transient interfaces. Using a geometric interface surface definition devoid of arbitrary cutoffs common to previous studies of interface composition, I calculate inter- and intrachain amino acid pairing preferences. As expected, salt-bridges and hydrophobic patches are prevalent, but likelihood correction of observed pairing frequencies reveals some surprising pairing preferences, such as Cys-His interchain pairs and Met-Met intrachain pairs. To complement my statistical observations, I introduce a 2D visualization of the 3D interface surface that can display a variety of interface characteristics, including residue type, atomic distance and backbone/sidechain composition. </p><p>My study of protein interiors finds that 3D structure prediction from sequence (as part of the CASP experiment) is very close to full-atom accuracy. Validation of structure prediction should therefore consider all atom positions instead of the traditional Calpha-only evaluation. I introduce six new full-model quality criteria to assess the accuracy of CASP predictions, which demonstrate that groups who use structural knowledge culled from the PDB to inform their prediction protocols produce the most accurate results. </p><p>My study of RNA backbone introduces a set of rotamer-like "suite" conformers. Initially hand-identified by the Richardson laboratory, these 7D conformers represent backbone segments that are found to be genuine and favorable. X-ray crystallographers can use backbone conformers for model building in often poor backbone density and in validation after refinement. Increasing amounts of high quality RNA data allow for improved conformer identification, but also complicate hand-curation. I demonstrate that affinity propagation successfully differentiates between two related but distinct suite conformers, and is a useful tool for automated conformer clustering. </p><p>My study of protein sidechain rotamers in X-ray structures identifies a class of systematic errors that results in sidechains misfit by approximately 180 degrees. I introduce Autofix, a method for automated detection and correction of such errors. Autofix corrects over 40% of errors for Leu, Thr, and Val residues, and a significant number of Arg residues. On average, Autofix made four corrections per PDB file in 945 X-ray structures. Autofix will be implemented into MolProbity and PHENIX for easy integration into X-ray crystallography workflows.</p> / Dissertation