Biomarker Panel Search Space (2D)

Biomarker Panel Search

Shortlist size n 14 genes

Subsets checked (2ⁿ)

–

Brute-force time

–

Exponential ÷ linear slowdown

–

How it works

Every run picks n candidate biomarker genes (each with a random expression-deviation weight) and a diagnostic target sum, then times four real algorithms on the same systems-biology dataset with performance.now() — nothing here is a formula guess, every bar is a measured wall-clock duration.

verify one panel:      O(n)        — sum n weights, compare to target
sort expression set:   O(m log m)  — m = n·3000 "genome-wide" values
pairwise correlation:  O(k²)       — k = n·35 candidates, all gene pairs
find the panel:        O(n·2ⁿ)     — try every one of 2ⁿ subsets

The brute-force row is a real subset-sum search: for each of the 2ⁿ subsets of the shortlist it sums the included genes and checks the target — the textbook NP-hard combinatorial-search pattern behind picking a minimal biomarker panel, choosing a gene set for a network hub, or any "does some combination explain the phenotype" question in systems biology. Verifying one proposed panel is cheap and linear; finding it by exhaustion is not.

Shortlist size n — candidate genes fed to the exhaustive subset search; doubling n doubles the subset count, so the exponential bar can leap off the chart while the others barely move.
Run benchmark — executes all four algorithms live at the current n and appends one new group of bars to the chart.
Y-axis scale — log makes small polynomial bars visible next to a huge exponential one; linear shows the raw disparity in real proportion.
Clear history — wipes the chart and starts a fresh run sequence.

Real-world relevance: this is why genomics pipelines never brute-force a full gene panel — they use the fast O(n)/O(n log n)/O(n²) stages to shortlist candidates first, and only run exhaustive or heuristic search over the small remainder, exactly as staged here.

computing…

O(n) mean O(n log n) sort O(n²) pairwise O(n·2ⁿ) subset-sum