More reliable protein NMR peak assignment via improved 2-interval scheduling

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.

Automated structure determination from NMR spectra

Automated methods for protein structure determination by NMR have increasingly gained acceptance and are now widely used for the automated assignment of distance restraints and the calculation of three-dimensional structures. This review gives an overview of the techniques for automated protein structure analysis by NMR, including both NOE-based approaches and methods relying on other experimental data such as residual dipolar couplings and chemical shifts, and presents the FLYA algorithm for the fully automated NMR structure determination of proteins that is suitable to substitute all manual spectra analysis and thus overcomes a major efficiency limitation of the NMR method for protein structure determination.