Fast gene set enrichment analysis

Key results

1. ShownThe multilevel estimator computes extremely small GSEA P-values accurately, and its own error estimates match the true errors measured against an exact algorithm.

   On rounded statistics from the example data, FGSEA-multilevel (Z = 101) agreed closely with an exact dynamic-programming method; estimated and actual errors matched for P-values from 10^-4 to 10^-100, gene-set sizes 15 to 250 and Z from 101 to 1001. Example-data P-values reached 10^-26, consistent with FGSEA-simple run with 10^8 permutations. · 1 Main; 2.5.6 Comparison with the exact method

2. ShownAcross 605 GEO datasets, BH-adjusted FGSEA P-values flag far more pathways at FDR 0.01 than the Broad implementation's Q-values, which are more conservative in a pathway-size-dependent way.

   With the C5_BP collection, Broad GSEA Q-values passed 39467 pathways in total: 60% of the 65690 from BH-adjusted FGSEA-simple at depth 10^4 and 48% of the 81628 from FGSEA-multilevel. Broad's pooled null was more sensitive than BH at the same 10^4 depth on some datasets, and even depth 10^5 was not enough for some datasets under BH. · 1 Main

3. ShownSharing one pool of random gene sets across all pathways, plus a square-root block decomposition for enrichment scores, yields the same nominal P-values as the reference implementation about two orders of magnitude faster.

   On a Th1 activation ranking against 700 Reactome pathways at n = 10000, FGSEA-simple and the reference gave indistinguishable P-values up to sampling noise, taking about 4 seconds vs about 420 seconds; this makes 10^5 samples routine and P-values near 10^-5 reachable. · 1 Main; 2.3 FGSEA-simple: an algorithm for fast…

4. ShownMany real datasets need sampling depths that are inconvenient or even impossible to run with the reference implementation before any pathway passes BH-adjusted FDR, because significance appears abruptly at a critical depth.

   Over half of the 605 two-condition GEO datasets had a critical sampling depth of at least 10^4, and 10-20% (by collection) at least 10^5; with the whole MSigDB collection single datasets reached 5·10^6, while reference time and memory grow linearly with samples and collection size. · 1 Main

5. SuggestedA filtering step condenses overlapping significant hits without needing a pathway hierarchy, by keeping a pathway only if it adds information beyond pathways already reported.

   A pathway is kept if it stays enriched below a set threshold either outside or only within the genes of another significant pathway, tested with FGSEA-simple in a sieve-like pass; it is illustrated on the example dataset only, with no quantitative evaluation in this text. · 1 Main; 2.6 Filtering redundant pathways