Justin Park, Computational Approaches to Reconstructing Ancestral Recombination Graphs

An ancestral recombination graph, or ARG, is a special kind of rooted, directed, acyclic graphs, that models the evolutionary history of a set of sequences representing individuals within a population. An ARG has two types of nodes: nodes of indegree 1, which represent mutations that result in new sequences, and nodes of indegree 2, which represent recombination (there is also the special node of indegree 0, which is the root of the ARG). Accurate reconstructions of ARGs have significant implications on a variety of issues, including the evolution of the human population (as well as other populations) and disease mapping. Since the true evolutionary history of a set of sequences is usually unknown, computational approaches to ARG reconstruction mostly attempt to reconstruct minimal ARGs --- ARGs with the minimum number of recombination events (or, nodes of indegree 2) --- to explain the evolution of the data. Further, these tools usually assume the infinite-site model as the evolutionary model. This model implies that each site mutates at most once during the evolutionary history of the population under study. In this talk, I will review existing approaches to minimal ARG reconstruction, and present our preliminary work on developing computational tools that attempt to reconstruct ARGs that are not necessarily minimal, but rather ones that reflect the "true" evolutionary history, by mimicking how recombination occurs in reality.