The Discretizable Molecular Distance Geometry Problem seems Easier on Proteins

Leo Liberti (), Carlile Lavor () and Antonio Mucherino ()
Additional contact information
Leo Liberti: LIX, École Polytechnique
Carlile Lavor: University of Campinas, Department of Applied Maths
Antonio Mucherino: University of Rennes 1, IRISA

Chapter Chapter 3 in Distance Geometry, 2013, pp 47-60 from Springer

Abstract: Abstract Distance geometry methods are used to turn a set of interatomic distances given by Nuclear Magnetic Resonance (NMR) experiments into a consistent molecular conformation. In a set of papers (see the survey [8]) we proposed a Branch-and-Prune (BP) algorithm for computing the set X of all incongruent embeddings of a given protein backbone. Although BP has a worst-case exponential running time in general, we always noticed a linear-like behaviour in computational experiments. In this chapter we provide a theoretical explanation to our observations. We show that the BP is fixed-parameter tractable on protein-like graphs and empirically show that the parameter is constant on a set of proteins from the Protein Data Bank.

Keywords: Branch-and-Prune; Symmetry; Distance geometry; Fixed-parameter tractable; Protein conformation (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-5128-0_3

Ordering information: This item can be ordered from
http://www.springer.com/9781461451280

DOI: 10.1007/978-1-4614-5128-0_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().