Deploying FPGAs to future-proof genome-wide analyses based on linkage disequilibrium

The ever-increasing genomic dataset sizes, fueled by continuous advances in DNA sequencing technologies, are expected to bring new scientific achievements in several fields of biology. The fact that the demand for higher sequencing throughput has long outpaced Moore's law, however, presents a challenge for the efficient analysis of future large-scale datasets, suggesting the urgent need for custom solutions to keep up with the current trend of increasing sample sizes. In this work, we focus on a widely employed, yet prohibitively compute- and memory-intensive, measure that is called linkage disequilibrium (LD), defined as the non-random association between alleles. Modern microprocessor architectures are not well equipped to deliver high performance for LD due to the lack of a vectorized population counter (counting set bits in registers). We present a modular and highly parallel reconfigurable architecture that, in combination with a generic memory layout transform, allows to rapidly conduct large-scale pairwise calculations on arbitrarily large one- and two-dimensional binary vectors, exhibiting increased bit-counting capacity. We map the proposed architecture to all four reconfigurable devices of a multi-FPGA platform, and deploy them synergistically for the evaluation of LD on genomic datasets with up to 1,000,000 sequences, achieving between 12.7X (4 FPGAs vs. 12 cores) and 134.9X (4 FPGAs vs. 1 core) faster execution than state-of-the-art reference software running on multi-core workstations. For real-world analyses that employ LD, such as scanning the 22nd human chromosome for traces of positive selection, the proposed system can lead to 6X faster processing, thus enabling more thorough genome-wide scans.