Page 246 - Applied Probability

11. Radiation Hybrid Mapping
the hybrid clone; a “0” indicates that the locus was absent; and a “?” in-
dicates that the locus was untyped in the clone or gave conflicting typing
results.
11.3 Minimum Obligate Breaks Criterion 233

Computing the minimum number of obligate breaks per order allows com-
parisons of different orders [3, 4, 5, 23]. If the order of the loci along the
chromosome is the same as the scoring order, then the clone described in
the last section requires three obligate breaks. These breaks occur when-
ever a run of 0’s is broken by a 1 or vice versa; untyped loci are ignored
in this accounting. The minimum number of obligate breaks for each clone
can be summed over all clones to give a grand sum for a given order. This
grand sum serves as a criterion for comparing orders. The minimum breaks
criterion can be minimized over orders by a stepwise algorithm [5] or by
standard combinatorial optimization techniques such as branch-and-bound
[19] and simulated annealing [17].
The advantage of the minimum breaks criterion is that it depends on al-
most no assumptions about how breaks occur and fragments are retained.
Given a common retention rate, this criterion is also strongly statistically
consistent. Following Barrett [1] and Speed et al. [20], let us demonstrate
this fact. Consider m loci taken in their natural order 1,... ,m along a
chromosome, and imagine an infinite number of independent, fully-typed
radiation hybrid clones at these loci. Let B i (σ) be the random number of
obligate breaks occurring in the ith clone when the loci are ordered accord-
ing to the permutation σ. In general, a permutation can be represented as
an m-vector (σ(1),...,σ(m)). Ambiguity about the left-to-right orienta-
tion of the loci can be avoided by confining our attention to permutations
σ with σ(1) <σ(m). The correct order is given by the identity permutation
id.
Given n clones, the best order is identified by the permutation giving
n
the smallest sum S n (σ)= B i (σ). Consistency requires that S n (id)
i=1
be the smallest sum for n large enough. Now the law of large numbers
1
indicates that lim n→∞ S n (σ)= E[B 1 (σ)] with probability 1. Thus to
n
demonstrate consistency, it suffices to show that the expected number of
breaks E[B 1 (id)] under id is strictly smaller than the expected number of
breaks E[B 1 (σ)] under any other permutation σ.
To compute E[B 1 (id)], note that the interval separating loci i and i +1
manifests an obligate break if and only if there is a break between the two
loci and one locus is retained while the other locus is lost. This event occurs
with probability 2r(1 − r)θ i,i+1 , where r is the retention probability and