TY - Generic T1 - Uncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques T2 - IEEE International Conference on Bioinformatics and Biomedicine, 2008. BIBM '08 Y1 - 2008 A1 - Nagarajan, N. A1 - Kingsford, Carl KW - avian hosted influenza genome KW - Bioinformatics KW - Capacitive sensors KW - Delay KW - diseases KW - Event detection KW - general bipartite graphs KW - genomic reassortments KW - Genomics KW - graph theory KW - high probability inconsistencies KW - History KW - human hosted influenza genome KW - incompatibility graph KW - Influenza KW - influenza strain KW - maximal biclique KW - maximal biclique enumeration KW - microorganisms KW - phylogenetic trees KW - Phylogeny KW - Public healthcare KW - quadratic delay algorithm KW - reassortment KW - reassortment event detection KW - Tree graphs KW - viral genome evolutionary history KW - virulence AB - 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. JA - IEEE International Conference on Bioinformatics and Biomedicine, 2008. BIBM '08 PB - IEEE SN - 978-0-7695-3452-7 ER -