title: The imperfect ancestral recombination graph reconstruction problem: upper bounds for recombination and homoplasy.
abstract: One of the central problems in computational biology is the reconstruction of evolutionary histories. While models incorporating recombination and homoplasy have been studied separately, a missing component in the theory is a robust and flexible unifying model which incorporates both of these major biological events shaping genetic diversity. In this article, we introduce the first such unifying model and develop algorithms to find the optimal ancestral recombination graph incorporating recombinations and homoplasy events. The power of our framework is the connection between our formulation and the Directed Steiner Arborescence Problem in combinatorial optimization. We implement linear programming techniques as well as heuristics for the Directed Steiner Arborescence Problem, and use our methods to construct evolutionary histories for both simulated and real data sets.
authors.affiliation: Department of Computer Science, Brown Univerisity, Providence, Rhode Island 02912, USA. lam@cs.brown.edu
authors.forename: Fumei
authors.initials: F
authors.lastname: Lam
authors.forename: Ryan
authors.initials: R
authors.lastname: Tarpine
authors.forename: Sorin
authors.initials: S
authors.lastname: Istrail
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D004330:Drosophila / Q000235:genetics; D019143:Evolution, Molecular; D008957:Models, Genetic; D010802:Phylogeny; D011995:Recombination, Genetic