More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling

Protein NMR peak assignment refers to the process of assigning a group of “spin systems” obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination. Recently, protein backbone NMR peak assignment has been formulated as an interval scheduling problem, where a protein sequence of amino acids is viewed as a discrete time interval (the amino acids on one-to-one correspond to the time units of ), each subset S of spin systems that are known to originate from consecutive amino acids of is viewed as a “job” j S , the preference of assigning S to a subsequence P of consecutive amino acids on is viewed as the profit of executing job j S in the subinterval of corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during . The interval scheduling problem is Max SNP-hard in general. Typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. To solve these most difficult assignments, we present an efficient 7/13-approximation algorithm. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e. jobs that need more than two consecutive time units), we obtained a new efficient heuristic for protein NMR peak assignment. Our study using experimental data shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the literature. The 7/13-approximation algorithm is also the first approximation algorithm for a nontrivial case of the classical (weighted) interval scheduling problem that breaks the ratio 2 barrier.