@proceedings {38176, title = {Computing the Tree of Life: Leveraging the Power of Desktop and Service Grids}, year = {2011}, month = {2011}, type = {10.1109/IPDPS.2011.344}, abstract = {The trend in life sciences research, particularly in molecular evolutionary systematics, is toward larger data sets and ever-more detailed evolutionary models, which can generate substantial computational loads. Over the past several years we have developed a grid computing system aimed at providing researchers the computational power needed to complete such analyses in a timely manner. Our grid system, known as The Lattice Project, was the first to combine two models of grid computing - the service model, which mainly federates large institutional HPC resources, and the desktop model, which harnesses the power of PCs volunteered by the general public. Recently we have developed a "science portal" style web interface that makes it easier than ever for phylogenetic analyses to be completed using GARLI, a popular program that uses a maximum likelihood method to infer the evolutionary history of organisms on the basis of genetic sequence data. This paper describes our approach to scheduling thousands of GARLI jobs with diverse requirements to heterogeneous grid resources, which include volunteer computers running BOINC software. A key component of this system provides a priori GARLI runtime estimates using machine learning with random forests.}, keywords = {(artificial, (mathematics), analysis, BOINC, COMPUTATION, computational, computing, data, Estimation, evolutionary, GARLI, genetic, Grid, GRIDS, handling, heterogeneous, History, HPC, information, intelligence), interface, interfaces, Internet, jobs, lattice, learning, life, likelihood, load, machine, maximum, method, model, molecular, phylogenetic, portal, Portals, power, project, resource, Science, sequence, service, services, sets, software, substantial, system, systematics, tree, TREES, user, Web}, author = {Adam L. Bazinet and Michael P. Cummings} } @proceedings {38555, title = {Uncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques}, year = {2008}, month = {2008}, publisher = {IEEE}, type = {10.1109/BIBM.2008.78}, abstract = {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.}, keywords = {avian 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}, isbn = {978-0-7695-3452-7}, author = {Nagarajan, N. and Kingsford, Carl} }