A high performance FPGA-based core for phylogenetic analysis with maximum parsimony method

S. Kasap, Khaled Benkrid

Research output: Chapter in Book/Report/Conference proceedingConference proceedingpeer-review

3 Citations (Scopus)


We present in this paper the detailed FPGA design of the Maximum Parsimony method for molecular-based phylogenetic analysis and its implementation on a Xilinx Virtex-4 FPGA chip. This is the first FPGA implementation of this method for nucleotide sequence data ever reported in the literature. The hardware architecture consists of a linear systolic array composed of 20 processing elements each of which performing the Sankoff's algorithm for a different tree topology in parallel. This array computes the scores of all theoretically possible trees for a given number of taxa in several iterations. The currently supported maximum number of taxa is 12 but this number can be easily increased. Furthermore, the resulting implementation outperforms an equivalent desktop-based software implementation (using PAUP software) by several orders of magnitude. The speed-up values achieved by the hardware implementation can reach over 20,000x for the 12-taxa case. This is achieved through harnessing both coarse-grain and fine-grain parallelism available in the algorithm and corresponding hardware implementation platform
Original languageEnglish
Title of host publicationProceedings of the 2009 International Conference on Field-Programmable Technology, FPT'09
Number of pages7
ISBN (Print)978-1-4244-4375-8
Publication statusPublished - 12 Jan 2010
Externally publishedYes
EventIEEE International Conference on Field-Programmable Technology
- Sydney, Australia
Duration: 9 Dec 200911 Dec 2009


ConferenceIEEE International Conference on Field-Programmable Technology


Dive into the research topics of 'A high performance FPGA-based core for phylogenetic analysis with maximum parsimony method'. Together they form a unique fingerprint.

Cite this