Optimal pathway reconstruction on 3D NMR maps

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.