Improved Recombination Lower Bounds for Haplotype Data

摘要

Recombination is an important evolutionary mechanism responsible for the genetic diversity in humans and other organisms. Recently, there has been extensive research on understanding the fine scale variation in recombination rates across the human genome using DNA polymorphism data. A combinatorial approach toward this is to estimate the minimum number of recombination events in any history of the sample. Recently, Myers and Griffiths proposed two measures, R_h and R_s, that give lower bounds on the minimum number of recombination events. In this paper, we provide new and improved methods (both in terms of running time and ability to detect past recombination events) for computing recombination lower bounds. Our principal results include: 1. We show that computing the lower bound Rh is NP-hard and adapt the greedy algorithm for the set cover problem to obtain a polynomial time algorithm for computing a diversity based bound R_g. This algorithm is several orders of magnitude faster than the Recmin program and the bound R_g matches the bound R_h almost always. 2. We also show that computing the lower bound R_s is also NP-hard using a reduction from MAX-2SAT. We give a O(m2~n) time algorithm for computing R_s for a dataset with n haplotypes and m SNP's. We propose a new bound R_I which extends the history based bound R_s using the notion of intermediate haplotypes. This bound detects more recombination events than both R_h and R_s bounds on many real datasets. 3. We extend our algorithms for computing R_g and R_s to obtain lower bounds for haplotypes with missing data. These methods can detect more recombination events for the LPL dataset than previous bounds and provide stronger evidence for the presence of a recombination hotspot. 4. We apply our lower bounds to a real dataset and demonstrate that these can provide a good indication for the presence and the location of recombination hotspots.