Heuristic search in constrained bipartite matching with applications to protein NMR backbone resonance assignment.
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.
Lin
Guohui
G
Bioinformatics Research Group, Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada. ghlin@cs.ualberta.ca
Tegos
Theodore
T
Chen
Zhi-Zhong
ZZ
D000465:Algorithms; D003198:Computer Simulation; D030562:Databases, Protein; D009682:Magnetic Resonance Spectroscopy / Q000379:methods*; D008956:Models, Chemical; D008958:Models, Molecular; D011487:Protein Conformation; D011506:Proteins / Q000032:analysis* / Q000737:chemistry*
D011506:Proteins