12 August 2011 in BMC Genomics
Virulence acquisition and loss is a dynamic adaptation of pathogens to thrive in changing milieus. We investigated the mechanisms of virulence loss at the whole genome level using Babesia bovis as a model apicomplexan in which genetically related attenuated parasites can be reliably derived from virulent parental strains in the natural host. We expected virulence loss to be accompanied by consistent changes at the gene level, and that such changes would be shared among attenuated parasites of diverse geographic and genetic background.
22 November 2017 in IEEE/ACM Transactions on Computational Biology and Bioinformatics
Methods to efficiently uncover community structures are required in a number of biological applications where observing tightly-knit groups of vertices (“communities”) can offer insights into the structural and functional building blocks. Classical applications of community detection have largely focused on unipartite networks. However, due to increased availability of biological data from various sources, there is now a need for handling heterogeneous networks which are built out of multiple types of objects. In this paper, we address the problem of identifying communities from biological bipartite networks---i.e., networks where interactions are observed between two different types of objects. Toward detecting communities in such bipartite networks, we make the following contributions: i) (metric) we propose a variant of bipartite modularity; ii) (algorithms) we present an efficient algorithm called biLouvain that implements a set of heuristics toward fast and precise community detection in bipartite networks (https://github.com/paolapesantez/biLouvain); and iii) (experiments) we present a thorough experimental evaluation of our algorithm including comparison to other state-of-the-art methods to identify communities in bipartite networks. Experimental results show that biLouvain identifies communities that have a comparable or better quality (as measured by bipartite modularity) than existing methods, while significantly reducing the time-to-solution between one and four orders of magnitude.
9 September 2023 in ACM Transactions on Embedded Computing Systems
Recent advances in 2.5D chiplet platforms provide a new avenue for compact scale-out implementations of emerging compute- and data-intensive applications including machine learning. Network-on-Interposer (NoI) enables integration of multiple chiplets on a 2.5D system. While these manycore platforms can deliver high computational throughput and energy efficiency by running multiple specialized tasks concurrently, conventional NoI architectures have a limited computational throughput due to their inherent multi-hop topologies. In this paper, we propose Floret, a novel NoI architecture based on space-filling curves (SFCs). The Floret architecture leverages suitable task mapping, exploits the data flow pattern, and optimizes the inter-chiplet data exchange to extract high performance for multiple types of convolutional neural network (CNN) inference tasks running concurrently. We demonstrate that the Floret architecture reduces the latency and energy up to 58% and 64%, respectively, compared to state-of-the-art NoI architectures while executing datacenter-scale workloads involving multiple CNN tasks simultaneously. Floret achieves high performance and significant energy savings with much lower fabrication cost by exploiting the data-flow awareness of the CNN inference tasks.
23 March 2021 in IEEE Transactions on Network Science and Engineering
Detecting communities in time-evolving/dynamic networks is an important operation used in many real-world network science applications. While there have been several proposed strategies for dynamic community detection, such approaches do not necessarily take advantage of the locality of changes. In this paper, we present a new technique called Delta-Screening (or simply, Δ-screening) for updating communities in a dynamic graph. The technique assumes that the graph is given as a series of time steps, and outputs a set of communities for each time step. At the start of each time step, the Δ-screening technique examines all changes (edge additions and deletions) and computes a subset of vertices that are likely to be impacted by the change (using the modularity objective). Subsequently, only the identified subsets are processed for community state updates. Our experiments demonstrate that this scheme, despite its ability to prune vertices aggressively, is able to generate significant savings in runtime performance (up to 38× speedup over static baseline and 5 × over dynamic baseline implementations), without compromising on the quality. We test on both real-world and synthetic network inputs containing both edge additions and deletions. The Δ-screening technique is generic to be incorporated into any of the existing modularity-optimizing clustering algorithms. We tested using two state-of-the-art clustering implementations, namely, Louvain and SLM. In addition, we also show how to use the Δ-screening approach to delineate appropriate intervals of temporal resolutions at which to analyze a given input network.
16 September 2011 in Bioinformatics
Summary: A MapReduce-based implementation called MR-MSPolygraph for parallelizing peptide identification from mass spectrometry data is presented. The underlying serial method, MSPolygraph, uses a novel hybrid approach to match an experimental spectrum against a combination of a protein sequence database and a spectral library. Our MapReduce implementation can run on any Hadoop cluster environment. Experimental results demonstrate that, relative to the serial version, MR-MSPolygraph reduces the time to solution from weeks to hours, for processing tens of thousands of experimental spectra. Speedup and other related performance studies are also reported on a 400-core Hadoop cluster using spectral datasets from environmental microbial communities as inputs. Availability: The source code along with user documentation are available on http://compbio.eecs.wsu.edu/MR-MSPolygraph. Contact:ananth@eecs.wsu.edu; william.cannon@pnnl.gov Supplementary Information: Supplementary data are available at Bioinformatics online.