Algorithmic methods in genetic mapping
Daniel G. Brown, David B. Schmoys · 2000
We design new algorithms for genetic linkage mapping projects. Mapping projects are very expensive procedures by which biologists approximately locate a large number of landmarks on an organism's genome. We show that their cost can be greatly reduced with minimal reduction in precision by performing most laboratory work on a subset of an experimental population that is well chosen. Our algorithms for this sample selection problem are based on a collection of models of increasing realism; the most abstract problem is a variant on the well-known k-center problem, while the most complicated incorporates the uncertainty and error common in real biological data. All of the problems that we study are NP-hard to approximate to within a factor of any polynomial in the size of the population, so we study heuristics for the problem that perform well in practice, based on mathematical programming and randomized rounding, local search, and greedy techniques. We show that an experimenter can cut a population (and, essentially, the experimental cost of mapping) in half with a reduction of only 10% in mapping accuracy; alternatively, one may perform the same amount of work as before with a significant improvement in accuracy. We also develop new algorithms for the analysis of genetic mapping data; while developed specifically for use with selected samples, our techniques are globally useful and 20% more precise than the previous standard techniques for this analysis. Our methods scale much better than previous ones, are robust under noisy data, and are easy to understand. Finally, to justify the very good performance of our sample selection algorithms, we analyze the probabilistic performance of one of our algorithms, under a highly abstract data model. In contrast with naive techniques, which have expected performance that is a logarithmic factor from optimal, our greedy algorithms are shown to have performance that converges to a factor of 2 of a trivial lower bound, and we show that the convergence to this bound is extremely fast.