Related Experiment Video
Updated: Aug 14, 2026

Atomic Scale Structural Studies of Macromolecular Assemblies by Solid-state Nuclear Magnetic Resonance Spectroscopy
Published on: September 17, 2017
Heuristic search in constrained bipartite matching with applications to protein NMR backbone resonance assignment
Guohui Lin1, Theodore Tegos, Zhi-Zhong Chen
1Bioinformatics Research Group, Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada. ghlin@cs.ualberta.ca
Abstract:
The constrained bipartite matching (CBM) problem is a variant of the classical bipartite matching problem that has been well studied in the Combinatorial Optimization community. The input to CBM is an edge-weighted complete bipartite graph in which there are a same number of vertices on both sides and vertices on one side are sequentially ordered while vertices on the other side are partitioned and connected into disjoint directed paths. In a feasible matching, a path must be mapped to consecutive vertices on the other side. The optimization goal is to find a maximum or a minimum weight perfect matching. Such an optimization problem has its applications to scheduling and protein Nuclear Magnetic Resonance peak assignment. It has been shown to be NP-hard and MAX SNP-hard if the perfectness requirement is dropped. In this paper, more results on the inapproximability are presented and IDA*, a memory efficient variant of the well known A* search algorithm, is utilized to solve the problem. Accordingly, search heuristics and a set of heuristic evaluation functions are developed to assist the search, whose effectiveness is demonstrated by a simulation study using real protein NMR backbone resonance assignment instances.
Related Concept Videos
¹H NMR of Conformationally Flexible Molecules: Temporal Resolution
2D NMR: Heteronuclear Single-Quantum Correlation Spectroscopy (HSQC)
¹H NMR Chemical Shift Equivalence: Homotopic and Heterotopic Protons
2D NMR: Overview of Heteronuclear Correlation Techniques
¹H NMR of Conformationally Flexible Molecules: Variable-Temperature NMR
2D NMR: Overview of Homonuclear Correlation Techniques
COSY90 is the standard two-dimensional (2D) COSY experiment that...
