title: FPGA Acceleration of the phylogenetic likelihood function for Bayesian MCMC inference methods.
abstract: BACKGROUND
  Likelihood (ML)-based phylogenetic inference has become a popular method for estimating the evolutionary relationships among species based on genomic sequence data. This method is used in applications such as RAxML, GARLI, MrBayes, PAML, and PAUP. The Phylogenetic Likelihood Function (PLF) is an important kernel computation for this method. The PLF consists of a loop with no conditional behavior or dependencies between iterations. As such it contains a high potential for exploiting parallelism using micro-architectural techniques. In this paper, we describe a technique for mapping the PLF and supporting logic onto a Field Programmable Gate Array (FPGA)-based co-processor. By leveraging the FPGA's on-chip DSP modules and the high-bandwidth local memory attached to the FPGA, the resultant co-processor can accelerate ML-based methods and outperform state-of-the-art multi-core processors.
  
  
  RESULTS
  We use the MrBayes 3 tool as a framework for designing our co-processor. For large datasets, we estimate that our accelerated MrBayes, if run on a current-generation FPGA, achieves a 10x speedup relative to software running on a state-of-the-art server-class microprocessor. The FPGA-based implementation achieves its performance by deeply pipelining the likelihood computations, performing multiple floating-point operations in parallel, and through a natural log approximation that is chosen specifically to leverage a deeply pipelined custom architecture.
  
  
  CONCLUSIONS
  Heterogeneous computing, which combines general-purpose processors with special-purpose co-processors such as FPGAs and GPUs, is a promising approach for high-performance phylogeny inference as shown by the growing body of literature in this field. FPGAs in particular are well-suited for this task because of their low power consumption as compared to many-core processors and Graphics Processor Units (GPUs).
authors.affiliation: Department of Computer Science and Engineering, University of South Carolina, Columbia, SC, USA.
authors.forename: Stephanie
authors.initials: S
authors.lastname: Zierke
authors.forename: Jason D
authors.initials: JD
authors.lastname: Bakos
mesh_terms: D001499:Bayes Theorem; D016013:Likelihood Functions; D010802:Phylogeny; D012984:Software
references.citation: Syst Biol. 2009 Apr;58(2):224-39
references.pmid: 20525580
references.citation: J Mol Evol. 1981;17(6):368-76
references.pmid: 7288891
references.citation: Proc Natl Acad Sci U S A. 1996 Aug 20;93(17):9188-93
references.pmid: 8799176
references.citation: Bioinformatics. 2009 Jun 1;25(11):1370-6
references.pmid: 19369496
references.citation: Mycologia. 2002 Jan-Feb;94(1):85-98
references.pmid: 21156480
references.citation: Mycologia. 2006 Nov-Dec;98(6):1018-28
references.pmid: 17486977
references.citation: Bioinformatics. 2003 Aug 12;19(12):1572-4
references.pmid: 12912839
references.citation: Mycologia. 2003 Jul-Aug;95(4):756-64
references.pmid: 21148982
references.citation: Bioinformatics. 2006 Nov 1;22(21):2688-90
references.pmid: 16928733
references.citation: Bioinformatics. 2005 Feb 15;21(4):456-63
references.pmid: 15608047
references.citation: BMC Bioinformatics. 2008 Jul 28;9:322
references.pmid: 18662388
references.citation: J Mol Evol. 2004 Mar;58(3):252-68
references.pmid: 15045481
references.citation: Mol Biol Evol. 2003 Feb;20(2):255-66
references.pmid: 12598693
references.citation: Mol Biol Evol. 2007 Aug;24(8):1586-91
references.pmid: 17483113
references.citation: Bioinformatics. 2002 Mar;18(3):502-4
references.pmid: 11934758
references.citation: Bioinformatics. 2004 Feb 12;20(3):407-15
references.pmid: 14960467
references.citation: Bioinformatics. 2005 Oct 1;21(19):3794-6
references.pmid: 16046495
references.citation: Bioinformatics. 2005 Apr 1;21(7):969-74
references.pmid: 15513992