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.

Maximum feasible subsystems of distance geometry constraints / M. Bruglieri, R. Cordone, L. Liberti. - In: JOURNAL OF GLOBAL OPTIMIZATION. - ISSN 0925-5001. - (2021), pp. 1-19. [Epub ahead of print] [10.1007/s10898-021-01003-4]

Maximum feasible subsystems of distance geometry constraints

R. Cordone
Secondo
;
2021

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.
Diagonally dominant programming; MINLP; Protein conformation
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
mar-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
MAXFS_DGP_JOGO.pdf

embargo fino al 06/03/2022

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 990.67 kB
Formato Adobe PDF
990.67 kB Adobe PDF Visualizza/Apri
Bruglieri2021_Article_MaximumFeasibleSubsystemsOfDis(1).pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 505.37 kB
Formato Adobe PDF
505.37 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/870069
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact