FPGA Acceleration of Phylogeny Reconstruction for Whole Genome Data

Abstract

In this paper we describe our design and characterization of a co-processor architecture to accelerate median-based phylogenetic reconstruction for gene-rearrangement data. Our current design performs a parallelized version of the breakpoint median computation and achieves an average speedup of 876 for simulated input data having a high evolution rate. After integrating our hardware-based median computation into the GRAPPA toolset, we have achieved an average speedup of 189 over the entire phylogenetic reconstruction procedure. The results in this paper suggest that FPGA-based acceleration is a promising approach for computationally expensive phylogenetic problems that are based on combinatorial optimization.