A computing system for characterizing a target protein or an interaction of the target protein with an entity, the computing system comprising one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs singularly or collectively executing a method comprising:
- (A) forming a first data construct comprising an original graph G from an atomic model of the target protein, the original graph G comprising a first plurality of vertices and a first plurality of edges, wherein
- each residue in a first plurality of residues of the target protein is a member of an enumerated amino acid type set,
- each respective vertex in the first plurality of vertices represents a different residue in the first plurality of residues and is further assigned the amino acid type, in the enumerated amino acid type set, of the different residue, and
- each respective edge in the first plurality of edges uniquely represents a pair of vertices in the first plurality of vertices that are within a threshold distance of each other in the atomic model,
- (B) obtaining a primary nuclear Overhauser enhancement (NOE) dataset of a sample comprising the target protein in perdeuterated form, wherein
- a second plurality of residues have been isotopically labeled in the sample of the target protein, and
- each residue in the second plurality of residues is a member of the enumerated amino acid type set;
- (C) identifying a plurality of cross peaks in the primary NOE dataset, wherein each respective cross peak in the primary NOE dataset is generated by NOE interaction between an isotopic label in a different first residue and an isotopic label in a different second residue in the second plurality of residues;
- (D) forming a second data construct comprising an observed graph H from the plurality of cross peaks, the observed graph H comprising a second plurality of vertices and a second plurality of edges, wherein
- each respective vertex in the second plurality of vertices represents a different residue in the second plurality of residues,
- each respective edge in the second plurality of edges represents a corresponding cross peak in the plurality of cross peaks, and
- each respective vertex in the second plurality of vertices is assigned one or more amino types in the enumerated amino acid type set using amino acid type assignments made by the primary NOE dataset or one or more secondary NOE NMR datasets taken of the target protein;
- (E) creating a plurality of placements of the observed graph H onto the original graph G, wherein each respective placement in the plurality of placements (i) includes a plurality of mappings and (ii) maps all the vertices of the observed graph H onto different vertices in the original graph G, each mapping in the plurality of mappings assigning a vertex in the observed graph H to the original graph G, wherein each respective placement in the plurality of placements is subject to a set of constraints comprising:
- when a vertex v in the observed graph H is mapped to a vertex w in the original graph G, the amino acid type assigned vertex w in the original graph G is in the one or more amino acid types assigned vertex v, and
- for an observed edge {a, b} between a vertex a and a vertex b in the observed graph H, when vertex a is mapped to a vertex v and vertex b is mapped to a vertex w in the original graph G, there exists an edge {v, w} between the vertex v and the vertex w in the original graph G;
- (F) initializing each set in a plurality of sets, each set in the plurality of sets representing a different vertex in the observed graph H;
- (G) determining, for each respective set in the plurality of sets, a number of different mappings for the vertex i represented by the respective set in the observed graph H into the original graph G by polling the plurality of placements as a constraint satisfaction problem in which, for each respective possible assignment of the vertex i into the original graph G, when a determination is made that there exists a mapping in the plurality of mappings that includes the respective assignment, the respective set is advanced, and is not advanced otherwise;
- and
- (H) deeming a vertex in the observed graph H to be uniquely assigned to a vertex in the original graph G when the set for the respective vertex includes a single unique assignment upon completion of the determining (G).