Constant Depth Threshold Circuits For Exhaustive Epistasis Detection
It addresses the computationally complex problem of epistasis detection in bioinformatics, offering a hardware-efficient solution for neuromorphic systems.
The paper proposes constant depth threshold circuits for exhaustive epistasis detection, achieving runtime bounded by the number of combinations without additional complexity overhead, using log-linear space.
The development of large-scale neuromorphic hardware has made practical implementations of threshold gate-based circuits a near-term possibility. The complexity advantages regarding traditional computing classes, as evidenced in the literature, have prompted us to tackle Epistasis Detection, one of the most computationally complex combinatorial problems in bioinformatics. We propose specially designed circuits that calculate the relative frequencies of all dataset combinations in an efficient pipelined fashion, taking advantage of co-located memory and configurable parallelism, obtaining complexity gains. Overall, we obtain the runtime to be bounded by the number of combinations to calculate, without any additional complexity overhead, contrary to classical approaches, using log-linear space. To accomplish this, we propose a data encoding and combination generation strategy using Leaky Integrate and Fire (LIF) neurons, that feeds a constant depth threshold gate population count circuit. Accounting for typical hardware characteristics, such as limited fan-in and variable precisions, we obtain logarithmic depth and log-cubic linear connections, for the population count circuit by composing developed unbounded fan-in constant depth threshold gate circuits to perform population count and binary array sum.