title: Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution.
abstract: BACKGROUND
  We are interested in studying the evolution of DNA single nucleotide polymorphism sequences which have undergone (meiotic) recombination. For a given set of sequences, computing the minimum number of recombinations needed to explain the sequences (with one mutation per site) is a standard question of interest, but it has been shown to be NP-hard, and previous algorithms that compute it exactly work either only on very small datasets or on problems with special structure.
  
  
  RESULTS
  In this paper, we present efficient, practical methods for computing both upper and lower bounds on the minimum number of needed recombinations, and for constructing evolutionary histories that explain the input sequences. We study in detail the efficiency and accuracy of these algorithms on both simulated and real data sets. The algorithms produce very close upper and lower bounds, which match exactly in a surprisingly wide range of data. Thus, with the use of new, very effective lower bounding methods and an efficient algorithm for computing upper bounds, this approach allows the efficient, exact computation of the minimum number of needed recombinations, with high frequency in a large range of data. When upper and lower bounds match, evolutionary histories found by our algorithm correspond to the most parsimonious histories.
  
  
  BACKGROUND
  HapBound and SHRUB, programs implementing the new algorithms discussed in this paper, are available at http://wwwcsif.cs.ucdavis.edu/~gusfield/lu.html
authors.affiliation: Department of Computer Science, University of California Davis, CA 95616, USA. yssong@cs.ucdavis.edu
authors.forename: Yun S
authors.initials: YS
authors.lastname: Song
authors.forename: Yufeng
authors.initials: Y
authors.lastname: Wu
authors.forename: Dan
authors.initials: D
authors.lastname: Gusfield
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000737:chemistry; D030562:Databases, Protein; D019143:Evolution, Molecular; D006239:Haplotypes; D006801:Humans; D020641:Polymorphism, Single Nucleotide; D011995:Recombination, Genetic; D016415:Sequence Alignment; D017421:Sequence Analysis / Q000379:methods; D012984:Software
chemical_list: D004247:DNA