### Mid-labeled Partial Digest

```Mid-labeled Partial Digest
Student: 蕭禕廷
1
Contents



2
1. Introduction
2. Partial Digest
3. Mid-labeled Partial Digest
1. Introduction
3
DNA
4
.
.
.
.
. TCAGGTCACA
. AGTCCAGTGT
.
.
.
.
.
.
Restriction Enzyme (限制內切酶)
EcoRI
G AAT T C
C T TAA G
5
Restriction Sites (切位)
EcoRI
G AAT T C
C T TAA G
G AAT T C
C T TAA G
Restriction Sites
6
G AAT T C
C T TAA G
2. Partial Digest
7
Partial Digest Problem

= { 1 , 2 , … ,  }

∆ =  −  1 ≤  <  ≤ }

Partial digest problem is to find , by
knowing ∆.
1
8
2
.
.
.
.
.
.

Partial Digest Problem Example
2
4
0
2
4
7
3
5
7
9
10
10
 ∆ = {2, 2, 3, 3, 4, 5, 6, 7, 8, 10}
6
8
Partial Digest Problem Algorithm

Skiena et al. gave an (2  lg ) algorithm
max ∆
10

∆ = { 2 2 3 3 4 5 6 7 8 10 }
0
10
8
11

∆ = { 2 2 3 3 4 5 6 7 8
0
10
?
12
}
8

∆ = { 2 2 3 3 4 5 6 7 8
}
8
0
8
13
10
8
2

∆ = {
0
7
10
8
7
3
1
14
}
2 3 3 4 5 6 7

∆ = {
0
3
8
3
7
5
15
}
2 3 3 4 5 6 7
10
16
⨉
o
.
.
.
. .
.
.
. . .
.

1
2
4
2−1
(+
2
2+1 − 1
17
Partial Digest ProblemAlgorithm
Each node

The total cost is (2  lg ).

18
needs ( lg ) time.

(lg )
∆
3. Mid-labeled Partial Digest
19
Mid-Labeled Partial Digest
1
2
.
.
.
.
.
.

partial digest
20
Mid-Labeled Partial Digest

= { 1 , 2 , … ,  },

∆ =  −

∆ , =  −   ,  contains exactly
, +1 , … ,  labels}
,  contains no labels}
1
21
1
2
= { 1 , 2 , … ,  }
2
.
.
.
.
.

.
.
.
.

Mid-Labeled Partial Digest
1
1
2
2
3
3
4 5
6
1
∆1,1
∆
1
2
3
∆1,3
22
Mid-Labeled Partial Digest Example
1
0
23
2
4

∆ = {2, 2, 3, 4}

∆1,1 = {3, 5, 6, 7, 8, 10}
7
10


∆ = { 2 2 3 4 }
∆1,1 = { 3 5 6 7 8 10 }
1 = 3
*
2 = 2
1
1
1 + 2 =  = 5 \$
1 2 = ∆1,1 = 6
24
2
\$
1 , 2 = {2, 3}


∆ = { 2 2 3 \$ 4 }
∆1,1 = { \$
3 5 6 \$7 8 10
\$ }
1 = 3
*
2 = 2
1
4
0
4
7 \$
25
7
3
8
\$
10
3
6
Mid-Labeled Partial Digest Algorithm
1
1
26
\$
22
1 +
1
2
Mid-Labeled Partial Digest Algorithm
1
2
. . .
. . .
1
27
2
−1

. . .
. . .

+1
Mid-Labeled Partial Digest Algorithm
. . .
−1

28
. . .

+1
+1
. . .
Mid-Labeled Partial Digest Algorithm
∆ ,
. . .
, +1,…,
. . .
−1

1
+1
. . .
+1
∆1,1
29
1
2
Mid-Labeled Partial Digest Algorithm
1
. . .
. . .
. . .
done
?
\$
∆11,−1
−1
30
−1

Mid-Labeled Partial Digest Algorithm
...
1 , … , 2−1
31
1 +  2
1
...
...
...
...
...
...

1
1
2
−1
∆1,−1

...
Mid-Labeled Partial Digest Algorithm
32
1 +  2
1
...
...
...
...
...
...

1 + 2
≤
1
Mid-Labeled Partial Digest Algorithm

Each node needs ( lg ).

The total time is (

1 +2
1
1
33
The
≤
2
+1
1
2 ...
1 +2
1
≤
2
+1

+1
2 lg )
~
1

2
+1
2
.
2

Stirling`s
: !
total
time approximation
is  2  lg+
. ~2 ≤ + 12

2
+1
2
31

Conclusion

For partial digest problem, Skiena et al. gave
an (2  lg ) algorithm.

For mid-labeled partial digest problem,
2
+1

34
2
3
there is an  2  lg  algorithm for
2  lg  for  = 1.
References
35

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein,
Introduction to Algorithms, Second Edition, 2001.

B. Lewin, Genes VII, 2000.

S. S. Skiena, W. D. Smith and P. Lemke, Reconstructing Sets
From Interpoint Distances, SOCG, 1990.

D. B. West, Introduction to graph theory, 1996.
36
```