page 141:

Algorithm 7.1 (Greedy)

WAS:

1. \Tau <- {f_1,f_2,...,f_N} S <- 0

2. while \Tau is not empty, do

        for s,t in \Tau with max{ov(s,t)} (s=t possible)

        (a)     if s is not equal to t, merge s and t to uvw

        (b)     if s = t remove s from \Tau; add s to S.

3. when \Tau is empty output T the concatenation of strings in S

1. \Tau <- {f_1,f_2,...,f_N}, S <- 0

2. while \Tau is not empty, do

        for s,t in \Tau with max{ov(s,t)} (s=t possible)

IS :

1. \Tau <- {f_1,f_2,...,f_N} ; S <- 0

2. while \Tau is not empty, do

        for s,t in \Tau with max{ov(s,t)} (s=t possible)        
        
        (a)     if s is not equal to t, merge s and t to uvw

                add uvw to \Tau

                remove s,t from \Tau

        (b)     if s = t remove s from \Tau; add s to S.

3. when \Tau is empty output T the concatenation of strings in S

Correction by Steven Salzberg, 10/5/95.

page 144:

WAS: Overcap can be evaluated by an alignment score (See Chapter 9). . . . S(a,b) is the maximum score over all alignments of a and b.

IS: Overlap can be evaluated by an alignment score (See Chapter 9). . . . S(a,b) is the maximum score over all alignments of a and b, where |a| = n, |b| = m.

Correction by Steven Salzberg, 10/5/95.

Page 144

WAS:

$A(i,j) = \max\{S(a_k a_{k+1} \cdots b_l b_{l+1} \cdots b_j)$,

IS:

$A(i,j) = \max\{S(a_k a_{k+1} \cdots a_i, b_l b_{l+1} \cdots b_j)$,

Correction by Alessandro Rizzi, 10/10/96

Page 146:

Last line on the page

WAS:

(s_i = a)I + r_j

IS:

(s_i = a) + r_j

page 151:

Correction by Steven Salzberg, 10/5/95

page 152:

To apply Theorem 7.5 to SBH data, we need to transform the SBH graph G in a simple way. To see the necessity for this, consider the case where a particular k-tuple is repeated twice (and no other k-tuple repeats exist). As the first repeat can be uniquely identified with s and the second with t, there is a unique Eulerian cycle. However, the cycle graph is

where two vertices with in(v) = out(v) = 2 are the repeated (k-1)-tuples, and the lower arc of C_2 represents the path between the k-tuple repeats.

Correction by Steven Salzberg, 10/5/95

page 154:

7.2.1 Other SBH Designs

WAS: This is just the largest n such that the extention probability is small.

IS : This is just the largest n such that the extention probability is large.

Correction by Steven Salzberg, 10/5/95

page 155: (binary chip branching probability)

WAS: \cong 1 - ((1 - {1 \over {2^k 4}})^{n-k})^2 . . .

IS: \cong (1 - (1 - {1 \over {2^k 4}})^{n-k})^2 . . .

Correction by Paul Hardy, 20 February 1996

Previous Level

USC Computational Biology Home Page