The number of recombination events in a sample history: Conflict graph and lower bounds

We consider the following problem: Given a set of binary sequences, determine lower bounds on the minimum number of recombinations required to explain the history of the sample, under the infinite-sites model of mutation. The problem has implications for finding recombination hotspots and for the Ancestral Recombination Graph reconstruction problem [29]. Hudson and Kaplan [15] gave a lower bound based on the four-gamete test. In practice, their bound R-m often greatly underestimates the minimum number of recombinations. The problem was recently revisited by Myers and Griffiths [22], who introduced two new lower bounds R-h and R-s which are provably better, and also yield good bounds in practice. However, the worst-case complexities of their procedures for computing R-h and R-s are exponential and super-exponential, respectively. In this paper, we show that the number of nontrivial connected components, R-c, in the conflict graph [4] for a given set of sequences, computable in time O(nm(2)), is also a lower bound on the minimum number of recombination events. We show that in many cases, R-c is a better bound than R-h. The conflict graph was used by Gusfield et al. [4] to obtain a polynomial time algorithm for the galled tree problem, which is a special case of the Ancestral Recombination Graph (ARG) reconstruction problem. Our results also offer some insight into the structural properties of this graph and are of interest for the general Ancestral Recombination Graph reconstruction problem.