Uncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques

TitleUncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques
Publication TypeConference Proceedings
Year of Conference2008
AuthorsNagarajan N., Kingsford C
Conference NameIEEE International Conference on Bioinformatics and Biomedicine, 2008. BIBM '08
Date Published2008
ISBN Number978-0-7695-3452-7
Keywordsavian hosted influenza genome, Bioinformatics, Capacitive sensors, Delay, diseases, Event detection, general bipartite graphs, genomic reassortments, Genomics, graph theory, high probability inconsistencies, History, human hosted influenza genome, incompatibility graph, Influenza, influenza strain, maximal biclique, maximal biclique enumeration, microorganisms, phylogenetic trees, Phylogeny, Public healthcare, quadratic delay algorithm, reassortment, reassortment event detection, Tree graphs, viral genome evolutionary history, virulence

The evolutionary histories of viral genomes have received significant recent attention due to their importance in understanding virulence and the corresponding ramifications to public health. We present a novel framework to detect reassortment events in influenza based on the comparison of two distributions of phylogenetic trees, rather than a pair of, possibly unreliable, consensus trees. We show how to detect all high-probability inconsistencies between two distributions of trees by enumerating maximal bicliques within a defined incompatibility graph. In the process, we give the first quadratic delay algorithm for enumerating maximal bicliques within general bipartite graphs. We demonstrate the utility of our approach by applying it to several sets of influenza genomes (both human- and avian-hosted) and successfully identify all known reassortment events and a few novel candidate reassortments. In addition, on simulated datasets, our approach correctly finds implanted reassortments and rarely detects reassortments where none were introduced.