Reconstructing distances in physical maps of chromosomes with nonoverlapping probes.
We present a new method for reconstructing the distances between probes in physical maps of chromosomes constructed by hybridizing pairs of clones under the so-called sampling-without-replacement protocol. In this protocol, which is simple, inexpensive, and has been used to successfully map several organisms, equal-length clones are hybridized against a clone-subset called the probes. The probes are chosen by a sequential process that is designed to generate a pairwise-nonoverlapping subset of the clones. We derive a likelihood function on probe spacings and orders for this protocol under a natural model of hybridization error, and describe how to reconstruct the most likely spacing for a given order under this objective using continuous optimization. The approach is tested on simulated data and real data from chromosome VI of Aspergillus nidulans. On simulated data we recover the true order and close to the true spacing; on the real data, for which the true order and spacing is unknown, we recover a probe order differing significantly from the published one. To our knowledge this is the first practical approach for computing a globally-optimal maximum-likelihood reconstruction of interprobe distances from clone-probe hybridization data.
Introduction
Physical mapping in molecular biology is the task of reconstructing
the order and location of features of biological
interest along a chromosome. The features may be
Corresponding author. Department of Computer Science, University
of Georgia, Athens, GA 30602-7404. Email: kece@cs.uga.edu.
Research supported by National Science Foundation CAREER Award
DBI-9722339.
y Department of Statistics, University of Georgia, Athens, GA
30602. Email: sanjay@stat.uga.edu
z Department of Genetics, University of Georgia, Athens, GA
30602. Email: arnold@genetics.uga.edu
sites at which restriction enzymes cut, so-called sequence-
tagged sites that are identified by short, uniquely-occurring
sequences, or positions of clones that contain fragments of
the chromosome. There is a diverse array of approaches for
constructing maps of such features depending on the type
of data that is collected, including mapping by nonunique
probes [2, 18], mapping by unique probes [1, 11, 12], mapping
by unique endprobes [7], mapping by nonoverlapping
probes [8], mapping from restriction-fragment length
data [10, 13], radiation-hybrid mapping [24, 5], and optical
mapping [21, 14, 16]; there are many probabilistic analyses
of various approaches [15, 4, 28, 27, 26]; and a wide
variety of computational techniques have been employed or
suggested, including greedy algorithms [18], simulated annealing
[20, 25, 2, 1], linear programming [7, 12, 8], and
semidefinite programming [6].
In this paper we develop a maximum-likelihood approach
for a type of physical mapping known as the sampling-
without-replacement protocol. The protocol is inexpen-
sive, simple to carry out in the lab, and uses widely-available
technology. Organisms that have been mapped
with this technique include Schizosaccharomyces pombe [19],
Aspergillus nidulans [22], and Pneumocystis carinii [3];
mapping projects in progress using the technique include
Neurospora crassa and Aspergillus flavus.
In the protocol, a library L consisting of many overlapping
clones that each sample a fragment of the chromosome
is developed. Clones in L are size-selected to have a target
length, and are arrayed on a plate. A subset of the clones
called the probe set P is then obtained by the following sequential
process. Initially, L. At the ith
iteration of the process, choose a clone P i from S at random,
remove P i from S, and add it to P. Hybridize P i against
all the clones in the library by extracting complementary
DNA from both of its ends and washing the DNA over the
arrayed plate, recording all clones in the library to which the
DNA sticks. Remove from S all clones in the library that
have a positive hybridization result with P i . Then repeat
this process for the next iteration, stopping once S becomes
empty.
We call the final set P the probe set, and the set
the clone set. The results of the experiments are summarized
in a probe-clone hybridization matrix H that records the
outcomes of all hybridizations between the probes in P and
the clones in C.
Notice that if a clone C overlaps with a probe
P in the chromosome, it must overlap with one of the ends
of P j , as all probes and clones are of the same length. Such
an overlap corresponds to a portion of DNA that is in common
between the clone and the end of the probe. In the absence
of error, the complementary DNA from the end of P j
will stick to C i , and the hybridization test of P j versus C i
will be a positive result; thus clone C i will be removed from
set S at the jth iteration. This implies that in the absence
of error the probe set P is a maximal nonoverlapping subset
of the library.
Suppose that in hybridization matrix H enough of the
clone-probe overlap structure is represented that we can recover
the order of the probes P across the chromosome.
Then for every consecutive pair of probes P and Q in this or-
der, we can examine H for the presence of a linking clone C
that overlaps with both P and Q. The probe set P together
with a linking clone for every consecutive pair forms a minimal
set of clones that cover the chromosome. A map giving
the order of the probes across the chromosome is then very
useful, since by individually sequencing just the probes and
linking clones and overlapping the sequences in the order
given by the map, we can reconstruct the DNA sequence of
the chromosome.
In reality, hybridization tests do not perfectly record the
overlap structure of probes and clones. Hybridization results
contain random false positives and false negatives. A
probe can also hybridize to a nonoverlapping clone due to
repeated DNA in the chromosome. In general, clones can
be chimeric, which means they sample two or more fragments
of the chromosome, and can contain deletions, which
happens when portions of the DNA get spliced out during
cloning. In the mapping projects using this protocol at the
University of Georgia, however, clones are produced by cos-
mids, which are small enough that chimerism and deletions
are not a significant problem. In our treatment we model
false positives and false negatives, but not chimerism, dele-
tions, or repeats. Hence false hybridizations due to repeats
are treated as a series of isolated false positives.
Related work Prior work on mapping by the sampling-
without-replacement protocol, by Cuticchia, Arnold and
Timberlake [9], Wang, Prade, Griffith, Timberlake and
Arnold [25], and Mott, Grigoriev, Maier, Hoheisel and
Lehrach [20], has largely used local-search heuristics such as
simulated annealing to try to find a probe order that minimizes
the Hamming-distance traveling-salesman objective.
While minimizing this objective is not known to optimize
any natural measure of the goodness of a map, Xiong, Chen,
Prade, Wang, Griffith, Timberlake and Arnold [27] have
shown that under certain assumptions on the distribution
of clones, the Hamming-distance objective is statistically
consistent; this means that as the number of clones goes
to infinity, an exact algorithm for the Hamming-distance
traveling salesman problem would recover the correct probe
order with probability one.
Christof and Kececioglu [8] recently showed that the
problem of computing a maximum-likehood probe order in
the sampling-without-replacement protocol in the presence
of false-positive and -negative hybridization error can be reduced
to the problem of finding the minimum number of
ones to change to zeroes in hybridization matrix H so that
the resulting matrix H 0 has at most 2 ones per row and
the consecutive-ones property on rows. They then showed
how to formulate this problem as an integer linear program,
and developed a branch-and-cut algorithm for computing
an optimal maximum-likelihood probe order. Using this ap-
proach, they were able to compute optimal probe orders for
realistic-sized instances on simulated data, and probe orders
with significantly fewer false positives on real data than
the best-possible map obtainable by a Hamming-distance
traveling-salesman approach. In this paper we complement
the work in [8] by developing a practical method for computing
a globally-optimal maximum-likelihood reconstruction
of the interprobe distances, given a probe order.
Plan of the paper In the next section we give a maximum
likelihood formulation of the problem of mapping by
the sampling-without-replacement protocol in the presence
of false positive and false negative error, which we call Mapping
by Nonoverlapping Probes. The problem is unique in
that the goal is to reconstruct the most likely order and spacing
of probes along the map from the hybridization data.
Section 3 then derives the likelihood function on probe orders
and spacings for this formulation, which has a remarkably
simple closed form. Section 4 explains how we tackle
the maximization of this function for a fixed probe order
using continuous optimization. Section 5 presents results
of some experiments with a preliminary implementation of
this approach. We then conclude with several directions for
further research.
2 The problem
In our maximum likelihood formulation we do not model
the sequential process of choosing the probes, and hence
we operate under the assumption that the probes form a
nonoverlapping set. We write fP1 Png for the set of
for the set of m clones, and we
formulate the problem as follows.
The task is to recover the probe order
and the probe spacing as illustrated in

Figure

1, given the m \Theta n clone-probe hybridization matrix
containing false positive and false negative errors.
Permutation - gives the names of the probes in left-to-right
order across the chromosome. Vector x gives the distance
beween consecutive probes, where component x j is the distance
between the left end of P- j and the right end of P- j\Gamma1 .
Matrix is a 0-1 matrix, with
ae
hybridizes to C
0; otherwise:
We assume that all clones are the same length, that the
probes are nonoverlapping, and that we know
ffl L, the length of the chromosome,
ffl ', the length of a clone,
ffl ae, the probablility that an entry of H has been
corrupted into a false positive, and
ffl j, the probability that an entry of H is a false negative

As stated, this is not a well-posed problem. In the
presence of false positives and negatives, any permutation
- of ng and any positive vector x for which
are an explanation of the data. To obtain
a well-defined problem, we invoke the principle of maximum
likelihood, which says that the best reconstructed map
is that - and x that are most likely to have given rise to H.
If we write p(-; x the probability that - and x are
the true order and spacing given the observed matrix H,
a maximum likelihood reconstruction is a pair (-   ; x   ) that
maximizes p(-; x j H). We take the following as our definition
of the problem.
(Mapping by Nonoverlapping Probes)
The Mapping by Nonoverlapping Probes Problem is the fol-
lowing. The input is the clone-probe hybridization matrix
H, the chromosome length L, the clone length ', the
false positive probability ae, and the false negative probability
j. The output is a probe order and probe spacing
pair (-; x) that maximize p(-; x under the assumption
that the probes are a collection of nonoverlapping clones, all
clones are of equal length, that the left ends of clones are
uniformly distributed across the chromosome, and that the
entries of H have been independently corrupted with false
positive probability ae and false negative probability j. 2
We can derive the function p(-; x using Bayes' theorem

In this equation, p(H j -; x) is the probability of observing
H given that - and x are the true order and spac-
ing, p(-; x) is the probability that - and x occur in na-
ture, and p(H) is the probability of observing H. 1 Since
e-
ex p(H j e-; e x) p(e-; ex)dex, the denominator is a
constant independent of - and x and can be ignored. Since
the names given to probes and the spaces between probes
are independent, p(-; names are assigned
to probes completely randomly,
is independent of - and can also be ignored. Thus the only
relevant quantities are p(H j -; x) and p(x).
If the probability density function p(x) on probe spacings
is uniform, this factor can be ignored as well. For the
model considered below, we do not yet know the density
function p(x), but it does not appear to be uniform. We
concentrate instead on deriving the function p(H j -; x),
and take maximizing it as our objective. This will differ
from truly maximizing p(-; x according to the bias due
to p(x).
We next derive function p(H j -; x) under the simplest
process by which H can be generated from - and x
with false positives and negatives. This process has three
stages:
(1) each clone is thrown down uniformly and independently
across the chromosome,
(2) for the row of the hybridization matrix corresponding
to a given clone, the probes that a clone
overlaps get a one in their column, and zeros are
placed everywhere else, and
(3) the ones and zeros are corrupted randomly and
independently with probability j and ae respectively

3 The objective function
To derive p(H j -; x) under this model, notice that each row
of H is independent of the other rows, since each clone is
thrown down independently and each entry is independently
corrupted. Writing H i for the ith row of H then, it suffices
are values taken on by underlying random
variables \Pi and X, when we write p(-; x) this is shorthand
for x). Furthermore, since - is a discrete variable while
x is a continuous variable, when we write p(-; x) this is the joint probability
density function of a discrete and a continuous random variable
evaluated at - and x.
to work out p(H i j -; x), since
Y
1-i-m
To derive p(H i j -; x), notice that in the absence of error
there are only three possible types of overlaps that can occur
with a given clone C i as illustrated in Figure 2:
(1) Clone C i overlaps with no probe. If the left end
of clone C i falls between the left ends of probes
P- overlaps with neither P- j
nor P-
. (If C i falls to the
left of P- 1 but does not overlap with it, we write
1 , and if C i falls to the right of P-n but
does not overlap with it, we write C i 2 N -
.)
(2) Clone C i overlaps with exactly one probe. If it
overlaps with only probe P- j
, we write C
.
overlaps with exactly two probes. If
it overlaps with both probe P- j and P- j+1 , we
.
In

Appendix

A, we derive p(H i j -; x) by summing over
the disjoint events C i 2 N -
j . For
here, note that the domain S of the probe order permutation
- is the set of all permutations on f1; and the
domain D ' R n of the spacing vector x is the set
1-i-n
We summarize the derivation in the following theorem.
Theorem 1 (Objective function) For hybridization matrix
1-i-m
a -
where the coefficients a -
ij are given by Equations
(2) through (5) in the Appendix, and we define
1-i-n
Then for a fixed probe order -,
where D is given by Equation (1). 2
In other words, if we can evaluate the following objective
function on permutations,
(and recover the minimizing x for a given -), we can reduce
the continuous problem of maximizing p(H j -; x) to a discrete
search for a permutation that minimizes g(-). 2 We
now describe how we tackle the evaluation of g(-).
2 Note that this does not solve the problem of finding a pair (-; x)
that maximizes p(-; x j H): the objective f(-; x) is missing a term
of \Gamma ln p(x), as we do not know the density function p(x).

Figure

1 The problem is to reconstruct the probe order permutation and the probe spacing vector
from the clone-probe hybridization matrix H. The probe set fP1 ; Png is chosen to form a non-overlapping
subset of the clones. Clones are size-selected to have the same length.
(a)
(b)
(c)

Figure

2 The three possible types of clone-probe overlaps. (a) C i 2 N -
.
4 Evaluating the objective for a fixed permutation
In this section, for a fixed - let us we write f(x) for f(-; x),
and define
Then
1-i-m
Below we show that f is convex in certain convex regions
of D, so that a greedy procedure such as gradient descent
will find the global minimum of f in such a region. We
describe how we choose these regions of D, and then explain
how to find the direction of greatest decrease in f in such
a constrained region for the gradient descent procedure. A
very readable summary of the facts from optimization that
we use is given by Lengauer [17].
4.1 Convexity
Recall that a set C ' R n is a convex set if for all points p
and q in C and all 0 - 1, the point -p + (1\Gamma-)q is in C.
A function R defined on a convex set C is a convex
function if for all points p and q in C and all 0 - 1,
Informally, a convex function is bowl-shaped.
Let us call a region C ' D good if for all points x 2 C
and all 1 defined as in
Theorem 1. The relevance of good regions is that they are
the regions throughout which f(x) is differentiable.
In a good region C consider all points
which is the ray traced by moving from point p 2 C in
direction Along such a ray the derivative
of f is well-defined and is equal to
d
ds
d
ds
where
d
ds
1-j-n
and where u(\Delta) denotes a unit step function at ':
Taking a second derivative along the ray yields
ds
so that
ds
1-i-m
d
ds f i (x)
0:
This implies that in every convex region C ' D that is good,
function f is convex.
A key property of convex functions is that a local minimum
of a convex function f in a convex set C is a global
minimum of f on C [17]. Thus if we can divide D into a
small number of good convex regions, it suffices to apply in
each region an algorithm that is only guaranteed to find a
local minimum; the best of these local minima is the global
minimum of f over the regions.
and consider the four regions D+1+1 ,
D \Gamma1\Gamma1 . These regions correspond to constraining all interior
distances between probes to be at most ', and then
forcing the exterior distances x1 and xn+1 to be on one side
of '. Each region is an intersection of halfspaces, and hence
is a convex set. The interior of each is a good region, and
for any ray originating in the interior we can make the appropriate
choice for the derivative at the boundary so that
the derivative along the ray is continuous throughout the
region. Thus we can find the global minimum in each of
these four regions by gradient descent as described below.
This does not necessarily find the global minimum of f
on D. However, notice that for our function f , if a spacing
vector x is modified by trading distance between two components
in such a way that both remain
at least ', the value of f is unchanged. Suppose then that
the global optimum x   over D has x
and x
component. By shrinking x
i to '
while stretching the larger of x
1 or x
n+1 , we can eventually
transform x   into a point in one of the four regions without
changing its value under f . Thus the best of the minima of
the four regions, call it ex, is not a global minimum over D
only if for all global minima x   over D, x
and in some other component x
stretching x
1 or x
n+1 as before shows that suboptimality
of ex is due only to error in ex 1 or ex n+1 . However, as there
are no linking clones by which to estimate e x1 and ex n+1 , the
hybridization data provides no direct information by which
to reconstruct these two exterior distances, and their estimates
should be regarded with suspicion in any reconstruc-
tion. Thus, if the biologist interprets the output e
x with the
understanding that when ex some component, this
distance may exceed ' in the true map, and that e x1 and ex n+1
may be inaccurate, then reporting the global optimum ex of
the four regions is reasonable.
4.2 Gradient descent
The gradient of f at point p is the vector
grad f(p) :=
@xn f(p)
where the kth component of the gradient is the partial
derivative of f with respect to xk evaluated at
@
where u(\Delta) is the unit step function defined before and pn+1
is defined in the same way as xn+1 . A basic fact in multivariable
calculus is that the direction of greatest decrease
of f at p is
The procedure known as gradient descent [23] starts from
a point p, computes the negative gradient direction v at p,
moves to the point p 0 that minimizes f along the ray p+sv,
and repeats, stopping once a point is reached at which the
gradient vanishes. In the unconstrained problem of minimizing
f over R n , such a point is a local minimum, and
since f is convex, when gradient descent halts it has found
a global minimum of the unconstrained problem.
For the constrained problem, however, of minimizing f
over a region C ' R n , the negative gradient direction v at a
point p on the boundary of C may be directed outside C, in
which case we cannot move along v, yet another direction v 0
at p that is directed inside C may exist along which f de-
creases, albeit at a slower rate. Let us call a direction v at a
point it is possible move along v from p and
remain in C. In general, the feasible direction v of greatest
decrease in f at a point p can be found as follows.
The boundaries of a region are given by constraints
that are hyperplanes. At point the
negative gradient direction
which of the bounding hyperplanes are tight. Let the list of
tight hyperplanes for which v points outside the halfspace
given by the hyperplane be H1 , ., Hk . Take v
and successively project v (0) onto H1 to obtain v (1) , then
project v (1) onto H2 to obtain v (2) , and so on. The vector
resulting from the final projection onto Hk is the
feasible direction of greatest decrease at p. If v
then p is a local minimum of f in C.
Given the feasible direction v of greatest decrease, we
compute the largest value t ? 0 for which
As f is convex, the one-dimensional problem of minimizing f
along p+ sv for s 2 [0; t] can be solved by a form of binary
search known as bisection [23].
This completes the description of our approach to evaluating
g(-). Over each of the four regions
we compute a global minimum by constrained gradient descent
using bisection, and take the best of the four minima.
Computing the gradient at a given point takes time \Theta(mn),
which dominates the time to find the best feasible direction
by successive projection, and is also the time to compute
derivatives at each step during bisection. As reaching a local
minimum can involve several gradient descent iterations,
and each iteration can involve several bisection steps, the
entire procedure is expensive. To find a good - we use the
local-search heuristic known as simulated annealing, calling
the above procedure to evaluate g(-) on each candidate
probe order.
5 Preliminary results
We now present some very preliminary results with an
implementation of this approach written by the second author

In the first experiments we ran the implementation
on simulated data. For our parameters we picked values
identical to those for chromosome VI of the fungus
Aspergillus nidulans, which has been mapped using the
sampling-without-replacement protocol [22]. This involved
clone length of
and a chromosome length of which corresponds
to a coverage of nearly 13. A false positive and false negative
probability of were used, which are
the estimated error rates for the mapping project. Clones
were thrown at random across the chromosome with the uniform
distribution, a probe set of nonoverlapping clones was
chosen, and the corresponding hybridization matrix H with
false positives and false negatives was generated.
We first tested how well the approach recovered the true
spacing, which was known for the simulated data, by running
the constrained gradient descent procedure with the
true probe order -. This is summarized in Table 1 for the
gradient descent started from a completely uniform initial
spacing, and an initial spacing obtained by a linear programming
approximation (which will be described in the full pa-
per). The hope was that a more sophisticated method for
choosing an initial spacing would lead to faster convergence
to a local minimum. As Table 1 shows, this was not the
case. Starting from a uniform spacing took fewer iterations
of gradient descent, and fewer total bisection steps. It is
interesting that both approaches found a final spacing with
better likelihood than the true spacing, which had a value
of 6649.32.
As a measure of the error between the true spacing
and the computed spacings, we used the root-mean-square
error (RMS). Interestingly, the linear programming spacing
had greater initial error because the two exterior distances
x1 and xn+1 were not well-estimated from the hybridization
data, and the uniform spacing happened to give
better estimates for these exterior distances. The computation
time using either initial spacing was around 5 minutes
on a Sun UltraSPARC 1 with a 167 MHz chip. The final
RMS error of 3.7 kb is roughly 9% of the clone length.
Clearly there is a limit to the accuracy to which one
can recover the true spacing from the discrete data of a hybridization
matrix, which is essentially giving counts of linking
clones. We can show that every method of recovering
spacings must in the worst case have a root-mean-square error
of at least
'). For the above data, ffl - 6:2 kb.
In comparison, the final error in Table 1 is around 60% of
this worst-case lower bound.
Next we tested how well the simulated annealing approach
combined with this procedure for evaluating f recovered
the true probe order. We started from an initial -
obtained by a greedy heuristic for the Hamming-distance
traveling salesman objective. This initial - had 6 break-points
with respect to the true -, and an initial likelihood
of 6728.45. After about 12 hours on the above machine the
simulated annealing procedure halted with a final - equal
to the true order, with a final likelihood of 6470.52.
In the second experiments we ran the implementation on
real mapping data from chromosome VI of Aspergillus nidu-
lans, which took around 12 hours on the above machine.
The computed probe order had 36 breakpoints with respect
to the published order [22], which was obtained using simulated
annealing on the Hamming-distance traveling salesman
objective [25]. While our computed order clearly had
little in common with the published order, for this mapping
data the true order is not known.
6 Conclusion
We have presented a new maximum-likelihood approach for
reconstructing the distances between probes for physical
maps constructed by hybridizing equal-sized clones against
a nonoverlapping clone-subset. This protocol has been used
to successfully map several organisms, and yields a model
whose likelihood function is sufficiently simple to permit a
closed-form expression. The resulting formulation gives to
our knowledge the first practical method for physical mapping
from hybridization data that can reconstruct globally-
optimal maximum-likelihood distances along maps.

Table

1 Recovering the spacing on data simulating chromosome VI of Aspergillus nidulans.
LP-based initial spacing Uniform initial spacing
Bisection steps 185 177
Gradient descent iterations 149 101
Initial RMS error 6.65 kb 5.66 kb
Final RMS error 3.78 kb 3.69 kb
Final likelihood 6610.41 6610.53
Further research Finding a provably optimal - under
the objective appears formidable
given that f is nonlinear, while attempting to find a
good - through simulated annealing started from a random
appears slow given that g(-) is expensive to eval-
uate. The following two-stage approach may be effective,
however:
(1) Use a combinatorial approach with guaranteed
performance to find an initial e- that optimizes a
simpler linear combinatorial objective eg(-).
(2) Polish e- under the original nonlinear objective g
by local search to obtain a final -   and spacing
x   .
For example, eg could be the combinatorial 2-consecutive-
ones objective of Christof and Kececioglu [8], which corresponds
to the same likelihood model but without probe
spacings. In fact, if eg is sufficiently accurate to recover an
acceptable e-, one might use the original objective f to simply
recover the best spacing for e-. We suspect that the
full f is not needed to recover the true probe order in prac-
tice, and that the real utility of our likelihood function f
will be to infer probe spacings for probe orders computed
by combinatorial methods.
The numerical techniques we used to compute x   2
argmin x2D f(-; x), namely gradient descent with bisection,
are elementary, and it would be interesting to investigate
whether convergence to x   can be sped up by more sophisticated
numerical techniques.
In taking f(-; x) as our objective, which is equivalent
to maximizing p(H j -; x), not p(-; x j H), we are implicitly
assuming that the a priori probability density function
on probe spacings, p(x), is uniform. Unfortunately, even
when the distribution of the left ends of clones is uniform,
the density function on probe spacings is not. It would be
interesting to work out the a priori probe spacing density
function under a natural model of clone placement (which
appears to be involved), and investigate whether its inclusion
in the likelihood objective improves recovery of the true
spacing.
Finally, a significant source of error not considered in
our model is repeated DNA. When the chromosome contains
a repeat R that happens to occur at the end of a
probe P , the probe will have a false-positive hybridization
with every clone that does not overlap P but contains the
same repeat R. Examination of the hybridization matrix for
chromosome VI of Aspergillus nidulans shows that the false
positives do not appear to occur completely independently
across the matrix, but appear to occur more frequently in
certain columns. This suggests that repeats may be present.
How to best incorporate repeats into the maximum likelihood
objective is an interesting open problem, as it is not
clear how to appropriately model both the number of repeat
families and the number of copies in a family.



--R

"Physical mapping of chromosomes using unique probes."
"Physical mapping of chromosomes: A combinatorial problem in molecular biology."
"Constructing a physical map of the Pneumocystis genome."
"Genomic mapping by anchoring random clones: A mathematical analysis."
"On constructing radiation hybrid maps."
"A geometric approach to be- tweenness."
"A branch-and-cut approach to physical mapping of chromosomes by unique end-probes."
"Computing physical maps of chromosomes with nonoverlapping probes by branch-and-cut."
"The use of simulated annealing in chromosome reconstruction experiments based on binary scoring."
"An algorithmic approach to multiple complete digest mapping."
"Physical mapping by STS hybridization: Algorithmic strategies and the challenge of software evaluation."
"Algorithms for computing and integrating physical maps using unique probes."
"Mapping clones with a given ordering or interleaving."
"Algorithms for optical mapping."
"Genomic mapping by fingerprinting random clones: A mathematical anal- ysis."
"Estima- tion for restriction sites observed by optical mapping using reversible-jump Markov chain Monte Carlo."
Combinatorial Algorithms for Integrated Circuit Layout.
"Construction of physical maps from oligonucleotide fingerprint data."
"A 13 kb resolution cosmid map of the 14 Mb fission yeast genome by nonrandom sequence-tagged site mapping."
"Algorithms and software tools for ordering clone libraries: Application to the mapping of the genome Schizosaccharomyces pombe."
"Towards constructing physical maps by optical mapping: An effective, simple, combinatorial approach."
"In vitro reconstruction of the Aspergillus nidulans genome."
Numerical Recipes in C.
"Building human genome maps with radiation hy- brids."
"A fast random cost algorithm for physical mapping."
"Be- yond islands: Runs in clone-probe matrices."
"On the consistency of a physical mapping method to reconstruct a chromosome in vitro."
"Genome mapping by nonrandom anchoring: A discrete theoretical analy- sis."

--TR
Combinatorial algorithms for integrated circuit layout
On constructing radiation hybrid maps (extended abstract)
An algorithmic approach to multiple complete digest mapping
Algorithms for computing and integrating physical maps using unique probes
Towards constructing physical maps by optical mapping (extended abstract)
Building human genome maps with radiation hybrids
Beyond islands (extended abstract)
Algorithms for optical mapping
Estimation for restriction sites observed by optical mapping using reversible-jump Markov chain Monte Carlo
Computing physical maps of chromosomes with nonoverlapping probes by branch-and-cut
Construction of physical maps from oligonucleotide fingerprints data
Mapping clones with a given ordering or interleaving
Physical mapping of chromosomes using unique probes
A Geometric Approach to Betweenness
maximum likelihood;physical mapping of chromosomes;sampling without replacement protocol;convex optimization;computational biology