What do we gain when tolerating loss? The information bottleneck, lossy compression, and detecting horizontal gene transfer

Abstract

Most microbes have the capacity to acquire genetic material from their environment. Recombination of foreign DNA yields genomes that are, at least in part, incongruent with the vertical history of their species. Dominant approaches for detecting these transfers are phylogenetic, requiring a painstaking series of analyses including alignment and phylogenetic tree reconstruction. These traditional pan-genomic methods do not scale. Here we propose an unsupervised, alignment-free and tree-free technique based on the sequential information bottleneck (SIB), an optimization procedure designed to extract some portion of relevant information from one random variable conditioned on another. In our case, this joint probability distribution tabulates occurrence counts of k-mers against their genomes of origin with the expectation that recombination will create a strong signal that unifies certain sets of co-occuring k-mers. We conceptualize the technique as a rate-distortion problem, measuring distortion in the relevance information as k-mers are compressed into clusters based on their co-occurrence in the source genomes. The result is fast, model-free, lossy compression of k-mers into groups that learns tracts of shared genome sequence differentiating recombined elements from the vertically inherited core. We show that the technique yields a new recombination measure based purely on information, divorced from any biases and limitations inherent to alignment and phylogeny. SignificanceThe information bottleneck, a lossy compression technique borrowed from the information theoretic and Natural Langauge Processing literature, is well suited to detecting evolutionary patterns in sets of co-occuring k-mers. Here we show that we can detect simulated and real recombination events while highlighting a core set of k-mers that comprise the vertically inherited portion of any set of genomes. Moreover, the compressibility of any given set of genomes offers a new way to compare the pangenomes of clades across the microbial tree of life. In our application, the bottleneck is informed by genome origin, our relevance variable, but the technique is general. The information bottleneck can be used for any biological contingency matrix where the goal is to learn groups from unstructured data.