New Error Measures and Methods for Realizing Protein Graphs from Distance Data

Autor: Leo Liberti, Carlile Lavor, Nelson Maculan, Ky Khac Vu, Claudia D’Ambrosio
Přispěvatelé: Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), FPT University, Instituto de Matemática, Estatística e Computação Científica [Brésil] (IMECC), Universidade Estadual de Campinas (UNICAMP), Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ), Universidade Federal do Rio de Janeiro (UFRJ)
Jazyk: angličtina
Rok vydání: 2017
Předmět:
Computational Geometry (cs.CG)
FOS: Computer and information sciences
0209 industrial biotechnology
0211 other engineering and technologies
02 engineering and technology
Interval (mathematics)
Quantitative Biology - Quantitative Methods
Measure (mathematics)
Theoretical Computer Science
Combinatorics
020901 industrial engineering & automation
Quadratic equation
Mathematics - Metric Geometry
protein conformation
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Optimization and Control
Quantitative Methods (q-bio.QM)
Mathematics
Discrete mathematics
Semidefinite programming
021103 operations research
Heuristic
Metric Geometry (math.MG)
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Solver
Euclidean distance
Computational Theory and Mathematics
Optimization and Control (math.OC)
FOS: Biological sciences
Computer Science - Computational Geometry
Geometry and Topology
Realization (systems)
distance geometry
mathematical programming
Zdroj: Discrete and Computational Geometry
Discrete and Computational Geometry, Springer Verlag, 2017, 57 (2), pp.371-418. ⟨10.1007/s00454-016-9846-7⟩
ISSN: 0179-5376
1432-0444
Popis: International audience; The interval Distance Geometry Problem (i DGP) consists in finding a realization in R K of a simple undirected graph G = (V, E) with nonnegative intervals assigned to the edges in such a way that, for each edge, the Euclidean distance between the realization of the adjacent vertices is within the edge interval bounds. In this paper, we focus on the application to the conformation of proteins in space, which is a basic step in determining protein function: given interval estimations of some of the inter-atomic distances, find their shape. Among different families of methods for accomplishing this task, we look at mathematical programming based methods, which are well suited for dealing with intervals. The basic question we want to answer is: what is the best such method for the problem? The most meaningful error measure for evaluating solution quality is the coordinate root mean square deviation. We first introduce a new error measure which addresses a particular feature of protein backbones, i.e. many partial reflections also yield acceptable backbones. We then present a set of new and existing quadratic and semidefinite programming formulations of this problem, and a set of new and existing methods for solving these formulations. Finally, we perform a computational evaluation of all the feasible solver+formulation combinations according to new and existing error measures, finding that the best methodology is a new heuristic method based on multiplicative weights updates.
Databáze: OpenAIRE
Externí odkaz: