An Event-Driven Approach to Genotype Imputation on a Custom RISC-V Cluster

Area of Science:

• Genetics
• Computer Science
• Bioinformatics

Background:

• Genotype imputation is crucial for inferring missing genetic markers in DNA.
• The Li and Stephens model is computationally intensive for modern x86 architectures.

Purpose of the Study:

• To develop an event-driven solution for genotype imputation.
• To evaluate the performance of the Li and Stephens model in an event-driven domain.
• To assess the scalability of the proposed algorithm on parallel hardware.

Main Methods:

• Implementation of the Li and Stephens model using graph-based Hidden Markov Modeling.
• Customized forward/backward dynamic programming algorithm.
• Event-driven paradigm mapping to thousands of concurrent cores on a RISC-V NoC cluster (POETS).
• Optimization using linear interpolation.

Main Results:

• A multi-core run achieved a 270X reduction in wall-clock processing time compared to a single-threaded x86 solution.
• Optimized algorithm demonstrated a reduction of approximately 5 orders of magnitude in wall-clock time.
• Demonstrated scalability of the event-driven algorithm with increasing hardware resources.

Conclusions:

• The event-driven paradigm is a viable and highly efficient approach for genotype imputation.
• Significant performance gains are achievable for genetic data analysis using parallel processing.
• Further investigation into event-driven solutions for complex genetic algorithms is warranted.