title: A Resolution of the Static Formulation Question for the Problem of Computing the History Bound.
abstract: Evolutionary data has been traditionally modeled via phylogenetic trees; however, branching alone cannot model conflicting phylogenetic signals, so networks are used instead. Ancestral recombination graphs (ARGs) are used to model the evolution of incompatible sets of SNP data, allowing each site to mutate only once. The model often aims to minimize the number of recombinations. Similarly, incompatible cluster data can be represented by a reticulation network that minimizes reticulation events. The ARG literature has traditionally been disjoint from the reticulation network literature. By building on results from the reticulation network literature, we resolve an open question of interest to the ARG community. We explicitly prove that the History Bound, a lower bound on the number of recombinations in an ARG for a binary matrix, which was previously only defined procedurally, is equal to the minimum number of reticulation nodes in a network for the corresponding cluster data. To facilitate the proof, we give an algorithm that constructs this network using intermediate values from the procedural History Bound definition. We then develop a top-down algorithm for computing the History Bound, which has the same worst-case runtime as the known dynamic program, and show that it is likely to run faster in typical cases.
authors.affiliation: Department of Computer Science, University of California at Davis, Davis, CA.
authors.forename: Julia
authors.initials: J
authors.lastname: Matsieva
authors.affiliation: Department of Knowledge Engineering (DKE), Maastricht University, Maastricht, The Netherlands.
authors.forename: Steven
authors.initials: S
authors.lastname: Kelk
authors.affiliation: Institut des Sciences de l'Evolution de Montpellier (ISE-M), Montpellier, France.
authors.forename: Celine
authors.initials: C
authors.lastname: Scornavacca
authors.affiliation: Fred Hutchinson Cancer Research Center, Seattle, WA.
authors.forename: Chris
authors.initials: C
authors.lastname: Whidden
authors.affiliation: Department of Computer Science, University of California at Davis, Davis, CA.
authors.forename: Dan
authors.initials: D
authors.lastname: Gusfield
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D019143:Evolution, Molecular; D008957:Models, Genetic; D010802:Phylogeny; D020641:Polymorphism, Single Nucleotide; D011995:Recombination, Genetic / Q000235:genetics*