Understanding recombination is a central problem in population genetics. In this paper, we address an established problem in Computational Biology: compute lower bounds on the minimum number of historical recombinations for generating a set of sequences [11,13,9,1,2,15]. In particular, we propose a new recombination lower bound: the forest bound. We show that the forest bound can be formulated as the minimumperfect phylogenetic forest problem, a natural extension to the classic binary perfect phylogeny problem, which may be of interests on its own. We then show that the forest bound is provably higher than the optimal haplotype bound [13], a very good lower bound in practice [15].We prove that, like several other lower bounds [2], computing the forest bound isNPhard. Finally, we describe an integer linear programming (ILP) formulation that computes the forest bound precisely for certain range of data. Simulation results show that the forest bound may be useful in computing lower bounds for low quality data.
['Yufeng Wu', 'Dan Gusfield']
A new recombination lower bound and the minimum perfect phylogenetic forest problem