A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation

An important goal in microbial computational genomics is to identify crucial events in the evolution of a gene that severely alter the duplication, loss and mobilization patterns of the gene within the genomes in which it disseminates. In this paper, we formalize this microbiological goal as a new pattern-matching problem in the domain of Gene tree and Species tree reconciliation, denoted "Reconciliation-Scenario Altering Mutation (RSAM) Discovery". We propose an $O(m\cdot n\cdot k)$ time algorithm to solve this new problem, where $m$ and $n$ are the number of vertices of the input Gene tree and Species tree, respectively, and $k$ is a user-specified parameter that bounds from above the number of optimal solutions of interest. The algorithm first constructs a hypergraph representing the $k$ highest scoring reconciliation scenarios between the given Gene tree and Species tree, and then interrogates this hypergraph for subtrees matching a pre-specified RSAM Pattern. Our algorithm is optimal in the sense that the number of hypernodes in the hypergraph can be lower bounded by $Ω(m\cdot n\cdot k)$. We implement the new algorithm as a tool, called RSAM-finder, and demonstrate its application to -the identification of RSAMs in toxins and drug resistance elements across a dataset spanning hundreds of species.