Technical Papers Archive

A Parallel Algorithm for the Construction of Partial Information Decomposition-Based Genome-Scale Networks from Single-Cell Datasets


Authors: Sriram P. Chockalingam, Maneesha Aluru, and Srinivas Aluru (Georgia Institute of Technology)

Abstract: Methods for constructing gene networks from tissue-level expression data, developed over the past two decades, are being reassessed for applicability to single-cell datasets. The higher noise and sparsity of single-cell data demand more robust, computationally intensive approaches, while also requiring scalability to orders-of-magnitude larger datasets. We focus on PIDC, an information-theoretic method that produces high-quality networks from single-cell data but incurs $O(n^3)$ runtime for $n$ genes, limiting scalability even with parallelization. We present a novel sequential algorithm that reduces complexity to $O(n^2 \log n)$, along with its distributed-memory parallelization achieving $O(n^2/p + T_{sort}(n^2, p))$ time, where $p$ is the number of processors and $T_{sort}$ is the time for parallel sorting. On 64 cores, our MPI implementation achieves a 158X speedup over the existing PIDC algorithm. We further demonstrate construction of a genome-scale human gene network with 30,000 genes from 800,000 cells in 2.5 hours using 2,048 cores.


Presentation: file

Back to Technical Papers Archive Listing