Optimal sequencing by hybridization in rounds.
Sequencing by hybridization (SBH) is a method for reconstructing a sequence over a small finite alphabet from a collection of probes (substrings). Substring queries can be arranged on an array (SBH chip) and then a combinatorial method is used to construct the sequence from its collection of probes. Technological constraints limit the number of substring queries that can be placed on a single SBH chip. We develop an idea of Margaritis and Skiena and propose an algorithm that uses a series of small SBH chips to sequence long strings while the number of probes used matches the information theoretical lower bound up to a constant factor.
Introduction
Consider the following problem. Let  be an alphabet with  letters. Given
a string s drawn uniformly at random from  n and the ability to ask queries
of the type: "Is x a substring of s?". What is the minimum set of such
questions one can ask such that with high probability one can reconstruct s.
The problem is an abstraction of a problem that occurs in the sequencing
of DNA molecules. DNA strands can be seen as sequences drawn from the
four letter alphabet of nucleotides fA; C; G; Tg.
Sequencing by hybridization (SBH) (Bains and Smith, 1988; Drmanac
et al., 1989; Lysov et al., 1998) has been proposed as an alternative to the
traditional Gilbert-Sanger method of sequencing by gel electrophoresis; The
surveys (Chetverin and Cramer, 1994; Pevzner and Lipshutz, 1994) give an
overview of both the technological and algorithmic aspects of the method.
The method applies the complementary Watson-Crick base pairing of DNA
molecules. A given single stranded DNA molecule will hybridize with its
complement strand. SBH is based on the use of a chip, fabricated using
photolithographic techniques. The active area of the chip is structured as
a matrix, each region of which is assigned to a specic oligonucleotide, biochemically
attached to the chip surface. A solution of
uorescently tagged
target DNA fragments are exposed to the chip. These fragments hybridize
with their complementary fragment on the chip and the hybridized fragments
can be identied using a
uorescence detector. Each hybridization (or lack
thereof) determines whether the fragment is or is not a substring of the target
string. In our formulation we will assume that the the hybridization chips
can give us an answer to a ternary query: whether a string does not occur,
occurs once or occurs more than once.
The classical sequencing chip design C(m), contains all  m single stranded
oligonucleotides of some xed length m. Pevzner's algorithm (Pevzner, 1989)
for reconstruction using classical sequencing chips interprets the results of
a sequencing experiment as a subgraph of the DeBruijn graph, such that
any Eulerian path corresponds to a possible sequence. The reconstruction
therefore is not unique unless the Eulerian path is unique.
Examples can be found that show that in order to uniquely reconstruct all
members of  n using a classical sequencing chip, C(m), m needs to be greater
than n(see (Skiena and Sundaram, 1995)). Pevzner et al. (1991) show experimentally
that the classical C(8) chip which contains 65.536 oligonucleotides
su-ces to reconstruct 200 nucleotide sequences in only 94 out of 100 cases.
Dyer et al. (1994) and Arratia et al. (1996) have shown independently that
for C(m) to be eective on random strings of length n, m needs to be chosen
greater than 2 log  n. In other words, for there to be a constant probability
that we can reconstruct a string of length n drawn uniformly at random
from  n using a classical hybridization chip, the chip must contain at least
substrings. This compares to the information theoretical lower bound on
the number of ternary queries needed to distinguish between  n elements of
n).
A variety of dierent methods have been suggested to overcome these
negative results for the classical SBH chips. Using the assumption that universal
DNA bases can be synthesized Preparata et al. (Preparata et al., 1999;
Preparata and Upfal, 2000) give a scheme for which the size of the chip is
optimal i.e. O(n). Broude et al. (1994) suggest generating positional information
along with the hybridization information (PSBH). PSBH was analyzed
algorithmically by Hannenhalli et al. (Hannenhalli et al., 1996) which
show NP-hardness of the general problem and give an e-cient algorithm if
the positional information is only o by a constant. This model was further
analyzed by Ben-Dor et al. (Ben-Dor et al., 1999). Drmanac et al. (1989)
suggested sequencing large sequences by obtaining spectra of many overlapping
fragments. This model was analyzed algorithmically by Arratia et
al. (1996) giving bounds on the probability of unique reconstruction. Shamir
and Tsur (2001) recently improved on the analysis of Arratia et al. (1996)
and furthermore gave an algorithm for the case when false negative errors
occurred in the hybridization.
Sequencing by hybridization in rounds or interactive sequencing by hybridization
was rst considered by Margaritis and Skiena (1995). The
assumption here is that the sequencing queries can be done adaptively and
once the results of one hybridization round are known a new chip can be
constructed. In their original paper Margaritis and Skiena give a number
of upper and lower bounds on the number of rounds needed dependent on
the number of probes allowed in each round. Among their results was an
algorithm that reconstructs a sequence with high probability using O(log n)
chips each containing O(n) queries. The main result of this paper improves
on this result. A few other papers have been written on ISBH. Skiena and
Sundaram (1995) showed that if only a single query could be asked in each
round nrounds are necessary and ( 1)n rounds are su-cient for string
reconstruction. Kruglyak (Kruglyak, 1998) gave an algorithm with a worst
case performance guarantee which shows that O(log n) rounds are su-cient
queries are placed on a chip in each round.
The following theorem is the main result of this paper.
Theorem 1.1 With high probability a string s drawn uniformly at random
from  n can be reconstructed by sequentially using seven hybridization chips
each containing O(n) substring queries.
Notice that this result is optimal for the number of queries in the information
theoretical sense, up to a constant multiple. Our algorithm proceeds
in the following manner. In its initial step we ask substring queries corresponding
to the classical SBH chip. We then construct the DeBruijn graph
in the way suggested by Pevzner. We then proceed to ask targeted queries
in order to unravel the string.
The main result of this paper is mathematical, although it may eventually
have some practical relevance. Sequencing chips similar to the classical
chips are already in production by Hyseq Inc., which holds several patents on
the procedure (Drmanac, Crkvenjakov, 1993). These chips have been used
for successfully for De-Novo sequencing (Drmanac et al., 1993) (sequenc-
ing when sequence is unknown). Given that many organisms have been
sequenced another problem of practical importance is resequencing by hybridization
(Drmanac et al., 1989; Pe'er and Shamir, 2000), in this problem
a template sequence is known and the goal of the sequencing is to determine
the specic mutational variants of the sequence. Machines for producing
oligonucleotide arrays using ink-jet printer technology have been pioneered
by Blanchard et al. (1996) and are currently being manufactured by Agilent
Technologies. This technology may prove to be particularly useful for interactive
sequencing by hybridization. For a review of dierent technologies
for DNA array manufacturing see (Blanchard, 1998; Schena, 1999). Other
relevant technologies include Aymetrix type arrays (Lockhart et al., 1996;
Fodor et al., 1991) and Southern Array Makers developed by Oxford Gene
Technologies (Southern, 1996). We note that technological constraints need
to be considered before a practical implementation of the method developed
in this paper. In particular, the more realistic case when false positive and
negative errors occur in the experiments needs to be considered.
The organization of the paper is as follows. In the next section we will give
overview of previous work. This will motivate our algorithm and we will give
a simplied version of it. In Section 3 we will give our complete algorithm
and verify its correctness. In Section 4 we will prove our complexity result
and in Section 5 we demonstrate our computational experience.
CTG#

Figure

1: The DeBruijn-graph constructed if the the substrings of s of length
3 are AGC, GCT , TGC, CTG, GCA and CAT and each one occurs once.
Motivation and basic algorithm
2.1 DeBruijn graphs
In this section we review the DeBruijn graph construction rst considered
by Pevzner s be our unknown target string. Given the answer of
a ternary query for all strings r of length m, whether r occurs once in s,
more than once, or not at all, we can construct an associated edge-labeled
digraph, D s
m , in the following manner. The vertex set of D s
m consists of
There is no edge from x 1
2g in which case the edge is labeled 1 if x 1
occurs once and 2  if x 1 occurs more than once in s. In
what follows we will call this the DeBruijn graph of s. Figure 1 shows the
construction of a DeBruijn graph.
We will also label the nodes of D s
m , a node x will be labeled 0 if it has no
in- or out-edges, it will be labeled 1 if it has at most one in-edge and at most
one out-edge both labeled 1, and labeled 2  otherwise. Let (x) denote the
label of a node/edge x.
We note that there is a unique path in D s
m for any substring x
of s where k  m 1, namely the path starting at x 1 ending
at x k m+2 x that traverses all of the edges x i x
1g. We will denote this path by P(x) and refer to it as the
path in D s
m corresponding to x. In the special case where k is m 1 or m we
will refer to it as the node/edge corresponding to x.
Pevzner showed that s corresponds to an Eulerian path in this graph.
Where we dene an Eulerian path in this graph to be any walk that traverses
the edges with label 1 exactly once and the edges with label 2  at least
twice. From the graph in Figure 1 we can tell that the original string s is
AGCTGCAT.
GC GC
GCA GC GCA
GCAT GC GCA

Figure

2: Examples of the mapping P(x), when
CTG#

Figure

3: The DeBruijn-graph constructed if the substrings of s of length 3
are AGC, GCT , CGC, GCG, TGC, CTG, GCA and CAT and each one
occurs once.
The DeBruijn graph may however have more than one Eulerian path. In
this case the construction of string s is ambiguous (see Figure 3).
2.2 Simplied algorithm
Our algorithm proceeds by constructing the DeBruijn graph for all substrings
of some xed length m. We then use information from that graph to construct
a set of substring queries that enable us to determine all substrings of s of
length number larger than m. We then iterate this
process noticing that the probability that D s
m is a path increases with m.
I.e. we will attempt to elongate the strings corresponding to the nodes in the
DeBruijn graph.
To motivate our algorithm let us look at where the ambiguities are in this
elongation process. Notice that if a node x in the DeBruijn graph has label
1, then each of the strings corresponding to the in- and out-edges occurs
only once in s. The elongation of the string corresponding to the in-edge
of x is hence unambiguous and can be determined by appending to it the
last character of the string corresponding to the out-edge. For example from
the graph
# TAGT we know that the string
CATAGT occurs in s. However if a node x has more than one in- or out-edge
we need to pair the in-edges with the out-edges.
ATAC

Figure

4: A node with two in- and out-edges
From the graph in Figure 4 we can tell that two of the strings CATACA,
CATACG, GACACA, GACACG occur in s but not which ones. To determine
all substrings of length six we would ask substring queries for each of these
strings. The central question in the remainder of this paper is to determine
conditions such that the number of queries generated in this way is not too
large.
If each of the edges in this graph was labeled 1 they would have a unique
elongation. To determine the elongation of the string CATAC by k characters
it would be su-cient to determine whether CATAC elongates to CATACA
or CATACG and then determine the elongation of ATACA or ATACG by
characters.
However if CATAC elongates to CATACG and ATACG occurs two or
more times in s then ATACG will have two elongations of length k 1 and
we cannot determine which is the elongation of CATAC. We see that to
determine the elongation of a particular edge e by k characters it is su-cient
to determine all paths from e that either (1) have length k or (2) are shorter
and end at an edge of multiplicity one.
This motivates the denition of a cluster, a collection of nodes and edges
that all have label 2  . Only when the Eulerian path passes through those
nodes and edges that have label 2  is the determination of the string am-
biguous. The set of clusters in the graph is the set of ambiguous parts of the
graph.
Denition 2.1 The cluster containing x, Cl(x), is the maximal connected
subgraph of D s
containing x such that nodes and edges
Our task is to determine s which can be thought of as determining an
Eulerian path from the start node of D s
m to the end node of D s
. Notice that
any internal node or edge labeled 1 has a unique occurrence in s, and will
therefore have a unique elongation. Assuming that we know which nodes
are the start node and the end, node we can reconstruct s by determining a
path from the start node to an edge labeled 1. We can then determine the
continuation of the Eulerian path from that edge by its unique elongation to
either another edge of label 1 or to the end node.
This motivates the following algorithm for reconstructing s. Let c be a
positive constant and Q be the set of queries, to be placed on the DNA chip.
Algorithm 1
Step 1. Classical SBH chip.
ne
Ask the queries in Q and construct D s
.
Step 2. Resolve ambiguities.
Let C s
While C s
choose a node x from C s
Let C Cl(x). C s
Let Q be the set of strings
1g.
or
Step 3. Reconstruct s from the DeBruijn graph
and the answers to the queries Q.
2.3 Potential pitfalls
Let us look at the complications we may face in the analysis of the algorithm.
If there is a cycle in the DeBruijn graph we cannot determine whether a given
string passes through the cycle or past it and we will add queries for both
possible strings. This may cause us to ask a large number of queries for each
such cycle.
As an example of this in Figure 5 we have a loop in AAA and the edge
from AAA to AAC has label 2  . We cannot determine from the graph
AAAA#

Figure

5: Example of a cluster along with its in and out edges, the cluster
being those nodes and edges having label 2  .
which two of the strings TAAACA, TAAACT, TAAAACA, TAAAACT,
CAAACA, CAAACT, CAAAACA or CAAAACT occur in s. The algorithm
will add the queries TAAAA, CAAAA, TAAACA, TAAACT, CAAACA,
TAAACA, AAAACA, AAAACT. As the edge AAAA occurs only once in
the graph we can rst determine whether TAAAA or CAAAA occurs in s
and then determine the occurrence of TAAAACA, TAAAACT, CAAAACA
and TAAAACT from which of the strings AAAACA or AAAACT occurs in
s.
If the cluster contains no cycles the number of queries generated by this
algorithm will grow as the number of in-edges times the number of out-edges
of the cluster. If the cluster contains cycles we may not be able to determine
how often a given path traverses the cycle. If it contains multiple cycles the
same holds true for each one of them, the number of queries generated by
the algorithm may therefore grow exponentially with the number of cycles
in the cluster. Notice that the occurrence in s of a string corresponding to
a node in the graph is highly correlated with the occurrence of the strings
corresponding to its neighbors. This interdependence makes the algorithm
di-cult to analyze. Complex clusters that require a large number of queries
have a reasonable probability of occurring and the average number of queries
generated by the algorithm may in fact be large.
Modied Algorithm
We modify the previous algorithm so that we only make a limited number
of queries initiating at any given node in the graph. Using two rounds of
queries we may hence not be able to determine s, but we will show that with
high probability seven rounds will be su-cient. We will use the following
modication of Step 2. Notice also that this modied version doesn't assume
prior knowledge of the start and end nodes as we will add queries starting at
any node in the cluster and terminating at any node. Let k
times
Let Q be the set of strings
Ask the queries in Q.
Construct D s
.
3.1 Correctness of algorithm
Let us clarify the statement of Theorem 1.1.
Denition 3.1 We say that an event occurs with high probability (whp) if
it occurs with probability 1 o(1) as n !1.
Lemma 3.1 The number of substring queries generated by an algorithm satisfying
the conditions of Theorem 1.1 is optimal in the information theoretical
sense, up to a constant multiple.
Proof: There are  n strings of length n and for there to be high probability
that we can sequence all the strings we must be able to distinguish between
strings. There are 3 m possible answers to m ternary queries.
n). Our algorithm generates O(1)
queries.
We now verify that the algorithm is correct, i.e. whp it reconstructs s.
Lemma 3.2
(a) A single iteration of Step 2 0 on D s
will allow us to construct D s
(b) After applying Step 2 0 we can whp reconstruct s.
Proof: (a) For each substring x of length m we add a query for all possible
elongations either of length k 0 or from x to a string y that has multiplicity
one, in which case the elongation of x can be determined from the unique
elongation of y. (b) follows from the result in Arratia et al. (1996) and Dyer
et al. (1994) that whp the DeBruijn graph D s
random s 2  n .
4 Complexity Analysis
We now proceed to estimate the expected number of queries in each iteration.
The main goal of this section is to prove the following lemma.
Lemma 4.1 The expected number of queries in Q generated by a single iteration
of Step 2 0 is O(n).
We will start by dening normal nodes in Section 4.1. We will then show
that the queries generated originating at a normal node form a tree. In
Section 4.2, we will bound the number of such trees. In Section 4.3, we will
consider the relationship between trees and substrings of s. In Section 4.4,
we summarize and upper bound the expected number of queries generated
originating at normal strings. In Section 4.5 we show that it is rare that a
node is not normal, and hence prove Lemma 4.1. Finally, in Section 4.6, we
show concentration of the expectation of the number of queries.
4.1 Normal substrings
Denition 4.1 For every node x 2 D s
m we dene a subgraph L x of D s
m . Its
edge and vertex sets are the sets of edges and vertices reachable from x by
a path x 1
1g.
We say that x and L x are normal if L x is a tree that does not contain end
and all substrings y of s that P maximally maps 1 to L x occur disjointly in s.
Notice that the denition of normal refers to substrings of s, i.e. a node
will be normal depending on the string s. In the example in Figure 5 L TAA
is the graph shown except for the node CAA and edge CAAA. L TAA is not
normal since it contains a cycle. Figure 6 shows LAAC .
4.2 Counting the number of trees
We will now bound the expected number of queries in Q whose initial string
is x if L x is normal. Notice that in this case the algorithm will in Step 2 0
generate one query with initial string x for every node in L x , other than x
1 I.e. the collection fy  s
substring relation.
AACA# ACA
ACT

Figure

example in Figure 5. We consider LAAC to be normal if s
is of the form *AACA*AACT*, where * denotes any string and not normal
if s is of the form *AACAACT* since here the two strings overlap.
and its children. Also notice (by Denition 4.1) when L x is normal it does
not contain a cycle and must therefore be a tree.
Denition 4.2 We say that an -ary tree (each node has at most  children)
is a (b; i; l)-tree if it has b branching nodes (nodes with more than one child),
single child nodes and l leaves. The children of a node will be considered
to be ordered and we will make a distinction between two children of a node
based on their ordering.
We can now count the expected number of queries whose initial string is
x by counting the number of dierent (b; i; l)-trees and then in Section 4.3
estimating the probability that L x is such a tree.
Lemma 4.2 The number of distinct (b; i; l)-trees is at
Proof: The number of trees with b branching nodes and l leaves is at most( 1)k+1
since it is less than the number of -ary trees
of size k (see (Knuth, 1968), Ex. 2.3.4.4.11). We now insert the internal
non-branching nodes into the tree by subdividing one of the existing edges
in the tree or adding a new single child root node. The choice of where to
put the internal nodes can be done in i+k 1
ways and the out-edges of the
internal nodes can be chosen in  i ways.
4.3 From trees to strings
We will now estimate the probability that L x takes the form of a tree T ,
and multiply by the number of queries generated if L x takes this form. To
avoid signicant over-counting of the number of queries with initial string
x, we count only the number of queries terminating at leaf nodes of T ; The
queries with initial string x that terminate at internal nodes of T can then
be counted when estimating the number of queries generated when L x takes
the form of one of the subtrees of T .
We will now dene a partial ordering of trees. This partial ordering
ensures that we count all the queries to the internal nodes as well.
Denition 4.3 A subtree T 0 of a labeled tree T , is an incubating subtree if,
for each node v in T , either all or none of the children of v occur in T 0 .
Note that by this denition all children of a given node must be removed
at the same time. Rephrasing, T descends from T 0 through a series of incubation
operations where all children of any given node appear in the same
operation. For the purpose of our proof, the important thing to note here is
that each node in T is a leaf node of some incubating subtree of T .
The following observation is immediate from Denition 4.1 of normal and
Denition 4.3.
Lemma 4.3 Given a collection C of nodes of a normal L x such that for all
y is not a predecessor z then there exist disjoint substrings
of s corresponding to each of the nodes in C. In particular the collection of
leaves of any (incubating) subtree of L x is such a collection.
We will now relate the trees L x to substrings of s. The following definition
gives a minimal requirement on the occurrence in s of the strings
corresponding to the nodes of L x .
Denition 4.4 We say that a collection C of strings is a string decomposition
of a tree T if each string corresponding to an edge occurs as a substring
in C and the strings corresponding to the edges that are not incident to the
root or the leaves occur twice as substrings in C.
A string requirement labeling of a tree T is dened by labeling
if e is a root edge or an edge between a branching node and a leaf, otherwise
2.
e l(e) and
e out of b l(e):
We now show an upper bound on the probability that L x takes form T in
four steps. First we give an algorithm that returns a particular type of string
decomposition. Then we bound the number of possible string decompositions
generated by the algorithm for any xed tree T . We then go on to bound
the probability that s contains disjointly a given string decomposition of s.
Finally we show that when L x is normal and takes form T or has T as an
incubating subtree then s contains disjointly substrings that form one of the
string decompositions of T that are generated by the algorithm.
Let us now x a node x in D s
m and x T to be some given (b;
for some xed integers b; i and l. Furthermore, let us dene mapping from T
to a subgraph of the complete DeBruijn graph. We will name the root node
of T x and let us name all the nodes of the graph T , as follows. Now notice
that in our denition of (b; i; l)-trees that each node has at most  children
and we make a distinction between two based on a predened ordering of the
children, we can therefore talk about the k th child of a node, where k is some
number between 1 and , possibly greater than the number of x's children. If
z is the k th child of a node named y 1 and the
edge between them y 1 is the k th letter of the alphabet
.
The following algorithm generates a string decomposition of T .
Algorithm 2
Label T using the string requirement labeling of Def. 4.4
Preorder the nodes of T.
Initialize C as an empty collection.
While 9 e such that l(e) > 0
Let v be the lowest ordered node of T with a
positively labeled out-edge, e.
Choose y such that
While v is non-leaf
Choose e as one of the out-edges of v.
Append to y the character corresponding to e.
Add y to the collection C.
Return C.
We will rst upper bound the number of string decompositions generated
by this algorithm.
Lemma 4.4 The number of possible string decompositions generated by Algorithm
2 is bounded above by  R T 2i+1 , where i is the number of internal
non-branching nodes in T and R T is dened in Denition 4.4.
Proof: Let us count the number of choices made by the algorithm. Let v
be some branching node and k be the sum of the labels of v's out-edges.
Algorithm 2 will arrive at most k times at v. Whenever v is chosen in
the outer loop one of v's out-edge labels gets decreased by one. Since the
in-edge of v has label at most two we will arrive at most twice at v in the
inner loop. The rst time we arrive at v in the inner loop all out-edges of v
have positive labels and one of them will be decreased. The second time we
arrive at v in the inner loop we may choose an edge we have chosen before.
The last time we arrive at v in the outer loop we have no choice of which
edge to traverse. All other times we have some choice of edge to traverse,
the number of choices clearly being less than . When we arrive at a node
that has a single child we have no choice as to which edge to traverse next.
The number of string decompositions is therefore at most
where B is the set of branching nodes. The inequality can be veried by
noting that the labels of out-edges of nodes that have one child are always
two except in the case when the root has only one child.
We will now upper bound the probability of any string decomposition.
Lemma 4.5 If C is a collection of strings generated by Algorithm 2 then the
probability that the strings of C occur disjointly as substrings of s is upper
bounded by  l  R T , where
Proof: Let D be our set of strings. By Lemma 4.3 jDj  l. When originally
chosen each of the strings in D has length m 1. Furthermore we will append
to them at least R T extra characters. Note that the probability of a string
of length j occurring in s is at most n
. We then have that the probability
of all of the strings in D occurring in s is bounded by:
x2D
jxj   l  x2D  m 1jxj   l  R T
We now relate L x to the string s.
Lemma 4.6 If T is an incubating subtree of a normal L x then s contains
disjointly one of the collections generated by Algorithm 2.
Proof: Based on the actual string s we will show how the Algorithm 2 can
be made to construct a collection of disjoint substring s. By the denition
of normal, if T is an incubating subtree of L x and L x is normal and e is an
edge of T labeled k by Algorithm 2 then s must contain at least k disjoint
substrings corresponding to e. In the outer loop of Algorithm 2 we can hence
always choose y to be some substring of s disjoint from those previously
chosen. Now let s correspond to y. In the inner loop we make the
choice of e based on the next characters (s j+1 and onwards) of s, i.e. if s j+1
is k then e will be chosen as the k-th child of v. Since L x is normal the end
string will not occur in L x and the choice of the child is hence always well
dened. Since T is an incubating subtree of L x this choice will never return
an edge not in T and will terminate at a leaf node of T .
4.4 Number of normal queries
Combining the results of Lemmas 4.2, 4.4 and 4.5 gives the following lemma.
Lemma 4.7 The probability that L x contains a (b; i; l)-tree as an incubating
subtree is at
l  i+1
l and
Lemma 4.8 Let that m is large enough so that
e
< 1. Then the expected size of the set of queries QN added to Q
corresponding to normal strings x is bounded by
ne
Proof: We can estimate the expected number of queries by multiplying the
number of nodes x, in D s
m with the probability that L x has a (b;
as an incubating subtree and with the number of leaves l and then summing
over all (b;
notice that l  b + 1. To get the expected number
of queries in Q we multiply the number of nodes in D s
m with the sum over
all possible k's and i's of the number of queries added for each tree (b
multiplied with the probability of the tree over all possible k's and i's and
the number of ways to choose the initial node x.
E(jQN
1X
ne
The second inequality follows from a series of algebraic manipulations and
noting k
(e) k . The second equality is a well known identity for geometric
series. The rst equality is less well known but can be observed by
dierentiating the identity for geometric series k times (Slomson, 1991).
We have now shown that only O(n) queries are generated for nodes x in
the graph where L x is normal.
4.5 Remaining Cases
We will now show that it is unlikely that L x is not normal and then we can
use the fact that the maximum number of queries generated by the algorithm
with initial string corresponding to any given node in the graph is bounded
by
Let us introduce some terminology.
Denition 4.5 1. We say that a string,
2. The core of a string that corresponds to a node (node string)
is the substring of x that occurs as a substring in all node
strings of L x , i.e. x k 0
The cases when L x is not normal are when end occurs in L x , L x has a
cycle or the string decomposition of L x consists of strings that are non-disjoint
in s.
End will occur in L x for at most
x. The number
of queries containing the string corresponding to end as a substring is hence
bounded by O(n 2
As the depth of L x is bounded by k contains a cycle the
period of the cycle must also be bounded by k 0 + 1. The core of x must
therefore have period at most k occurs in all the node strings of
L x . If the core of x has period less than k call x a low-periodic
core string. To simplify presentation we will also consider strings which are
periodic with period less than d 1log  ne to be low-periodic core strings.
All extensions of a node string x will appear disjointly if the core of x does
not occur twice in s, starting at positions i and j, where ji jj  m+k 0 + 1.
Here m 1 is the length of the node strings in the current iteration of Step
the condition may therefore be rewritten as ji jj  O(log  n). If this
happens we say the core of x is self-repetitive.
To count the expected number of queries in Q we will consider four cases.
First we will count the expected number of queries stemming from strings
with a low-periodic core. Then the expected number of elongations of strings
with a self-repetitive core given that the core is not low-periodic. The remainder
of the strings are normal or have the terminal string of s occurring
in L x .
We will now count the number of queries in Q that originate at low-
periodic core strings. The number of node strings with a core of period k is
determined by the degrees of freedom outside the core (k 0 +1) plus the degrees
of freedom inside the core ( k) and is therefore  k 0 +k+1 . The number of
extensions of low-periodic core node string is hence at most
d 1log  ne
d 1log  ne+k+1 O(n 1
Now we look at the number of query strings originating at node strings
whose core is self-repetitive but not low-periodic. The expected number of
cores that are self-repetitive and not low-periodic is at most
(number of places i for the rst core to start)
(number of places for second core to start)
rst core)
which is bounded above by n  O(log  n)   d 1log  ne
log  n). The
expected number of strings with a self-repetitive core is hence bounded by
O(n 7
log  n). The expected number of queries added to Q in this case is
hence bounded by O(n 9
Using Lemma 4.8 have now shown Lemma 4.1. The expected number of
queries generated in Step 2 0 is bounded by
ne
4.6 Concentration of Expectation
We now use Azuma's inequality (see (Alon and Spencer, 1992)) to show that
with high probability Step 2 0 has only a linear number of queries.
Lemma 4.9 With high probability no more than O(n) queries are added to
Q in each iteration of Step 2 0 .
Proof:
We can view s to be a sequence of n independent random trials, one for
each of its characters. We want to bound the number of queries that may
be added to or removed from Q if we change one character. The changing
of one character may eect at most (m ne
5 log  n) strings, where m denotes the length of the node strings in the
current iteration of Step 2 0 . This can be seen by rst choosing the position
of the character change in the query string and noting that the length of
each query string is at most m c be the character that
was changed in s and let r m+2 r be the characters immediately
preceding and following c with q be a query string that is
aected by the character change and the length of q. The path in
m that q corresponds to must pass through one of the nodes corresponding
to substrings of length m 1 containing c. In particular if the character
change occurred in the jth position of q then if j  m 1, q has characters
positions the characters in
position can then be any character. If
in its rst positions
and the characters can be any character. In both cases there are
at most
strings that can be aected.
By Azuma's equality we have
5 log  n)) 2
Putting completes the proof.
Computational Results
The choice of k 0 as d 1log  ne in the previous section was done for ease of
presentation and may be chosen slightly larger to decrease the number of
rounds. To test the practicality of our method we implemented a variant of
the algorithm presented that is not as stringent as the algorithm analyzed
closer to the original algorithm with Step 2. In this variant,
we limited the length of the queries to the largest l such the total number of
queries in each round is limited to O(n), instead of limiting their length to a
xed k 0 . In other words Step 2 is modied to:
m is a line.
Let Q be the set of strings
v) l is chosen as large as possible with
Ask the queries in Q.
.

Table

1 shows the number of SBH chips used when the base pairs are
generated randomly. The number of query rounds is signicantly lower than
the number of rounds guaranteed by the worst-case performance guarantee of
the algorithm. We see that if we initially use a classical SBH chip containing
all oligonucleotides of size dlog 4 ne 1 we can nish the sequencing of the
DNA in less than 4n extra queries, using a single chip, for all of our examples.

Table

2 shows the number of SBH chips used to sequence arbitrarily
chosen virus sequences. For all but one of our examples our algorithm will
sequence their DNA by using the classical chip containing all strings of length
log then an extra round of at most 4n queries.
6

Acknowledgements

The authors would like to than R.Ravi, Magnus M. Halldorsson, Dan  iel F.
Gudbjartsson and the anonymous referees for reviewing this paper. Alan
M. Frieze was supported in part by NSF grant CCR9818411. Bjarni V.
Halldorsson was supported by a Merck Computational Biology and Chemistry
Program Graduate Fellowship from the Merck Company Foundation.



--R

The probabilistic method.
Poisson process approximation for sequence repeats
A novel method for nucleic acid sequence determination.
On the complexity of positional sequencing by hybridization
and Paterson
Synthetic DNA arrays.


Oligonucleotide arrays: New concepts and possibilities.

DNA sequnence determination by hybridization: A strategy for e-cien large scale sequencing
The probability of unique solutions of sequencing by hybridization.



Positional sequencing by hybridization.
The Art of Computer Programming: Fundamental Algo- rithms
Multistage sequencing by hybridization.
Expression monitoring by hybridization to high-density oligonucleotide arrays




Spectrum alignment: E-cient resequencing by hybridization
Towards DNA-sequencing by hybridiza- tion
Improved chips for sequencing by hybridization.
Journal of Biomolecular Structure and Dynamics
Optimal reconstruction of a sequence from its probes.

DNA Microarrays.
Large scale sequencing by hybridization
Reconstructing strings from substrings.
Journal of Computational Biology

DNA chips: analyzing sequence by hybridization to oligonucleotides on a large scale.


--TR
The art of computer programming, volume 1 (3rd ed.)
Sequencing-by-hybridization at the information-theory bound
Towards DNA Sequencing Chips
Reconstructing strings from substrings in rounds

--CTR
Steven Skiena , Sagi Snir, Restricting SBH ambiguity via restriction enzymes, Discrete Applied Mathematics, v.155 n.6-7, p.857-867, April, 2007
Eran Halperin , Shay Halperin , Tzvika Hartman , Ron Shamir, Handling long targets and errors in sequencing by hybridization, Proceedings of the sixth annual international conference on Computational biology, p.176-185, April 18-21, 2002, Washington, DC, USA
sequencing by hybridization;probabilistic analysis;DNA sequencing