Selective Mapping: A discrete optimization approach to selecting a population subset for use in a high-density genetic mapping project

摘要

We study the problem of sampling from a large genetic mapping population in which all individuals have identical pedigrees. We show that samples obtained from large populations, selected on the basis of limited genetic data, are better studied for use in high-density mapping experiments than random samples of the same size. We model the problem of choosing a mapping sample as a discrete stochastic optimization problem, related to existing clustering problems, and study various heuristics for the problem, including some randomized rounding algorithms. Experiments on both simulated data and ten data sets from biological populations show that these heuristics perform very well in practice despite the problem being NP-hard to approximate to within any constant. Our proposals offer the possibility of higher resolution, less expensive genetic maps.