数理解析研究所講究録 1325 巻 2003 年 175-180

175

More Reliable Protein NMR Peak Assignment via Improved
2-Interval Scheduling
Jianjun Wen \P

Romeo Rizzi \SGuohui Lin \dager
Tao Jiang \dag er
Ying Xu **Dong Xu ||Zhi-Zhong Chen *Abatraoet“
Protein NMR peak assignment refers to the process of assigning agroup of spi11systems” obtained
experimentally to aprotein sequence of mli1lo acids. The automation of this process is spin an unsolved andhasproblem ill NMR protein structure determination. Recently, Protein NMR peakinterval Scheduling problem, where a prote sequence $P$ ofacids is viewed as
bae1l formulated as
subsetto tlle 1le units of ),i1lter\Jal I(tlle aJnino acids on
adiscrete
acids bo1n $P$ is viewed ffi a“job” $js$ ,late ffonl consecutive
systems that are lulow1l toofthe profit
of consecutive a11li1lo acids on is viewed
preference of assigning to atlle subinterval of I corresponding to , md the goal is to maximize the total profit
job $js$of) during I. The interval Scheduling problem isjok (on a lgle
SNPthirdof executat ostreal practice of Protein NMR Peak assign ment each job is usuallyin general; but injobs that require o1le or two consecutive me units are tlle
10 consecutive ti11le nits, fiJld typically. In order to solve these most difficult assignments, we present an fflcient
most difficult tojob
IlatioIl algoritIlIIl for tlle special case of the interval Scheduling problem
one or two consecutive time units. Combining this algorithm with a greedy filtering strategy for handlingnew fficient heuristic
more than two consecutive time units), we obtai
long jobs ( $i.e$ . jobs that
produc th6 baet
for Protein NMR peak assignment Our eperi1nental study shows that tlle newpeak assign ment in 11lost of the cas compared with the NMR peak assig1l11lent algorithms in the recent
literature. The above algorithm i\S also the first approximation algorithm for nontrivial case of theratio 2barrier.
(weighted) ltervd scheduling problem, that real$\mathrm{a}\epsilon \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{I}\mathrm{u}\mathrm{n}\mathrm{e}\mathrm{n}\mathrm{t}$$\mathrm{c}\mathrm{h}\epsilon \mathrm{U}\mathrm{e}\mathrm{l}\mathrm{l}\dot{9}\mathrm{n}\mathrm{g}$$\theta \mathrm{I}\mathrm{I}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{o}$$\dot{\mathrm{u}}1$$\mathrm{a}\mathrm{I}1$$\mathrm{I}$$\mathrm{t}\dot{\mathrm{u}}$$\mathrm{e}\mathrm{a}\mathcal{L}\mathrm{h}$$P\mathrm{o}\mathrm{I}\mathrm{l}\triangleright \mathrm{t}\mathrm{o}\mathrm{e}\mathrm{o}\mathrm{n}\mathrm{e}\infty \mathrm{r}\mathrm{r}\mathrm{a}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{d}$$\mathrm{t}\mathrm{i}\prime \mathrm{I}\mathrm{l}\mathrm{e}$$S$$\mathrm{a}\mathrm{m}\dot{\mathrm{u}}10$$0\dot{\mathrm{n}}\mathrm{g}\dot{\mathrm{u}}$$\mathrm{s}\mathrm{p}\dot{\mathrm{u}}1$$S$$\mathrm{t}\mathrm{I}_{1}\mathrm{e}$$P$$\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\Re \mathrm{u}\mathrm{e}\mathrm{I}\mathrm{l}\mathrm{o}\mathrm{e}P$$\mathrm{a}\epsilon$$P$$\mathrm{i}\mathrm{I}1$$\mathrm{e}\mathrm{x}\mathrm{e}\mathrm{m}\mathrm{t}\overline{\mathrm{l}}\mathrm{I}\mathrm{g}$$\mathrm{M}\mathrm{a}\mathrm{J}\kappa$$\mathrm{t}\mathrm{I}_{1}\mathrm{e}$$\mathrm{s}\dot{\mathrm{u}}$$\mathrm{I}\mathrm{I}\mathrm{l}\mathrm{a}\mathrm{d}\dot{\mathrm{u}}\mathrm{I}\mathrm{l}\mathrm{e}$$\dot{\mathrm{u}}\mathrm{g}$$\mathrm{r}\alpha \mathrm{l}\mathrm{u}\mathrm{i}\mathrm{r}\mathrm{a}\mathrm{e}$$\mathrm{t}\mathrm{I}_{1}\mathrm{e}$$\mathrm{m}$$\mathrm{t}\mathrm{i}$$\mathrm{t}1_{1}\mathrm{e}$$\mathrm{u}$$\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}/\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{l}\mathrm{e}$$\mathrm{w}\mathrm{I}_{1}\mathrm{e}\mathrm{o}\mathrm{e}\mathrm{e}\mathrm{a}\mathrm{d}_{1}$$\mathrm{t}\mathrm{h}\mathrm{e}$$\frac{\iota\tau}{7}.- \mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}\dot{\mathrm{u}}$$\cdot$$\mathrm{n}\mathrm{e}\alpha 1$$\mathrm{a}$$\mathrm{h}\mathrm{e}\mathrm{u}\mathrm{i}8\mathrm{t}\mathrm{i}\mathrm{c}$$\mathrm{e}$$\mathrm{e}$$\mathrm{c}\mathrm{l}\mathrm{a}\epsilon 8\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{l}$$\mathrm{a}$$\mathrm{t}1_{1}\mathrm{e}$$\dot{\mathrm{u}}$1Introduction

Due to the efforts of structural genomics [8], the NMR (nuclear magnetic resonance) technique has been used
as ahigh-throughput technology to solve protein structures at agenome scale. Typically, protein structure
determination via NMR involves the following steps:@NMR spectral data generation, which produces-resonance peaks corresponding to amino acids in the target protein sequence. Peaks corresponding
to acommon amino acid are grouped into aspin system;-certain geometric relationships ( $e.g$ . distances and angles) between the spin systems;
Peak picking, which identifies “real” resonance peaks (peaks generated ffom protein atoms rather thannoise) from NMR spectral maps.
Peak assignment, which assigns resonance peaks, typically peak groups, to individual residues of the target
Protein sequence.
Structural restraint extraction, which extracts inter-residue distances, dihedral angles, etc., based on thepeak assignment.
Structure calculation, which calculates the protein structure, using molecular simulation and energy minimization, under the identified NMR restraints.
Among the five steps, the third one (namely, NMR peak assignment) is very time consuming. The process usuallytakes weeks or sometimes even months of manual work in order to produce anearly complete assignment. The
automation of the assignment process is still an unsolved and challenging problem in NMR protein struc rure

.
.
.
.

determination.
Two key pieces of information form the foundation of NMR peak assignment:-0394, Japan. Part of work done while*Department of Mathematical Sciences, Thkyo Denki University, Hatoyama, Saitama.
visiting at University of Alberta. Email: chen\copyright r\dagger Department of Cbmpute Science, University of California, Riverside, CA 92521, and Shanghai Center for Bioinformation
Taehnoloy. Email: jiang\copyright c$.ucr.edu.
.
, Canada. Email:\ddagger Department of Computing Science, University of Alberta, Edmonton, Alberta
SDipartimento di Informatica Telecomunicazioni, University di TYento, Italy
Department of Computer Science, University of California, Riverside, CA 92521. Email: wjia1lju\copyright cs.ucr.edu.
IIProtein Informatics GrouP, Life Sciences Division, Oak Ridge National Laboratory, Oak Ridge, TN 37831-6480, USA. Email:{?}{?}d@ornl .gov.
and Computer Sciences and Mathematics Division, Oak Ridge National
Informatica Group, Life Sciences
Laboratory. Oak Ridge, TN 37831-6480, USA. Email: xyr@orn.gov.
$3\mathfrak{N}$$.\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{a}\mathrm{i}.*\mathrm{c}.\mathrm{j}\mathrm{p}$$\mathrm{T}6\mathrm{G}2\mathrm{E}8$$\mathrm{E}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{l}:\prime \mathrm{o}\mathrm{m}\mathrm{e}\mathrm{o}\mathrm{O}\mathrm{s}\mathrm{c}\dot{|}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}.\mathrm{u}\mathrm{n}\dot{|}\mathrm{t}n.\dot{|}\mathrm{t}$$\mathrm{e}$$\tau$$\mathrm{n}*\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{i}\mathrm{n}$$\mathrm{D}\mathrm{i}\mathrm{v}\mathrm{i}_{8}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{p}\mathrm{h}1_{\dot{1}}\mathrm{n}\mathrm{Q}\mathrm{c}\mathrm{s}.\mathrm{u}\mathrm{a}1\mathrm{b}\mathrm{e}\hslash \mathrm{a}.\epsilon*$

176

.
.

The likelihood (or weight) of the matching between aspin system and an amino acid on the protein
sequence.
The sequential adjacency ( $i.e.$ , consecutivity) information of some subsets of spin systems ( $i.e.$ , each such
subset of spin systems should correspond to asubsequence of consecutive amino acids on the host protein
sequence). Each maximal such subset is called asegment of spin systems. It is worth noting that eachsegment usually consists of at most 10 spin systems.

In arecently developed computational framework [10], the NMR peak assignment problem has been formulated
as a(weighted) interval scheduling problem1 as follows. Aprotein sequence of amino acids is viewed as adiscrete time interval I(the amino acids on one t0-0ne correspond to the time units of $I$). Each segmentconsecutive time units of I(this corresponds toof spin systems is viewed as ajob js- Each job $js$ requires
consecutive amino acids on ). For eachthe requirement that the spin systems in should be assigned totime unit , of , the profit $w(js, t)$ of starting job $js$ at time unit and finishing at time unit $t+|S|-1$ of I
consecutive amino acids on that
corresponds to the preference of assigning the spin systems in to those, $t+|S|-1$ . Given , the jobs $js$ , and the profits $w(js, t)$ , our goal iscorrespond to the time units , $t+1$ ,to maximize the total profit of the executed jobs ( $i.e$ . we want to find a maximum-likelihood assignment of thegiven spin systems to the amino acids on ).
SNP-hard $[3, 4]$ . Indeed, for every integer $k\geq 2$ ,Unfortunately, the interval scheduling problem isthe special case of the interval scheduling problem (called the interval scheduling problem or k-ISP for short)
SNP-hard. On the other hand, several 2
where each job requires at most consecutive time units isapproximation algorithms for the interval scheduling problem are known [2, 1, 3, 4]. Although these algorithms
are theoretically sound, aPPlying them to protein NMR Peak assignment produces unsatisfactory assignments
as demonstrated in [3]. Amajor reason why these algorithms do not have good performance in protein NMR
$P$

$S$

$P$

$|S|$

$S$

$f$

$P$

$|S|$
$t$

$\mathcal{T}$

$S$

$t,$

$P$

$|S|$

$\mathrm{X}$$\ldots$$P$${\rm Max}$$k$${\rm Max}$$k$.

peak assignment is that they ignore the following important observation:

In the real practice of protein NMR peak assignment, long segments of spin systems are typically easier
to assign than shorter segments. In fact, many long segments have unique matches. On the other hand,segments consisting of one or two spin systems are often very difficult to assign.
$S$

The above observation suggests the following heuristic framework for protein NMR peak assignment: first try toassign segments consisting of at least $k+1$ spin systems for some small integer (say, $k=2$ ), and then solve an
instance of -ISP. In [7], we have presented such aheuristic and have shown that it is very effective for protein
NMR peak assignment. Amajor drawback of the heuristic in [7] that it lEes an inefficient branch-and-boundalgorithm for fc-ISP.
In order to improve the efficiency of the heuristic in [7], we present anew approximation algorithm for 2-ISP
and is the first approximation algorithm
in this paper. This algorithm achieves an approximation ratio of
Our algorithm
for anontrivial case of the classical interval scheduling problem that breaks the ratio 2
is combinatorial and quite nontrivial –it consists of four separate algorithms and outputs the best solution
returned by them. The main tool used in the algorithm design is maximum-weight bipartite matching andcareful manipulation of the input instance. Since the algorithm is combinatorial, it is easy to implement andruns very fast in practice. Substituting the new algorithm for the branch-and-bound algorithm in the heuristic
We have performed extensive experiments
in [7], we obtain anew heuristic for protein NMR peakon 70 instances of (pseudo) real NMR data derived from 14 proteins to evaluate the performance of our new
heuristic in terms of (i) the weight of the assignment and (ii) the number of correctly assigned resonance peaks.
The experimental results show that not only does the new heuristic run very fast, it also produces the best
peak assignment on most of the instances, compared with the protein NMR peak assignment algorithms in the
recent literature [3, 4, 7, 10].
$k$

$k$

$\mathrm{i}B$$13\overline{\overline{7}}$$\mathrm{b}\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{e}\mathrm{r}.2$$\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}.3$

2Anew approximation algorithm for 2-ISP. Let
Let Ibe the given discrete time interval. Without loss of generality, we may assume that$\{v_{1,2}v, \ldots,v_{n_{1}}\}$ be the given set of jobs requiring one time unit of Z. Let
be the given set of jobs requiring two contiguous time units of I. Note that $n_{1}+n_{2}$ is the total number ofdenote the time unit $[i-1,i]$ of I. Let $U=\{u_{\dot{1}}|1\leq i\leq I\}$ . Let
given jobs. For each $1\leq i\leq I$ , let$J_{2}’=\{v_{n_{1}+2}, v_{n_{1}+4}, \ldots, v_{n_{1}+2’\iota_{2}}\}$ .
edge weighted bipartite graph $G$
Let $V=J_{1}\cup J_{2}\cup \mathrm{J}${. We construct$U$such that the profit of executing job
and $V$ as follows: For every
and every
with color$\mathrm{I}=[0, I]$$I_{1}$$=$$12=\{v_{\mathfrak{n}_{1}+1},v_{n_{1}+3}, \ldots, v_{n_{1}+2n\mathrm{a}-1}\}$$u_{\dot{*}}$$\mathrm{m}$$Vj$$\mathrm{c}1\mathrm{a}_{*}\mathrm{s}\mathrm{s}\mathrm{a}\mathrm{e}$$\in J_{1}$$\tau_{\dot{l}}\in U$,$v_{j})J_{2}$are edges of and the weight of each of them is half the profit.
$\in M$and every $vj\in I2$ ,Aconstrained matching of is amatching of such that for every. The objective of 2-ISP is equivalent to finding a maximum-weight constrained
if and only if
and$(n\dot{\mathrm{r}}+1,vj\dagger 1)$

$G$

$G$

$\mathrm{A}f$$G$$u_{\dot{*}}\in U$$(\tau h.,vj)$$(u_{\dot{|}+}1,v\mathrm{j}+1)\in M$’

let $w(M)=w_{1}(M)+w_{2}(M)$ .
1In [10] it was called the $conlt1u\dot{|}ned$ bipartite matching Problem.
unweighted ISP where the profit of executing ajob at each specific time interval is either 0or 1(indePendent of the job’s
paper, our interest is in the weighted problem.
,$2\mathrm{F}\mathrm{o}\mathrm{r}$$1\mathrm{e}\mathrm{n}_{5_{\mathrm{T}\mathrm{h}\mathrm{e}}^{\mathrm{t}\mathrm{h})}}$$\mathrm{C}\mathrm{h}\mathrm{u}\mathrm{z}\mathrm{h}\mathrm{o}\mathrm{y}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}$$\mathrm{e}\mathrm{t}\mathrm{a}\mathrm{l}.[5]\mathrm{g}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{a}\mathrm{l}.58\lambda \mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}.\ln \mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{p}\mathrm{u}\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{u}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}8\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{u}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{r}$177
be amaximum-weight constrained matching in G. In Sections 2.1, 2.3 through 2.5, we wiU designLetfour algorithms each outputting aconstrained matching in G. The algorithm in Section 2.5 is the main algorithm
and is quite sophisticated. We wiI try to find a large constant such that the heaviest one among the four
. So, fix
for the. It will turn ollt that
output matchings is of weight at least
discussions in the rest of this section.
$M^{*}$$\epsilon$

2.1$\epsilon=\frac{1}{26}$$\epsilon=\frac{1}{26}$$( \frac{1}{2}+\epsilon)w(M^{*})$

Algorithm 1(At’) is relatively large comparedThis algorithm will output aconstrained matching of large weight when
we partition the time interval I
Supposethat
algorithm.
idea
behindtheexplain
the
first
.
We
with
into shorter intervals, called basic inter vals, in such away that each basic interval, except possibly the first andconsist of 1or 2time units), consists of 3time units. There are exactly three suchthe last (which may
with $0\leq h\leq 2$ , consider, and P2, respectively. With respect to eachpartitions of I. Denote them by Pq,
the problem Qh of finding a constrained scheduling which maximizes the total profit of the executed jobs, but
can be assigned to at most one job and each executed
subject to the constraint that each basic interval in. It is not so hard to see that each problem Qh
job should be completed within asingle basic interval inrequires the computation of amaximum-weight (unconstrained) matching in asuitably constructed bipartite
graph, and hence can be solved in polynomial time.
, the bffi one gives ascheduling by which the executed jobs
We claim that among the three problems. This claim is actually easier to see, if we refer to amore
achieve at least atotal profit ofthan Qh by adding the following constraint:
constrained scheduling problem$w_{2}$$w_{1}(M^{\mathrm{r}})$$\mathrm{p}\mathrm{o}\mathrm{s}_{\iota}\mathrm{s}\mathrm{i}\mathrm{b}1\mathrm{y}$$P_{h}$$P_{1}$$P_{h}$$P_{h}$$Q_{h}$.

$\frac{1}{3}w_{1}(M^{\mathrm{r}})+\frac{2}{3}w_{2}(\mathrm{A}\mathrm{t}’)$$Q_{h}’$

and for each basic interval b in , only the primary timeFor each job
to vj’ where the primary time unit of b, is u:if b consists of three time units
if b consists of the last two time unitsof the first two time units uiu2 of , isb consists of one time unit only.

$\iota \mathrm{m}\mathrm{i}\mathrm{t}$$P_{h}$$v_{j}\in J_{1}$of b can be assigned
if b consistsof I, is b itself if$u\dot{*}-1uiu_{\dot{1}}+1,\dot{\mathrm{L}}\mathrm{s}u1$$\mathcal{T}$$u_{I}$

exactly two indices h$\in${0,1, 2} such that some basic interval in$P_{h}$$u_{I-1}u_{I}$contains both time units$u:u_{\dot{|}+1}$. Similarly,, the three problems. Thus, by inheriting from the optimal scheduling
unit of some basic interval in
is athe threesuch thathave more constrained schedulings
more-constrained scheduling
altogether achieve at least a total profit of $w_{1}(M^{\mathrm{r}})+2w_{2}(M^{*})$ . Hence, the’). Indeed, we can prove the, and,achieves at least atotal profit ofamong$Q_{h}’$$M^{\mathrm{r}}$$P_{h}$$M_{h}^{*}$$\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}_{11}1\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}$$M_{h}^{l}$$\Lambda f_{h}^{\mathrm{s}}$$\mathrm{b}\mathrm{e}_{\iota}\mathrm{s}\mathrm{t}$$M_{1}^{l}$$M_{2}^{l}$$\frac{1}{3}w_{1}(M^{*})+\frac{2}{3}w_{2}(M$$M_{3}^{\mathrm{r}}$following better bound which is needed in later sections:
The

, and
achieves a total profit of at least
more-constrained scheduling among hfi,
assigns no job in Jl, where $p_{1}=0$ (respectively, $p_{I}=0$ ) if
incident to(respectively, ) equals the weight of the edge of), while(respectively,$M_{2}^{*}$$\mathrm{b}\alpha \mathrm{t}$$M_{3}^{l}$$M^{\mathrm{r}}$$\frac{1}{3}w_{1}(M^{\mathrm{r}})+\frac{2}{3}w_{2}(M^{\mathrm{r}})+\frac{1}{3}(p_{1}+p_{I})$to$u_{1}$$M^{\cdot}$$u_{1}$$u_{I}$(respectively,$1k_{I}$$p_{I}$$p_{1}$) otherwise.

is
To see why we have this better bound, first note that there are exactly two indices h {0,1,2} such that. Similarly, there are exactly two indices h {0,1. 2} such thatthe primary time unit of abasic interval inbound follows.
ur is the primary time unit of abasic interval in . By these two facts, the betterlead
to better experimental
may often
As it should be expected, the constrained scheduling problems. However, as for general theoretical results, we don’t
results than the more-constrained scheduling problems
can be solved more efficiently
know if there is adifference between the two types of problems. Moreover,. Hence, for simplicity, in the following exposition we wiU consider only the more-constrained scheduling
than
$\in$

$u_{1}$$\in$$P_{h}$$P_{h}$$Q_{h}$$Q_{h}’$$Q_{h}’$$Q_{h}$

problems.
requires the computation of a
It is not hard to see that each more-constrained scheduling problem, and hence can be
maximum-weight (unconstrained) matching in asuitably constructed bipartite graphsolved in polynomial time.
$Q_{h}’$$Q_{h}’$$G_{h}$

in can be found in $O(I(n_{1}+n_{2})\sqrt{I+n_{1}+n\mathrm{z}})$ time, whose weight
Lemma 2.1 A $r,onstmine,d$ matchingnot, where $p_{1}=0(re.9pextive,ly, p_{I}=0)$ if
at leastthe,to$equaL_{9}$incidentedge,$M$weight)(respectively,
’,
by
while
of
to
of
matched a better ofthe$G$$Z_{1}$$u_{1}(re.s\mathrm{p}e,ct\dot{\iota}vely, ul)i9$$\frac{1}{3}w_{1}(M^{\mathrm{r}})+2_{w}32(M^{*})+\frac{1}{3}(p_{1}+p_{I})$$\dot{\mathrm{A}}9$$M^{\mathrm{t}}$$J_{1}$(re.qpedively,$u_{I}$$u_{1}$$p_{I}$) otherwise.

Corollary 2.2 If $w_{1}(M’)$

2.2

$P1$

$\leq(\frac{1}{2}-3\epsilon)w(M$’$)$, then$w(Z_{1})\geq(_{2}^{\pm}+\epsilon)w(M^{\iota})$.

.

Preparing for the other three algorithms

Before running the other three algorithms, we need to compute a marimum-weight unconstrained matching
will be an additional input to the other three algorithms. Therefore,of . The unconstrained matchingof .
algorithms,
fix amaximum-weight unconstrained matching
before proceeding to the details of thetoin asophisticated way. But first, we use
The algorithms in Sections 2.3 through 2.5 will use
follows.
ofasdefine several subsets$M_{\mathrm{u}\mathrm{n}}$$G$$M_{\mathrm{u}\mathrm{n}}^{\mathrm{r}}$$M_{\mathrm{u}\mathrm{n}}^{\mathrm{r}}$$G$$M_{\mathrm{r}}^{*}$$M_{\mathrm{u}\mathrm{n}}^{\mathrm{r}}$

$U$

178

.
..

}

)

$\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}\mathrm{l}$$\cdot$$\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}\mathrm{t}o\mathrm{a}vj\in J_{1}\mathrm{b}\mathrm{y}\mathrm{y}\lambda f_{\mathrm{u}\mathrm{n}}^{*}$$U_{1}^{0}=\mathrm{f}_{u_{i}}^{u_{i}}U=\in U\in U|\mathit{1}\mathrm{A}_{t}\mathrm{i}\mathrm{s}u_{i}\mathrm{i}\mathrm{s}$$\Lambda,f_{\mathrm{u}\mathrm{n}}^{*}$}.

$..U_{2,2}=\mathrm{f}_{\{\mathrm{z}_{\dot{|}}\in}^{1\mathit{1}_{i}\in}U_{2,1}=UU|\tau\iota_{i}\mathrm{i}\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}\mathrm{t}\mathrm{o}\mathrm{a}v_{j}\tau\iota_{\dot{l}}\mathrm{i}\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}\mathrm{t}\mathrm{o}\mathrm{a}v_{j}\in J_{2}’\mathrm{b}\mathrm{y}M_{\mathrm{u}\mathrm{n}}^{*:}\in J2\mathrm{b}\mathrm{y}\Lambda\prime f_{\mathrm{u}\mathrm{n}}^{*}.\cdot$

$W=$

{

and $u_{i+1}\in U_{2,2}$ }.
and $W_{R}=$ { $u_{i}\in U|$ wil $1\in W$ }.

$\tau\iota_{i}\in U_{1}|u_{i-1}\in U_{21}$$W_{L}=\{\tau\iota_{i}\in U|14_{\dot{|}+1}\in W\}$

In general, whenever $u_{i}\in W$ , we have $u_{i-1}\in W_{L}$ and $u_{i+1}\in W_{R}$ . Moreover, since
can intersect.
among $W$ ,and
and
Acommon idea behind the forthcoming algorithms is to divide the weights
parts, based on the aforementioned subsets of . Define the smaller parts as follows.

$W\subseteq U_{1}$$w_{1}(M^{\mathrm{r}})$..
..

$w_{2}(M^{\mathrm{r}})$into smaller$U$$\cdot$.

, no two sets

$W_{R}$$W_{L}$$\beta^{L}\mathrm{i}_{\mathrm{S}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{t}\circ \mathrm{t}\mathrm{a}1\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{a}11\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}(\mathfrak{R},v_{j}}\beta \mathrm{i}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}1\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{a}11\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}_{\mathrm{f}\in M^{\mathrm{r}}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}u_{\dot{*}}\in W\mathrm{a}\mathrm{n}\mathrm{d}v_{j}\in J_{1}}(u_{\dot{l}},v)\in M^{\mathrm{s}}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}u_{\dot{l}}\in W_{L}\mathrm{m}\mathrm{d}v_{j}\in.J_{1}$$\beta_{R}$is the total weight of all edges $(u:,vj)\in M^{\mathrm{r}}$ such that $u:\in W_{R}$ and $vj\in J_{1}$.

.
.

$\overline{\beta}=w_{1}(M^{\mathrm{r}})-\beta_{L}-\beta-\beta_{R}$is the total weight of all edges $(u:,vj)\in M^{*}$ such that either $vj\in J2$ and {us,.
orandsuch that either $vj\in J2$ andis the total weight of all edges$W_{L}\cup W\cup W_{R}$ , orand $\{u:-1,u:\}\subseteq W_{L}\cup W\cup W_{R}$ .
$\alpha_{0}$$u_{\dot{*}+1}$}$\cap W=\emptyset$,$\{u_{\dot{*}-1},uj\}\cap W=\emptyset$$v_{j}\in J_{2}’$$\{u_{\dot{l}}, u:+1\}\subseteq$$(u_{\dot{1}}, v_{j})\in M^{\mathrm{t}}$$\alpha_{1}$$v_{j}\in J_{2}’$Lemma 2.3$\alpha_{0}+\alpha_{1}=w_{2}(M^{\mathrm{r}})$and$\beta_{L}+\beta+\beta_{R}+\overline{\beta}=w_{1}$(Af’).

Now, we are ready to explain how the four algorithms are related. The algorithm in Section 2.3, called. The algorithm
Algorithm 2, will output aconstrained matching of weight at least. Thus, if
at
least
weightofmatching
3,ain Section 2.4, called Algorithm will olltpllt constrained’then Algorithm 2or 3will output a constrained matching of weight at least, then Algorithm 1or 4will output a(see CoroUary 2.6 below). On the other hand, if(see Section 2.6).
constrained matching of weight at least$\frac{1}{3}\overline{\beta}+\frac{2}{3}\alpha_{0}+\beta+\frac{2}{3}(\beta_{L}+\beta_{R})$$\beta+\overline{\beta}+\alpha_{1}$$( \frac{1}{2}+\epsilon)w(M^{*})$$\beta\geq(\frac{1}{6}+\S_{\epsilon)w(M^{\mathrm{r}})}3$$\beta<(\frac{1}{r}, +\frac{5}{3}\epsilon)w(M^{*})$$( \frac{1}{2}+\epsilon)w(M^{*})$

2.3

Algorithm 2

We first explain the idea behind the algorithm. The removal of the vertices in $W$ leaves $|W|+1$ blocks ofeach of which consists of consecutive vertices of . For each block 6, we use the idea of Algorithm 1to construct, Gb, ,. For each $h\in\{0,1, 2\}$ , we consider the graph $UbGb,h$ where ranges over all blocks,
three graphs
by adding the vertices of $W$ and the edges $\{u:, vf\}$ of such thatand obtain anew graph$u:\in W$ and. We then compute a maximum-weight (unconstrained) matching in each , and furtherof as in Algorithm 1. The output of Algorithm 2is the heaviest
convert it to aconstrained matching.
matching among

$U$

$U$

$G_{b_{\mathrm{I}}0}$

$0$

$b$

$G_{b,2}$$G$$G_{h}’\mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}\cup bG_{b,h}$$G_{h}’$$v_{j}\in J_{1}$$G$$\overline{M}_{h}’$$\overline{M}_{0}’,\overline{M}_{1}’,\overline{M}_{2}’$Lemma 2.4 A constrained matching.
is at least$Z_{2}$

in$G$

can be found in$0(1(\mathrm{n}\mathrm{i}+n_{2})\sqrt{I+n_{1}+n_{2}})$

time, whose weight$\frac{1}{3}\overline{\beta}+\frac{2}{3}\alpha_{0}+\beta+\frac{2}{3}(\beta_{L}+\beta R)$

2.4

Algorithm 3

We ffist explain the idea behind Algorithm 3. Suppose that we partition the time interval Iinto shorter intervals
wherein such away that each shorter interval consists of either one time unit or three time units. There is only one such partition of Z. Further suppose that we want to execute at most one job in eachof the shorter intervals, while maximizing the total profit of the executed jobs. This problem can be solved in$r\iota_{t-1}u_{*}.u_{1+1}$$\tau\nu_{\dot{\mathrm{r}}}\in W$

polynomial time by computing amaximum-weight (unconstrained) matching in asuitably constructed bipartite
graph. We can proye that this matching results in ascheduling by which the executed jobs achieve at least a

total profit of$\beta+\overline{\beta}+\alpha_{1}$.

Lemma 2.5 A constrained matching Z$ in.
’at least$G$

can be found in $O(I(n_{1}+n_{2})\sqrt{I+n_{1}+n_{2}})$ time, whose weight$\beta+\overline{\beta}+\alpha_{1}$$\dot{\mathrm{a}}$Corollary 2.6 If

2.5$\beta\geq(\frac{1}{6}+\frac{6}{3}\epsilon)w(M^{*})$, then $\max\{w(Z_{2}),w(Z.\mathrm{q})\}\geq(\frac{1}{2}+\epsilon)w(M$ ’ .
$)$Algorithm 4, we partition
to aconstrained matching of . To convert
The idea behind Algorithm 4is to convert
and $u:+1$ such that) into two subsets none of which contains two vertices(respectively,
incident to the vertices of each such subset can be). The set of edges of(respectively,
extended to aconstrained matching of . In this way, we obtain four constrained matchings of . Algorithm 4
outputs the heaviest one among the four matchings. We can prove that the weight of the output matching is.
at least
asnext proceed to the details of Algorithm 4. Algorithm 4computes aconstrained matching in$G$$M_{\mathrm{u}\mathrm{n}}^{l}$$U_{1}\cup \mathrm{L}/2,1$$U_{1}\cup U_{2,2}$$u_{i}\in \mathrm{L}/2,1$$u_{\dot{l}+1}\in \mathrm{U}2.\mathrm{i}$$M_{\mathrm{u}\mathrm{n}}^{\mathrm{r}}$$u_{\dot{l}}$$M_{\mathrm{u}\mathrm{n}}^{l}$

$G$

$G$

$w(M_{\mathrm{u}}^{\mathrm{r}_{11}})/2$$G$$\mathrm{W}\mathrm{e}-$$P1$ ’

179
1. Starting at$u_{1}$, divide$U$

into segments each of which is in the following form:$u_{i-}\ell u_{i-,+1}\cdots$ $u_{i-1}u_{i}u_{\dot{\tau}+1}\cdots$ $u_{i\dagger r-1}u_{\mathrm{a}\dagger r}$,,,
for all $i+1\leq j\leq i+r$ ,for all $i-\ell,$ $\leq j\leq i-1,$
where$ui$ the $r,mte,r$ of the segment.
may be equal to zero. We
and has no restriction. Note that
denote the number
denote the integer such that is the center of 8; let
For each segment , let.
; letdenote the number of vertices in 8that succeedof vertices in that precede
$l$

$s$

$u_{\dot{\alpha}\dagger r\dagger 1}\not\in \mathrm{U}2\mathrm{f}2$$\mathrm{c}\mathrm{a}\mathrm{u}$$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}r$$i$$\mathrm{c}(\mathrm{s})$$\ell(s)$$u_{\dot{\iota}}$$r(\epsilon)$$\mathrm{s}$$u_{c(s)}$$u_{\mathrm{c}(s)}$

..
..

and
2. For each segment 8, compute two integers
and
If $u_{c(s)}\in U0$ , then.
, thenIf, then $x_{\theta}=c(s)$ andIf, thenandIf

3. Let$u_{i-\ell-1}\not\in \mathrm{U}21$$\uparrow j\in U_{2,2}$$u_{j}\in U_{2,1}$$u_{i}$$x_{s}$$u_{\mathrm{c}(s)}\in U_{1}$$y_{s}$

as follows:$=\mathrm{c}(\mathrm{s})$$x_{\epsilon}=1/S$$y_{\epsilon}=\mathrm{r},(s)+1$$u_{\mathrm{c}(s)}\in \mathrm{U}21$$y_{*}=c(\epsilon)$$x_{\epsilon},=\mathrm{c}(s)-1$$u_{\mathrm{c}(s)}\in \mathrm{U}2\mathrm{f}2$.

$r_{s}/=\mathrm{c}(\mathrm{s})+1$$x_{\theta}=\mathrm{c}(\mathrm{s})-1$

.
.
,
,
,
,

$U_{2,1}^{\mathrm{e}}= \bigcup_{s}\{u_{\dot{1}}|(x_{\epsilon}-i)\mathrm{m}\mathrm{o}\mathrm{d} 2=0, c(\epsilon)-\ell(\epsilon)\leq i\leq x_{\mathfrak{g}},\}$$U_{2.1}^{o}= \bigcup_{\epsilon}\{u:|(x_{s}-i)\mathrm{m}\mathrm{o}\mathrm{d} 2=1, \mathrm{c}(\mathrm{s})-\ell,(\epsilon)\leq i\leq x_{g},\}$$U_{2,2}^{e}= \bigcup_{\epsilon}\{u:|(i-y_{\epsilon})\mathrm{m}\mathrm{o}\mathrm{d} 2=0,\mathrm{y}’\leq i\leq c(\epsilon)+r(s)\}$$U_{2^{\mathrm{O}}.2}= \bigcup_{s}\{u:|(i-y_{\epsilon})\mathrm{m}\mathrm{o}\mathrm{d} 2=1,y_{\epsilon}\leq i\leq \mathrm{c}(\mathrm{s})+r(s)\}$where 8runs over all segments.

4. Let$M_{2,1}^{e}=\{(\mathrm{u}\mathrm{i}.

\mathrm{v}\mathrm{j})\in M_{\mathrm{u}\mathrm{n}}^{*}|u_{i}\in U_{2_{1}1}^{e}\}\cup$

{
Li {
{

{

$(_{1k+1},v_{j+1})|u_{\dot{1}}$$M_{2,2}^{\mathrm{e}}=\{(\mathrm{u}\mathrm{i}.\mathrm{v}\mathrm{j})\in M_{\mathrm{u}\mathrm{n}}^{\iota}|u_{\dot{l}}\in U_{2,2}^{e}\}$$(u_{\dot{|}-1},$ $v_{j-1})|u_{\dot{l}}\in U_{2,2}^{\mathrm{e}}\cap U_{2,2}$$kf_{2,2}^{o}=\{(u_{i}, v_{j})\in \mathrm{A}f_{\mathrm{u}\mathrm{n}}^{\mathrm{r}}|u_{\dot{l}}\in U_{2,2}^{o}\}\cup$Note that for each edge

$N_{2,1}^{o}$$\overline{U}_{2,1}^{o}$$\overline{U}_{2^{\mathrm{o}},2}$that are not matched byand the vertices in .

$U$

$M_{2,1}^{e}$,$M_{2,1}^{\mathrm{o}}\cup N_{2^{\theta},1}$,$M_{2,2}^{\mathrm{e}}$$M_{2,1}^{o}$$M_{2^{0},2}$

and$Z_{4}$

among$M_{2,2}^{\mathrm{o}}\cup N_{2,2}^{o}$$hf_{2,1}^{\epsilon}$,$U_{2.1}^{\mathrm{o}}\subseteq \mathrm{U}21$

and

},

}.

$U_{2.2}^{\mathrm{o}}\subseteq \mathrm{U}2\mathrm{f}2$], compute amaximum-weight matching, compute amaximum-weight matching$hf_{2.1}^{o}\cup N_{2,1}^{o}$,$M_{2.2}^{\mathrm{e}}$,$hf_{2,2}^{o}\cup N_{2,2}^{\mathrm{o}}$are constrained matchings inLemma 2.8$w(M_{2.1}^{\mathrm{e}})+w(M_{2,1}^{\mathrm{o}})+w(\Lambda f_{2,2}^{\epsilon})+w(M_{2.2}^{o})\geq 2w(M_{\mathrm{u}\mathrm{n}}^{*})$

Lemma 2.9$(U-\overline{U}_{2.1}^{o})\cap(U-\overline{U}_{2,2}^{o})\subseteq W$

2.6$\in M_{\mathrm{u}11}’$},$J_{1}$

7. Output the maximum-weight matching
Lemma 2.7

. Indeed,$\{u:,vj\}\in M_{\mathrm{u}\mathrm{n}}^{*}$$\{u_{\dot{l}},vj\}$},$J_{1}$$\overline{U}_{2,2}^{o}$$N_{2,2}^{o}$$vj\not\in J_{1}$that are not matched by.
and the vertices in$U$$\overline{U}_{2,1}^{o}$of vertices of
6. For the set
between the vertices in, we have$\{\tau\mu,vj\}\in M_{\mathrm{m}}^{*}$$\{u_{i},v_{j}\}\in M_{\mathrm{u}\mathrm{n}}^{*}$$\in U_{2,1}^{o}\cap U_{2,1}$$(\mathrm{u}_{-1}.,v_{j-1})|u.\cdot\in U_{2^{O},2}\cap \mathrm{U}2\mathrm{f}2$$(\text{\^{u}} \mathrm{V}\mathrm{j})\in M_{2,1}^{o}\cup M\mathrm{J}\mathrm{f}2$

of vertices ofbetween the vertices in

5. For the set

and
md
and
and

$(u_{\dot{\alpha}+1},v_{j+1})|u_{\dot{\mathrm{a}}}\in U_{2,1}^{\mathrm{e}}\cap \mathrm{U}21$$M_{2,1}^{o}=\{(u:,v_{j})\in M_{\mathrm{u}\mathrm{n}}^{*}|u_{i}\in U_{2.1}^{o}\}\cup$

$G$

.

.

.

.

Performance of the algorithm when$\beta$is small

For acontradiction, assume the following:
Assumption 2.10$\ \mathrm{q}_{\iota}\mathrm{q}$$\beta<(\frac{1}{6}+\S \mathrm{a})w(M$’$)$

and $\max\{w(Z_{1}),w(Z_{4})\}<(\frac{1}{2}+\epsilon)w(M’)$ .

We want to derive acontradiction under this assumption. First, we derive three inequalities from thisumption and the lemmas in Section 2.5.

Lemma 2.11$w(M_{2^{\mathrm{O}},1})+w(M_{2.2}^{o})\geq(1-2\epsilon)w(M^{\mathrm{r}})$.

Lemma 2.12 $w(N_{2.1}^{\mathrm{o}})+w(N_{2,2}^{o})<4\epsilon w(M^{*})$ .
Lemma 2.13 $\beta>w1(M^{\mathrm{r}})-4\epsilon w(M$’ .
$)$Now, we are ready to get acontradiction. By Corollary 2.2 and Assumption 2.10,
On the other hand, by Aasumption 2.10,
Thus, by Lemma 2.13,. Therefore,, contradicting our choice that$\beta>(\frac{1}{2}-7\epsilon)w(M^{\mathrm{s}})$.

(Af’) $>( \frac{1}{2}-3\epsilon)w(M^{*})$ .
. Hence,$\epsilon=\frac{1}{26}$$\frac{1}{2}-7\epsilon<\frac{1}{6}+\frac{6}{3}\epsilon$

Theorem 2.14 A constrained matching$w_{1}$$\beta<(\frac{1}{6}+\frac{6}{3})w(M^{\mathrm{r}})$

$Z$

in

$G$

with $w(Z) \geq\frac{13}{7}w(M^{*})$ can be found in $O(I(n_{1}+n_{2})\sqrt{I+n_{1}+n_{\mathrm{i}}}$18032-ISP with aspecial profit function
In this section, we consider proportional 2-ISP, where the profit of executing a job at each specific time interval
is either 0or proportional to the length of the job. A -approximation algorithm was recently presented in [4]. We note in-approximation algorithm for it for any
for proportional 2-ISP. Here, we present a-approximation algorithm for unweighted
passing that asimple modification of this algorithm leads to a 1.5$\frac{5}{3}$$\epsilon>0$$(1.5 +\epsilon)$$($$\epsilon)$

2-ISP.

$\mathrm{i}\mathrm{n}\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}2.\mathrm{L}\mathrm{e}\mathrm{t}E\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{s}\mathrm{e}\tau\iota_{\dot{l}}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}.\mathrm{L}\mathrm{e}\mathrm{t}\mathrm{t}F\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{s}\mathrm{e}\{u_{\dot{*}},\tau \mathrm{z}_{i+1},v_{j})\in U\mathrm{x}U\mathrm{x}J_{2}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}u_{i},v_{j})\in U\mathrm{x}J_{1}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{o}fi \mathrm{t}\mathrm{o}\mathrm{f}$$\mathrm{e}\mathrm{x}\mathrm{e}\mathrm{c}11\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{j}\mathrm{o}\mathrm{b}v_{j}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{L}\mathrm{e}\mathrm{t}U,J_{1},\mathrm{m}\mathrm{d}J_{2}\mathrm{b}\mathrm{e}\mathrm{a}\mathrm{s}$andis positive.
profit of executing job
in time units
and on edge set $E\cup F$ . Obviously,
Consider the hypergraph $H=(U\cup J_{1}\cup J_{2},E\cup F)$ on vertex set
proportional 2-ISP becomes the problem of findi amatching $E’\cup F’$ in $H$ with $E’\subseteq E$ and $F’\subseteq F$ suchthat $|E’|+2|F’|$ is maximized over all matchings in $H$ . Our idea is to reduce this problem to the problem ofhypergraph ( $i.e,$ . each hyperedge consists of exactly
finding amaximum cardinality matching in athree vertices). Since the latter problem admits a $(1.5 +\epsilon)$ -approximation algorithm [6] and our reduction isthat proportional 2-ISP admits a $(1.5+\epsilon)$ -approximation algorithm.
approximation preserving, it, there is a polynomial-time $(1.5+\epsilon)$ -apprvimation algorithm for prvportional
Theorem 3.1 For every$u_{\dot{|}}$$v_{j}$$u_{\dot{\iota}\dagger 1}$$U\cup J_{1}\cup J_{2}$$\cdot$$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{w}_{\llcorner}\mathrm{s}$$\epsilon>0$

2-ISP.

4Anew heuristic for protein NMR peak assignment
As mentioned in Section 1, the -approximation algorithm for 2-ISP can be easily incorporated into aheuristic
ffamework for protein NMR peak assignment introduced in[7]. The heuristic first tries to assign “long”
segments of three or more spin systems that are llllder the consecutivity constraint to segments of the hostprotein seqllence, lksing asimple graedy stratey, md then solves an instance of 2-ISP fomed by the remaining
unassigned spin systems and amino acids. The first step of the ffamework i8 ako called greedy $filter\cdot ng$ md
may potentially help improve the accuracy of the heuistic significantly in practice because we are often able toassign long segments of spin systems with high confidence. We have tested the new heuristic based on theapproximation algorithm for 2-ISP and compared the results with two of the baet approximation and heuristic
algorithms in[3, 4, 7], namely the 2-approximation algorithm for the interval scheduling problem $[3, 4]$ andthe branch-and-bound algorithm(augmented with greedy filtering)[7]. The test data consists of 70(pseudo)levels of consecutivity
ignment derived from 14 proteins, each with 5
real instances of NMR peakdatabase [9],entry in theconstraints,
shown in Table 1. Each protein is repre.qented fi.slevel is represented by the underscore symbol following the BioMagResBanke.g. bmr4027, md theof theentry. For example, -5 mems that the nllmber of pairs of consecutive spin systems in the input is
total number of spin systems. Hence, the higher the consecutivity level index, the more the constraint. The
is available to the public upon request to the authors.
program of the new$\frac{13}{7}$$\frac{13}{7}-$$(\mathrm{d}\mathrm{e}\mathrm{n}_{\iota}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{y})$$\mathrm{a}\mathrm{s}_{\iota}\mathrm{s}$$\mathrm{m}$$:\iota \mathrm{s}$$\mathrm{B}\mathrm{i}\mathrm{o}\mathrm{M}\mathrm{a}\mathrm{g}{\rm Re}_{\iota}\mathrm{s}\mathrm{B}\mathrm{m}\mathrm{k}$$\mathrm{c}\mathrm{o}\mathrm{n}\sec\iota \mathrm{l}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}$$50^{\sigma/0}$$\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{l}\Gamma\dot{\mathrm{L}}\mathrm{S}\mathrm{t}\mathrm{i}\mathrm{c}$References[1] A. Bar-Noy, R. Bar-Yehuda, A. Preund, J. Naor, and B. Schieber. Aunified approach to approximating
resource allocation and scheduling. Journal of the ACM, 48:1069-1090, 2001.
[2] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Approximating the throughput of multiple machines in.
real-time schedulng. Proceedings of$STOC’\mathit{9}\mathit{9}$[3] Z.-Z. Chen, T. Jiang, G. Lin, J. Wen, D. Xu, J. Xu, and Y. Xll. Approximation algorithms for NMR
spectral peak assignment. To appear in Theoretical Computer Science, 2002.
[4] Z.-Z. Chen, T. Jiang, G. Lin, J. Wen, D. Xu, and Y. Xu. Improved approximation algorithms for NMII

spectral peak assignment. Pmrxzdings of WABIEO(E.
[5] J. Chuzhoy, R. Ostrovsky, and Y. Rabani. Approximation algorithms for the job interval selection problem
and related scheduling problems. Proceedings of FOCS’2001.
[6] C.A.J. Hurkens and A. Schrijver. On the size of systems of sets of every t, of which have an SDR, with
an application to the worst-case ratio of heuristics for packing problems. SIAM Journal on Discrete
Mathematics, 2 (1) $:68- 72$ ,1989.
[7] G. Lin, D. Xu, Z.-Z. Chen, T. Jiang, J. Wen, and Y. Xu. An efficient branch-and-bound algorithm for the.
assignment of protein backbone NMR peaks. Pmexdings of[8] National Institute of General Medical Sciences. Pilot projects for the protein structure initiative (structural,1989.
genomics). $http.\cdot//wuw$. nih. $gov/gmnt\mathrm{s}/guide/rfa- flee/RFA- GM-g\mathit{9}-\theta\theta \mathit{9}$ .html, June:RFA$CSB’B\mathit{0}\mathit{0}\mathit{2}$$\mathrm{G}\mathrm{M}-99\triangleleft 09$[9] University of Wisconsin. BioMagResBank.
Wisconsin, 2001.

.bmrb. urise. edu. University of Wisconsin, Madison,$http.\cdot//um\prime u’$[10] Y. Xu, D. Xu, D. Kim, V. Olman, J. Razumovskaya, and T. Jiang. Automated assignment of backbone
NMR peaks using constrained bipartite matching. IEEE Computing in Science &Engineering, 4:50-62