FPGA-based computation for maximum likelihood phylogenetic tree evaluation
Publication in refereed journal

CUHK Authors
Author(s) no longer affiliated with CUHK


Full Text

Times Cited
Web of Science4WOS source URL (as at 09/08/2020) Click here for the latest count

Other information
AbstractPhylogenetic tree is a meaningful representation for the evolutionary history of different organisms. Due to the exponentially increasing search space for the optimal Maximum Likelihood (ML) criterion, the phylogeny inference is classified as NP-hard. Heuristic search makes use of the likelihood evaluation function extensively to give score for the candidate solutions. This tree evaluation becomes a critical but computationally demanding task. In this paper, we address the computational issue for the evaluation of a phylogenetic tree under ML criterion, for a given set D of n properly aligned DNA sequences each with l nucleotide sites. We present a high performance field programmable gate arrays (FPGA) implementation for tackling the tree evaluation process in order to speed up the tree reconstruction. An efficient fine-grained parallel design based on the idea of partial likelihood is proposed. It has been shown to be 100 times faster than solely using the software.
All Author(s) ListMak TST, Lam KP
Name of Conference14th International Conference on Field-Programmable Logic and Applications
Start Date of Conference30/08/2004
End Date of Conference01/09/2004
Place of ConferenceLeuven
Journal nameLecture Notes in Artificial Intelligence
Year2004
Month1
Day1
Volume Number3203
PublisherSPRINGER-VERLAG BERLIN
Pages1076 - 1079
ISBN3-540-22989-2
ISSN0302-9743
LanguagesEnglish-United Kingdom
Web of Science Subject CategoriesComputer Science; Computer Science, Hardware & Architecture; Computer Science, Software Engineering; Computer Science, Theory & Methods

Last updated on 2020-10-08 at 02:37