Using set theory to reduce redundancy in pathway sets.

Area of Science:

• Bioinformatics
• Computational Biology
• Systems Biology

Background:

• Pathway databases like KEGG, Reactome, and ConsensusPathDB contain redundant information, hindering their effective use.
• Previous methods for redundancy reduction often result in pathways of heterogeneous sizes or mixed biological functions.
• Existing approaches for redundant pathway data include visualization, merging, or clustering, each with limitations.

Purpose of the Study:

• To develop an alternative method for reducing pathway redundancy without merging pathways.
• To generate pathway subsets that cover all genes in pathway databases or enrichment results.
• To achieve substantial reductions in redundancy while controlling pathway size and maximizing gene coverage.

Main Methods:

• Utilized the set cover mathematical framework to address pathway redundancy.
• Developed an algorithm to simplify enrichment data and identify redundant pathways.
• Applied the set cover approach to the ConsensusPathDB dataset and osteoarthritis enrichment pathways.

Main Results:

• Achieved a 74% reduction in redundancy while representing 100% of genes, or an 88% reduction for 95% of genes.
• Demonstrated that five of the top ten enriched osteoarthritis pathways were redundant subsets.
• Successfully removed redundant pathways from enrichment results, enabling more informative pathway representation.

Conclusions:

• The proposed method offers an alternative for handling pathway redundancy, ensuring homogeneous pathway sizes and maximized gene coverage.
• Pathways are preserved in their original form, maintaining biological interpretability.
• The set cover application optimizes pathway summaries for differentially regulated gene sets, prioritizing redundancy reduction, size control, or gene coverage.