Download the full-sized PDF of More Reliable Protein NMR Peak Assignment via Improved 2-Interval SchedulingDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Computing Science, Department of


This file is in the following collections:

Technical Reports (Computing Science)

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


Author or creator
Chen, Zhi-Zhong
Jiang, Tao
Lin, Guohui
Rizzi, Romeo
Wen, Jianjun
Xu, Dong
Xu, Ying
Additional contributors
Protein NMR peak assignment
Structural genomics
Interval scheduling
Constrained bipartite matching
Approximation algorithm
Computational biology
Type of item
Computing Science Technical Report
Computing science technical report ID
Technical report TR03-07. 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 NMR peak assignment has been formulated as an interval scheduling problem, where a protein sequence P of amino acids is viewed as a discrete time interval I (the amino acids on P one-to-one correspond to the time units of I), each subset S of spin systems that are known to originate from consecutive amino acids from P is viewed as a \"job\" jS, the preference of assigning S to a subsequence P of consecutive amino acids on P is viewed as the profit of executing job jS in the subinterval of I corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during I. The interval scheduling problem is Max SNP-hard in general; but in the real practice of protein NMR peak assignment, each job jS usually requires at most 10 consecutive time units, and typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. In order to solve these most difficult assignments, we present an efficient 13/7 -approximation algorithm for the special case of the interval scheduling problem where each job takes one or two consecutive time units. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e. jobs that need more than two consecutive time units), we obtain a new efficient heuristic for protein NMR peak assignment. Our experimental study shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the recent literature. The above algorithm is also the first approximation algorithm for a nontrivial case of the well-known interval scheduling problem that breaks the ratio 2 barrier.
Date created
License information
Creative Commons Attribution 3.0 Unported

Citation for previous publication

Link to related item

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 332960
Last modified: 2015:10:12 17:06:34-06:00
Filename: TR03-07.pdf
Original checksum: 4cb85d795fff771a165d0aa93dfdb2a3
Well formed: true
Valid: true
Page count: 18
Activity of users you follow
User Activity Date