The analysis of Range Quickselect and related problems.

Range Quickselect, a simple modification of the well-known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Range Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.The key element appearing in the analysis of Range Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us.In particular, we have been able to carry out a precise analysis of the expected number of moves of the pth element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results.Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

Evaluating differences in linkage disequilibrium between populations.

We propose two methods to evaluate the statistical significance of differences in linkage disequilibrium (LD) between populations, where LD is measured by the standardised parameter D'. The first method is based on bootstrapping individuals within populations in order to test LD differences for each pair of loci. Using this approach we propose a solution to the problem of testing multiple locus-pairs by means of a single test for the number of pairs that exhibit significant LD differences among populations. The second method provides the Bayesian posterior probability that one population has greater LD than the other for each locus pair. Both methods can handle genotypes with unknown phase, and are demonstrated using two data sets. For the purpose of demonstration, we apply the methods to two different sets of data from humans. First, we explore the issue of LD differences between reproductively isolated populations using a new data set of twelve Xq25 microsatellites, typed in four European populations. Second, we examine evidence for LD differences between Alzheimer cases and controls from the Icelandic population using 19 single nucleotide polymorphisms (SNPs) from a 97 kb region flanking the Apolipoprotein E (APOE) gene on chromosome 19.