Abstract
Identifying overlapping gene co-expression modules is a fundamental task in bioinformatics. Traditional models often struggle with overlapping memberships and varying interaction strengths. This paper introduces the Weighted Clique Decomposition (WCD) model and develops Fixed Parameter Tractable (FPT) algorithms. By parameterizing the problem by the number of modules ($k$) rather than the sum of edge weights ($K$), the proposed methods achieve significant performance gains, enabling the analysis of networks with higher interaction intensities.
Introduction
In biological systems, genes rarely operate in isolation; instead, they form functional modules or pathways. Identifying these modules from co-expression data is vital for drug discovery and disease research. While cliques—subgraphs where every node is connected—are a common model for these modules, real biological data is characterized by overlapping gene functions and varying strengths of co-expression.
The challenge lies in the computational complexity of partitioning graphs into cliques, which is NP-hard. This paper addresses the weighted, overlapping version of this problem, seeking an efficient solution for practical biological applications.
The Weighted Clique Decomposition Model
The authors propose the Weighted Clique Decomposition (WCD) model. This model assumes that the observed co-expression weight between two genes is the sum of the weights of all modules to which both genes belong. This additive approach allows for a more nuanced representation of biological reality than binary models.
Algorithmic Framework
To solve the WCD problem, the authors developed algorithms within the Fixed Parameter Tractable (FPT) framework. Unlike previous approaches that were limited by the total weight of the edges, these new algorithms are parameterized by the number of modules ($k$). This reparameterization ensures that the complexity grows exponentially only with the number of modules, making the method independent of the magnitude of expression values.
The pipeline involves three main stages:
- Preprocessing: Utilizing a modified Breadth-First Search (BFS) to prune non-overlapping cliques.
- Kernelization: Reducing the graph to a "kernel" of at most $4^k$ vertices, preserving the optimal solution while minimizing the search space.
- Weight Recovery: Determining the weights of the identified clique structures using either Linear Programming (
lp) for real-valued weights or Integer Partitioning (ipart) for integer weights.
This approach improves upon the traditional Weighted Edge Clique Partition (WECP) problem, which is defined as follows:
Experimental Evaluation
The algorithms were tested on biologically-inspired synthetic datasets: the TF-Dataset (based on transcription factor relationships) and the LV-Dataset (based on latent variables from real gene expression compendia). These datasets reflect the heavy-tailed weight distributions found in nature.
The results demonstrate superior scaling for the new lp and ipart algorithms compared to the previous wecp baseline. While wecp consistently timed out when the sum of weights $K$ exceeded 13, the new methods successfully solved instances with $K$ up to 44 in under an hour. Furthermore, the new algorithms became the more efficient choice for any network containing six or more modules.
Conclusion and Future Work
The WCD model and its associated FPT algorithms provide a robust framework for identifying overlapping gene modules in noise-free settings. Future research will focus on adapting these methods to handle noisy biological measurements through approximation techniques and scaling the algorithms to handle the thousands of modules present in whole-genome analyses. Additionally, incorporating hierarchical biological structures could further refine the model's accuracy.
Summary updated