Maximum feasible subsystems of distance geometry constraints

Maurizio Bruglieri (), Roberto Cordone () and Leo Liberti ()
Additional contact information
Maurizio Bruglieri: Politecnico di Milano
Roberto Cordone: Università degli Studi di Milano
Leo Liberti: LIX CNRS Ecole Polytechnique, Institut Polytechnique de Paris

Journal of Global Optimization, 2022, vol. 83, issue 1, No 3, 29-47

Abstract: Abstract We study the problem of satisfying the maximum number of distance geometry constraints with minimum experimental error. This models the determination of the shape of proteins from atomic distance data which are obtained from nuclear magnetic resonance experiments and exhibit experimental and systematic errors. Experimental errors are represented by interval constraints on Euclidean distances. Systematic errors occur from a misassignment of distances to wrong atomic pairs: we represent such errors by maximizing the number of satisfiable distance constraints. We present many mathematical programming formulations, as well as a “matheuristic” algorithm based on reformulations, relaxations, restrictions and refinement. We show that this algorithm works on protein graphs with hundreds of atoms and thousands of distances.

Keywords: Protein conformation; MINLP; Diagonally dominant programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01003-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jglopt:v:83:y:2022:i:1:d:10.1007_s10898-021-01003-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01003-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().