Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

An Ancestral Recombination Graph (ARG) is directed acyclic graph (with additional properties), that generalizes a directed tree, allowing structural properties that are not tree-like. With the growth of genomic and population data much of which does not fit ideal tree models, and the increasing appreciation of the genomic role of such phenomena as recombination (crossing-over and gene-conversion), recurrent and back mutation, horizontal gene transfer, and mobile genetic elements, there is greater need to understand the algorithmics and combinatorics of ARGs. In this talk I will discuss and prove two results concerning the combinatorial structure of ARGs. Both of the result concern the question of how complex an ARG has to be in order to derive a given set of binary sequences M. Generally, we want an ARG to be simple and as `tree-like' as possible. However, there is a simple constaint making `tree-likeness' difficult. The ARG-decomposition theorem shows that this is the only constraint, so there is a `fully-decomposed' ARG for every M. A MinARG is an ARG that minimizes the number of `recombination nodes' (nodes with in-degree two). Generally, we want to construct a MinARG for an input set M. However, it is not always possible to construct a fully-decomposed MinARG. I will show (and maybe prove) a NASC for when a fully-decomposed MinARG is possible. The NASC is abstract and non-constructive, and leaves open the general question of more fully understanding when a fully-decomposed ARG is possible. Joint work with V. Bafna, V. Bansal and Y. Song