Connectivity Inference in Mass Spectrometry Based Structure Determination

摘要

We consider the following Minimum Connectivity Inference problem (MCI), which arises in structural biology: given vertex sets V_i ? V, i ∈ I, find a graph G = (V,E) minimizing the size of the edge set E, such that the sub-graph of G induced by each V_i is connected. This problem arises in structural biology, when one aims at finding the pairwise contacts between the proteins of a protein assembly, given the lists of proteins involved in sub-complexes. We present four contributions.