Optimal pathway reconstruction on 3D NMR maps

Marta Szachniuk, Maria Cristina De Cola, Giovanni Felici, Dominique De Werra, Jacek Błazewicz

Research output: Contribution to journalArticlepeer-review


A three-dimensional Nuclear Magnetic Resonance (NMR) map displays the results of NMR experiments, that allow to determine the shape of a biological molecule. Shape calculation starts from a reconstruction of a sequence of NMR signals, which is equivalent to finding a specific path in a graph representation of the problem. Let G=(V,E) be a graph that models the interactions reflected on an NMR map. Its edges are colored with c colors, where each color corresponds to one of c different relationships between the signals. The sequence of interactions under consideration is represented using a concept of an orderly colored path in the c-edge-colored graph. In this paper, we consider the problem of finding the required arrangement of NMR signals on the 3D map and we present its graph representation. We discuss the computational complexity of the problem, we consider its two alternative integer programming models, and evaluate the performance of an optimization algorithm based on the solution of their relaxation combined with the separation of fractional cycles in a Branch & Cut scheme.

Original languageEnglish
Pages (from-to)134-149
Number of pages16
JournalDiscrete Applied Mathematics
Publication statusPublished - Feb 19 2015


  • Integer programming
  • longest path
  • NMR assignment
  • Orderly colored

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Optimal pathway reconstruction on 3D NMR maps'. Together they form a unique fingerprint.

Cite this