fulfill a large variety of tasks in living systems, be it as reaction catalysts, molecular sensors, immune responses, or driving muscular activity [@voet2010biochemistry]. Knowing a protein’s 3D structure is a requirement for any detailed understanding of its function, and functional or structural disorder can lead to disease. Structure resolution techniques have made strong progress in recent years: biomolecules that were inaccessible a decade ago can now be structurally resolved, as exemplified by the rapid growth of structural databases [@PDB2015]. The resolution techniques, however, do not directly provide structural information as 3D coordinates. Instead, [*e.g.,* ]{}X-ray crystallography yields a diffraction pattern which has to be translated into a structural model. Similarly, Nuclear Magnetic Resonance (NMR) techniques measure coupled atomic spins, which can be translated into pairwise distances between specific atoms. These distances are typically incomplete, [*i.e.,* ]{}not all spatially adjacent atom pairs are detected [@stothers2012carbon]. Also computational tools, such as co-evolutionary analysis of multiple-sequences alignments of protein [@schug2009; @uguzzoni2017; @ovchinnikov2017] or RNA families [@leonadis2015] can provide distance constraints between residues for biomolecular structure prediction. Conceptually, one can understand the information provided by these techniques as incomplete and erroneous parts of the complete distance matrix. **Motivation.** Our goal is to provide an 