1. Minimal NMR distance information for rigidity of protein graphs
- Author
-
Leo Liberti, Benjamin Bardiaux, Michael Nilges, Thérèse E. Malliavin, Bradley Worley, Bruce R. Donald, Carlile Lavor, Instituto de Matemática, Estatística e Computação Científica [Brésil] (IMECC), Universidade Estadual de Campinas (UNICAMP), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Duke University [Durham], Bioinformatique structurale, Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), C.L. would like to thank the Brazilian research agencies CNPq, FAPESP and B.D. would like to thank the NIH grants R01 GM-118543 and R01 GM-078031 for their financial support., We are also thankful to Angela Gronenborn and Michael Souza, for discussions that clarify some ideas in the paper, and to anonymous referees that made very important comments to this work., Bioinformatique structurale - Structural Bioinformatics, Universidade Estadual de Campinas = University of Campinas (UNICAMP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Computational complexity theory ,Nuclear Magnetic Resonance ,0211 other engineering and technologies ,Structure (category theory) ,Rigidity (psychology) ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Topology ,01 natural sciences ,Article ,Cardinality ,Protein structure ,Distance Geometry ,Discrete Mathematics and Combinatorics ,Molecule ,Combinatorial search ,Mathematics ,Quantitative Biology::Biomolecules ,[SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Structural Biology [q-bio.BM] ,Applied Mathematics ,Solution set ,021107 urban & regional planning ,[SDV.BBM.BP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biophysics ,[SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biomolecules [q-bio.BM] ,Vertex orders ,010201 computation theory & mathematics ,[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] ,Molecular structure - Abstract
International audience; Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.
- Published
- 2019