%PDF-1.3
%
2 0 obj
<>
endobj
1 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
17 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
9 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
5 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
11 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
25 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
20 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
18 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
7 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
35 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
32 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
31 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
30 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
13 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
15 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
10 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
29 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
12 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
24 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
21 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
23 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
6 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
27 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
19 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
33 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
14 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
37 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
8 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
4 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
26 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 53/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0 q-Br44C@B 9 s
(P
endstream
endobj
3 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
16 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
34 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
22 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
36 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 54/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T R
Ɩf
!\!Y\ !p )P
endstream
endobj
28 0 obj
<>>>/Subtype/Form/BBox[0 0 612 792]/Matrix [1 0 0 1 0 0]/Length 55/FormType 1/Filter/FlateDecode>>stream
xs
w3T04PI2P0T5T0P02S04S @$P5 )1
endstream
endobj
38 0 obj
<>stream
Arbortext Advanced Print Publisher 9.0.114/W
2012-02-07T00:56:32-08:00
2011-11-09T17:24:16+05:30
application/pdf
untitled
Acrobat Distiller 8.1.0 (Windows)
uuid:da24d26d-058d-415c-82e7-4fc1c3620d3f
uuid:8b4bc5db-132b-461d-865b-c5b3f4812d5f
endstream
endobj
39 0 obj
<>stream
x+ |
endstream
endobj
40 0 obj
<>stream
xS**T0T0 Bil])D. qgj
endstream
endobj
41 0 obj
<>stream
x+ |
endstream
endobj
42 0 obj
<>stream
xS**T0T0 Bih]9D. qaj
endstream
endobj
43 0 obj
<>stream
x+ |
endstream
endobj
44 0 obj
<>stream
xS**T0T0 Bih] D. pa
endstream
endobj
45 0 obj
<>stream
x+ |
endstream
endobj
46 0 obj
<>stream
xS**T0T0 Bid]D. qdj
endstream
endobj
47 0 obj
<>stream
x+ |
endstream
endobj
48 0 obj
<>stream
xS**T0T0 Bil]D. pa
endstream
endobj
49 0 obj
<>stream
x+ |
endstream
endobj
50 0 obj
<>stream
xS**T0T0 Bid]%D. rs
endstream
endobj
51 0 obj
<>stream
x+ |
endstream
endobj
52 0 obj
<>stream
xS**T0T0 Bih]D. r^j
endstream
endobj
53 0 obj
<>stream
x+ |
endstream
endobj
54 0 obj
<>stream
xS**T0T0 BiU !D. _e1
endstream
endobj
55 0 obj
<>stream
x+ |
endstream
endobj
56 0 obj
<>stream
xS**T0T0 Bid]1D. pa
endstream
endobj
57 0 obj
<>stream
x+ |
endstream
endobj
58 0 obj
<>stream
xS**T0T0 BiUD* :
endstream
endobj
59 0 obj
<>stream
x+ |
endstream
endobj
60 0 obj
<>stream
xS**T0T0 BiU)D* 9V
endstream
endobj
61 0 obj
<>stream
x+ |
endstream
endobj
62 0 obj
<>stream
xS**T0T0 BiUD* 8
endstream
endobj
63 0 obj
<>/XObject<>/ProcSet [/PDF /Text /ImageB /ImageC /ImageI]/Font<>>>/Thumb 75 0 R/MediaBox[0 0 612 792]/Rotate 0>>
endobj
76 0 obj
<>/ProcSet[/PDF/Text]/Font<>>>
endobj
65 0 obj
<>stream
/GS1 gs
BT
/F1 1 Tf
9.9626 0 0 9.9626 74.0976 715.4644 Tm
0 0 0 1 k
0 Tc
0 Tw
[(exper)-9.4(iments.)-392.6(In)-390.5(these)-392.6(experiment)-12.6(s,)-389.3(a)-383.8(gene)-393.6(\(cause\))-397.1(is)-386.7(perturb)-8.2(ed)-390.3(and)-385.3(as)-391.5(a)-389.5(result)-390.6(othe)-7.6(r)-384(genes)-395.5(change)-391.2(their)]TJ
0 -1.195 TD
[(expre)-9.4(ssion)-242.3(levels)-242.5(\(effec)-10.2(ts\).)-236.2(Ass)-8.6(uming)-237.7(that)-243.7(each)-241.7(cause-ef)-12.7(fect)-239(pair)-242.9(should)-241.8(be)-236.6(connec)-9.9(ted)-240.2(by)-240.5(a)-235.9(direct)-10(ed)-236.6(path)-7.6(way)]TJ
0 -1.2007 TD
[(in)-271.7(the)-274.3(physical)-278.1(network,)-272.2(on)-7.2(e)-270(can)-267.6(predi)-10.3(ct)-267.8(an)-270.8(orient)-8.2(ation)-272.9(\(direc)-9.2(tion)-270.3(assignm)-10.1(ents\))-273.3(to)-266.1(the)-274.3(undirected)-276.6(p)-6.5(art)-270.6(of)-271(the)]TJ
T*
[(networ)-9.3(k)-336.5(that)-334.7(will)-339.6(best)-338.8(agree)-335.5(with)-342.6(the)-331.2(cause)-10.4(-effec)-10.2(t)-333.6(informat)-9.5(ion.)]TJ
1.0015 -1.2007 TD
[(The)-333.9(resu)-8(lting)-336.5(combina)-9.5(torial)-335.3(problem)-339.8(can)-335.9(be)-333.4(formali)-8.7(zed)-335.9(by)-331.6(repr)-8.8(esenting)-335.1(the)-336.9(networ)-9.3(k)-330.8(a)0(s)-334.6(a)-332.6(mixed)-336.3(graph)-7.6(,)]TJ
-1.0015 -1.2007 TD
[(whe)-8(re)-375.2(undirect)-11.5(ed)-373.2(edges)-378.5(mode)-8.4(l)-373.4(interact)-10.3(ions)-376.9(with)-376.7(unknow)-8.5(n)-370.7(causa)-10.4(l)-373.4(direct)-10(ion,)-375.3(and)-374(dir)-7(ected)-376.1(edges)-384.2(represent)]TJ
T*
[(int)-7.8(eractions)-288.4(with)-280(know)-7(n)-279.6(direct)-10(ionality.)-286.8(The)-282.7(cause-effe)-12.3(ct)-279.2(pairs)-284.7(are)-286.7(modele)-8.7(d)-279.6(b)0(y)-280.4(a)-275.7(collec)-9.8(tion)-281.7(of)]TJ
/F6 1 Tf
37.7966 0 TD
[(sourc)-8(e-target)]TJ
-37.7966 -1.2007 TD
[(vert)-10.6(ex)-375(pairs)]TJ
/F1 1 Tf
4.8939 0 TD
[(.)-370.3(The)-379.5(goal)-371.8(is)-375.4(to)-374.2(orient)-378.1(\(assign)-378.4(single)-377.3(direct)-10(ions)-371.2(to\))-376.9(the)-376.7(undirected)-379(edges)-378.5(so)-372.6(that)-380.2(a)-372.4(maximum)]TJ
-4.8939 -1.2007 TD
[(nu)-7.2(mber)-374.5(of)-379.1(source-tar)-11.5(get)-376.7(pairs)-375.7(adm)-7.6(it)-371.2(a)-378.1(directed)-383.2(path)-377.5(from)-380.4(the)-376.7(source)-381.2(to)-374.2(the)-376.7(target.)-380.2(We)-375.7(call)-382(this)-374(problem)]TJ
0 -1.195 TD
[(MA)-7.4(XIMU)-9.2(M-MIXED)-9.5(-GRAPH)-10.9(-ORIEN)-9.5(TATI)-8.6(ON.)]TJ
1.0015 -1.2007 TD
[(Previo)-10.3(us)-321.4(work)-327.6(on)-325.9(this)-328.4(and)-328.4(related)-331.2(problems)-330.3(can)-330.2(be)-322(cla)-8.6(ssied)-329.4(into)-327.2(theoretic)-11.1(al)-324.7(and)-322.7(appl)-7.6(ied)-325.5(work.)-328(On)-329.8(the)]TJ
-1.0015 -1.2007 TD
[(theo)-7.6(retical)-277(side,)-270.9(Arkin)-268.6(and)-271.5(Hassi)-9(n)-262.5(\(2002\))-276(studied)-269.9(the)-274.3(decision)-272.5(problem)-277.2(of)-265.3(orient)-8.2(ing)-266.8(a)-270(mixed)-273.7(graph)-269.3(to)-266.1(adm)-7.6(it)]TJ
T*
[(dir)-7(ected)-336.3(paths)-333.9(for)-330.6(a)-332.6(give)-7.6(n)-325.1(set)-338.1(of)-327.9(sourc)-8.8(e-target)-339.6(vertex)-337.2(pairs)-330.2(and)-334.1(show)-8.2(ed)-333.4(that)-329(thi)-7.8(s)-326.3(probl)-8.6(em)-331.2(is)-329.8(NP-)-7.4(comple)-8.7(te.)]TJ
T*
[(Th)-7(e)-235.9(probl)-8.6(em)-240.2(of)-242.5(nding)-239.9(strongl)-8.3(y)-239.8(connecte)-10.3(d)-239.8(orientations)-248.9(of)-242.5(graphs)-242.8(can)-244.9(be)-236.6(solv)-7(ed)-242.3(in)-237.6(polyn)-6.6(omial)-242.3(time)-241.5(\(Boesc)-10.3(h)]TJ
T*
[(and)-504.8(Tinde)-8.2(ll,)-502.5(1980;)-501.7(Chung)-503.6(et)-501.2(al.,)-501.9(19)-7.2(85\).)-499.7(Recent)-11.7(ly)-499.4(we)-502.3(prove)-7.6(d)-495.8(that)-505.4(MA)-7.4(XIMUM-)-8.9(MIXED)-9.7(-GRAPH)-10.9(-OR-)]TJ
T*
[(IEN)-8(TATI)-8.6(ON)-356.5(admit)-9(s)-354.8(a)-355.4(sub-li)-7.6(near)-361.4(polynomial)-9.8(-time)-358.1(appro)-7.6(ximation)-361.1(\(Elb)-7.6(erfeld)-362(et)-358.9(al.,)-354(201)-8(1\).)-356.7(For)-356.3(a)-355.4(com)-7.6(pre-)]TJ
T*
[(hensi)-9.6(ve)-293.5(discussion)-297.3(of)-293.7(the)-291.4(various)-297.6(kinds)-292.3(of)-293.7(graph)-297.8(orientations)-9.9(,)-290.6(w)0(e)-291.8(ref)-8(er)-289.8(to)-294.5(the)-291.4(textbook)-297.9(of)-293.7(Bang-J)-8.6(ensen)-293.1(and)]TJ
0 -1.195 TD
[(Gut)-9(in)-334.3(\(2008\).)]TJ
1.0015 -1.2007 TD
[(For)-293.7(the)-297.1(special)-301.9(case)-299.8(of)-293.7(an)-293.5(undirected)-305(network)-300.3(\(with)-294.1(no)-297.4(pre-directed)-300.9(edges)-8.6(\),)-293.3(the)-297.1(orientation)-303.8(problem)-299.9(was)]TJ
-1.0015 -1.2007 TD
[(show)-8.2(n)-387.7(t)0(o)-385.6(b)0(e)-390.3(NP-com)-9.3(plete)-394.2(and)-385.3(hard)-393.8(to)-385.6(appro)-7.6(ximat)-9(e)-383.8(t)0(o)-391.2(within)-392.4(a)-389.5(constant)-392(factor)-396.1(of)-384.8(11/12)-393.5(\()-82.4(Medve)-9.3(dovsky)]TJ
T*
[(et)-239.4(al.,)-240.1(2008\).)-239.5(On)-238.8(the)-240.2(posi)-7(tive)-238(side,)-242.5(Medvedovsk)-8.6(y)-239.8(e)0(t)-239.4(al.)-234.1(\(2008\))-241.8(provi)-8.6(ded)-237.4(an)-236.6(ILP-ba)-9.3(sed)-238.6(algo)-7.6(rithm,)-237.1(and)-243.1(showed)]TJ
T*
[(that)-323.3(the)-314.1(probl)-8.6(em)-314.1(is)-318.5(appro)-7.6(ximable)-325.2(to)-311.6(withi)-10.3(n)-313.7(a)-315.5(ratio)-320.4(of)]TJ
/F7 1 Tf
21.9257 0 TD
(U)Tj
/F1 1 Tf
.7398 0 TD
[(\(1/)-7(log)]TJ
/F6 1 Tf
2.7144 0 TD
(n)Tj
/F1 1 Tf
.5008 0 TD
[(\),)-316.1(whe)-8(re)]TJ
/F6 1 Tf
3.6704 0 TD
(n)Tj
/F1 1 Tf
.8137 0 TD
[(is)-318.5(the)-319.8(number)-319.1(of)-316.5(vertic)-10(es)-317.5(in)-317.3(the)]TJ
-30.3648 -1.2007 TD
[(networ)-9.3(k.)-336.9(The)-339.6(approximat)-10.8(ion)-335.1(ratio)-337.5(was)-339.2(later)-344.9(improv)-7.2(ed)-333.4(to)]TJ
/F7 1 Tf
23.4735 0 TD
(U)Tj
/F1 1 Tf
.7455 0 TD
[(\(log)-337.8(log)]TJ
/F6 1 Tf
3.568 0 TD
(n)Tj
/F1 1 Tf
.8365 0 TD
[(/)-333.6(log)]TJ
/F6 1 Tf
2.2307 0 TD
(n)Tj
/F1 1 Tf
.5008 0 TD
[(\))-338.5(\(Gamzu)-341.9(et)-336.1(al.,)-336.9(2010\).)-341.9(Dorn)]TJ
-31.3549 -1.2007 TD
[(et)-336.1(al.)-336.5(\(2011\))-338.6(stud)-7(ied)-336.9(the)-336.9(parameter)-12.9(ized)-333.7(com)-7.6(plexity)-339.8(of)-333.6(orient)-8.2(ing)-335.1(undirected)-344.8(networ)-9.3(ks.)]TJ
1.0015 -1.2007 TD
[(On)-335.5(the)-336.9(prac)-8.6(tical)-334.3(side)-8.8(,)-330.4(several)-341(auth)-7.6(ors)-335.5(studied)-338.2(the)-336.9(orient)-8.2(ation)-335.5(problem)-339.8(and)-339.8(related)-336.9(annot)-8.4(ation)-335.5(probl)-8.6(ems.)]TJ
-1.0015 -1.195 TD
[(Yea)-9.8(ng)-434(et)-432.9(al.)-433.2(\(2004\))-435.3(wer)-10(e)-429.3(the)-433.6(rst)-440.7(to)-431.1(use)-437.7(perturbation)-440.4(exper)-9.4(iments)-437.7(to)-431.1(annot)-8.4(ate)-435.4(protei)-8.2(n)-427.6(networ)-9.3(ks.)-435.6(They)]TJ
0 -1.2007 TD
[(propos)-7.7(ed)-384.6(a)-378.1(proba)-7.6(bilis)-7.6(tic)-379.5(mode)-8.4(l)-379.1(and)-385.3(an)-378.9(accomp)-13.5(anying)-384.7(inference)-390.6(appro)-7.6(ach)-381.4(to)-379.9(predi)-10.3(ct)-381.6(edge)-382.2(dir)-7(ections)-385.5(and)]TJ
T*
[(sign)-7(s)-263.7(o)0(f)-265.3(activa)-9.8(tion)-264.7(and)-271.5(repress)-9.6(ion)-261.1(from)-272.3(cause-ef)-12.7(fect)-267.4(data.)-271.5(Ourfali)-270.9(et)-262.2(al.)-268.2(\(2007\))-270.3(provided)-274.4(an)-265.1(ILP)-265(formu)-11.3(lation)]TJ
T*
[(for)-268(the)-268.6(problem)-271.5(of)-265.3(inferr)-9.4(ing)-266.8(edge)-268.4(signs)-265(that)-272.1(maximiz)-10.1(e)-264.3(the)-268.6(expected)-272.1(numb)-6.6(er)-267.1(of)-265.3(explain)-8.7(ed)-265.1(cause-ef)-12.7(fect)-267.4(pairs.)]TJ
T*
[(Gi)-8.2(tter)-348.1(et)-347.5(al.)-347.9(\(2011\))-350(used)-347.5(SATI)-8(SFIABIL)-10.5(ITY-based)-355.1(appro)-7.6(ximation)-8.3(s)-343.4(t)0(o)-345.7(tackle)-351.2(the)-348.3(ori)-7(entation)-353.7(problem.)-351.5(The)]TJ
T*
[(main)-267.2(cavea)-11(t)-259.6(o)0(f)-265.3(all)-265.7(these)-267.4(appro)-7.6(aches)-266.4(is)-267.2(that)-260.7(they)-269.4(depend)-269.9(on)-263.3(enumera)-10.5(ting)-264.7(all)-265.7(possibl)-7.6(e)-258.6(path)-7.6(s)-263.7(between)-267.8(a)-264.3(pair)-265.6(of)]TJ
T*
[(genes)-372.8(and,)-368.7(hence)-9.2(,)-364.6(they)-371.8(are)-366.3(limit)-7(ed)-367.5(to)-368.5(paths)-368.1(of)-367.7(very)-371(short)-368.2(length)-370.4(\(3)-367.7(for)-364.7(the)-371(rst)-366.7(two)-367.5(wor)-8.2(ks)-366.9(and)-368.3(5)-365(for)-370.4(the)]TJ
T*
[(latt)-7.4(er\).)]TJ
1.0015 -1.195 TD
[(Our)-378.1(main)-375.3(cont)-7.6(ribution)-374.9(in)-374.2(this)-379.7(article)-379.5(is)-375.4(a)-372.4(rst)-378.1(efcient)-376.7(ILP)-378.9(formulat)-9.5(ion)-374.9(of)-373.4(the)-376.7(orientation)-383.5(problem)-379.6(on)]TJ
-1.0015 -1.2007 TD
[(mi)-7.8(xed)-374(graphs,)-374.1(lea)-8.6(ding)-370(to)-374.2(an)-373.2(optim)-7.2(al)-376(solution)-374.1(of)-373.4(the)-376.7(problem)-379.6(on)-371.4(current)-379.8(networ)-9.3(ks.)-373(We)-375.7(impleme)-10.1(nted)-371.8(our)]TJ
T*
[(appro)-7.6(ach)-244.9(and)-243.1(appl)-7.6(ied)-245.8(it)-240.4(to)-243.3(a)-241.6(large)-245.4(data)-248.4(set)-241.3(of)-242.5(phy)-8(sical)-241.7(int)-7.8(eractions)-248.5(and)-243.1(knockou)-7.1(t)-242.5(pairs)-244.8(in)-243.3(yeast)-11.3(.)-239.4(W)0(e)-244.9(collec)-9.8(ted)]TJ
T*
[(int)-7.8(eraction)-240.9(and)-243.1(cause-ef)-12.7(fect)-239(pair)-242.9(informat)-9.5(ion)-238.4(from)-238.2(differ)-9.4(ent)-240.2(publication)-11.6(s)-235.3(and)-237.4(integr)-8.2(ated)-242.7(them)-238.8(into)-241.9(a)-235.9(physi)-7.8(cal)]TJ
T*
[(networ)-9.3(k)-370.7(with)-371(3,658)-373.3(proteins,)-375.5(2,639)-373.3(PPIs,)-369.2(4,095)-373.3(PDIs,)-373.9(along)-372.6(with)-371(53,809)-374.1(knockou)-7.1(t)-367.7(pairs)-375.7(among)-373.3(the)-371(mo-)]TJ
T*
[(lec)-8.6(ular)-254.3(component)-11(s)-246.6(o)0(f)-253.9(the)-251.5(networ)-9.3(k.)-251.5(We)-250.6(carrie)-11(d)-251.1(out)-249.7(a)-252.9(number)-256.6(of)-248.2(exper)-9.4(iments)-255.6(to)-249(mea)-9.4(sure)-252.7(the)-251.5(accuracy)-261.7(of)-253.9(the)]TJ
T*
[(ori)-7(entations)-258.9(produc)-8.3(ed)-259.4(by)-251.9(our)-254.6(method)-263(for)-256.6(different)-260.9(input)-259.7(scena)-10.4(rios.)-254.1(In)-259.6(particular,)-264.6(we)-257.6(studied)-258.5(how)-256.6(the)-257.2(portion)]TJ
T*
[(of)-248.2(undirected)-253.8(interact)-10.3(ions)-246(and)-243.1(the)-245.8(numb)-6.6(er)-244.3(of)-242.5(cause)-10.4(-effec)-10.2(t)-242.5(pairs)-244.8(aff)-8(ect)-241.9(the)-245.8(ori)-7(entations.)-253.6(We)-244.9(further)-249.1(comp)-8.4(ared)]TJ
0 -1.195 TD
[(ou)-7.2(r)-486.4(performanc)-11.1(e)-491.9(t)0(o)-488(that)-494.1(of)-487.2(two)-492.7(layman)-492.4(appro)-7.6(aches)-494.1(that)-494.1(are)-491.5(based)-492.3(on)-490.9(orient)-8.2(ing)-488.7(undirect)-11.5(ed)-487(networ)-9.3(ks,)]TJ
0 -1.2007 TD
[(ignor)-8.6(ing)-295.3(the)-297.1(edge)-302.5(direction)-9.3(ality)-298.4(inf)-7(ormation.)-303.8(We)-296.1(dem)-7.6(onstrate)-302.9(that)-300.6(our)-294.5(method)-302.9(retain)-10(s)-292.2(more)-300.6(inform)-9.1(ation)-295.7(to)]TJ
T*
[(gu)-7.2(ide)-331.2(the)-336.9(sear)-9.8(ch,)-333.7(achievi)-10.5(ng)-331.6(highe)-8.4(r)-332.8(numb)-6.6(ers)-337.3(of)-333.6(correctly)-346.1(oriented)-341.5(edges.)]TJ
1.0015 -1.2007 TD
[(The)-385.2(artic)-9.2(le)-381.7(is)-381.1(organ)-7.6(ized)-385(as)-380.1(follow)-10.3(s:)-381.1(In)-379.1(Sect)-8.6(ion)-380.6(2,)-382.4(we)-382.8(provide)-387.4(prelimi)-9.5(naries)-384(and)-385.3(dene)-387.9(the)-382.4(orient)-8.2(ation)]TJ
-1.0015 -1.2007 TD
[(probl)-8.5(em.)-439.7(In)-441.7(Section)-446.1(3,)-439.3(we)-445.4(present)-447.3(an)-441.5(ILP-based)-447.1(algo)-7.6(rithm)-441.6(to)-436.8(solv)-7(e)-440.7(the)-439.3(ori)-7(entation)-444.8(problem)-447.9(on)-439.7(mixed)]TJ
T*
[(graph)-7.6(s.)-332.4(In)-339.2(Section)-338(4,)-331.2(we)-337.3(disc)-8.8(uss)-334.7(our)-334.3(impleme)-10.1(ntation)-339.8(of)-333.6(this)-334.1(algo)-7.6(rithm,)-333.9(and)-339.8(in)-334.3(Section)-338(5,)-336.9(we)-331.6(repor)-9.6(t)-333.6(o)0(n)-331.6(its)]TJ
T*
[(appl)-7.6(ication)-341.6(to)-334.3(orient)-338.2(physical)-340.7(networ)-9.3(ks)-332.8(in)-334.3(yeast)-11.3(.)]TJ
/F2 1 Tf
10.959 0 0 10.959 237.8834 117.7511 Tm
[(2.)-501.9(PRELIMINAR)6.4(IES)]TJ
/F1 1 Tf
9.9626 0 0 9.9626 84.0755 93.8268 Tm
[(We)-330.2(focus)-327.4(on)-320.2(simpl)-8.4(e)-321.2(g)-6.5(raphs)-327.4(with)-325.5(no)-325.9(loops)-326.4(or)-322.2(para)-8.6(llel)-326.1(edges.)-327.6(A)]TJ
/F6 1 Tf
25.8692 0 TD
[(mixed)-332.7(graph)]TJ
/F1 1 Tf
5.4345 0 TD
[(is)-324.2(a)-326.9(triple)]TJ
/F6 1 Tf
4.2167 0 TD
(G)Tj
/F8 1 Tf
1.0527 0 TD
(=)Tj
/F1 1 Tf
.8877 0 TD
(\()Tj
/F6 1 Tf
.3357 0 TD
(V)Tj
/F1 1 Tf
.6146 0 TD
(,)Tj
/F6 1 Tf
.5747 0 TD
(E)Tj
/F1 1 Tf
7.4718 0 0 6.641 478.6014 92.1826 Tm
(U)Tj
9.9626 0 0 9.9626 483.9873 93.8268 Tm
(,)Tj
/F6 1 Tf
.5691 0 TD
(E)Tj
/F1 1 Tf
7.4718 0 0 6.641 495.7794 92.1826 Tm
(D)Tj
9.9626 0 0 9.9626 501.1652 93.8268 Tm
(\))Tj
-42.8669 -1.2007 TD
[(that)-334.7(consi)-9.5(sts)-331.8(of)-333.6(a)-332.6(set)-332.4(of)-333.6(vertices)]TJ
/F6 1 Tf
13.3671 0 TD
(V)Tj
/F1 1 Tf
.6146 0 TD
[(,)-330.4(a)-332.6(set)-332.4(of)]TJ
/F6 1 Tf
3.972 0 TD
[(undir)-7.8(ected)-336.3(edges)-332.9(E)]TJ
/F1 1 Tf
7.4718 0 0 6.641 331.3133 80.2205 Tm
(U)Tj
/F9 1 Tf
9.9626 0 0 9.9626 338.3432 81.8646 Tm
(4)Tj
/F1 1 Tf
1.1666 0 TD
({)Tj
/F6 1 Tf
.4837 0 TD
(e)Tj
/F9 1 Tf
.6146 0 TD
(4)Tj
/F6 1 Tf
1.1666 0 TD
(V)Tj
/F10 1 Tf
.7853 0 TD
(r)Tj
/F11 1 Tf
.552 0 TD
(j)Tj
/F6 1 Tf
.2731 0 TD
(e)Tj
/F11 1 Tf
.4496 0 TD
(j)Tj
/F8 1 Tf
.4382 0 TD
(=)Tj
/F6 1 Tf
.717 0 TD
(2)Tj
/F1 1 Tf
.5008 0 TD
[(},)-335.1(and)-334.1(a)-326.9(set)-338.1(of)]TJ
/F6 1 Tf
6.2312 0 TD
[(d)-6.5(irected)]TJ
-39.9021 -1.2007 TD
[(edges)-281.7(E)]TJ
/F1 1 Tf
7.4718 0 0 6.641 105.7889 68.2583 Tm
(D)Tj
/F9 1 Tf
9.9626 0 0 9.9626 112.8189 69.9023 Tm
(4)Tj
/F6 1 Tf
1.1666 0 TD
(V)Tj
/F8 1 Tf
.9503 0 TD
()Tj
/F6 1 Tf
.8877 0 TD
(V)Tj
/F1 1 Tf
.6146 0 TD
[(.)-273.5(W)0(e)-279(assum)-11.5(e)-275.7(that)-277.8(every)-282.5(pair)-277(of)-276.6(vertices)-281.9(is)-278.6(either)-283.1(connecte)-10.3(d)-273.9(b)0(y)-274.7(a)-281.4(single)-280.5(edge)-279.8(of)-276.6(a)-275.7(specic)]TJ
/F2 1 Tf
-7.5058 67.0005 TD
[(14)-7.2(38)-31111.8(SI)-7.6(LVERBUS)-13.4(H)-334.4(E)0(T)-335.3(AL.)]TJ
ET
endstream
endobj
77 0 obj
<>stream
hlOkSAߤVICB %*IKjE'y7yy3efC좫BEЅB܈ 8ʅww9?8y;ݭh^YVWra@ųG6ͷsswBHbCX˰!2zk;ס!lJ02QF4Y11>*O\+HhmSZ@+N- (3)*а2az
Lb#BAtWcr8TJu6
SgrGUo2o^'dkh\\:sb]֯ۯWFFB$)۟~Lybj>ޫ