FPGA Hardware Acceleration of a Phylogenetic Tree Reconstruction with Maximum Parsimony Algorithm
-
- BLOCK Henry
- Faculty of Engineering, Information and Systems, University of Tsukuba
-
- MARUYAMA Tsutomu
- Faculty of Engineering, Information and Systems, University of Tsukuba
この論文をさがす
抄録
<p>In this paper, we present an FPGA hardware implementation for a phylogenetic tree reconstruction with a maximum parsimony algorithm. We base our approach on a particular stochastic local search algorithm that uses the Progressive Neighborhood and the Indirect Calculation of Tree Lengths method. This method is widely used for the acceleration of the phylogenetic tree reconstruction algorithm in software. In our implementation, we define a tree structure and accelerate the search by parallel and pipeline processing. We show results for eight real-world biological datasets. We compare execution times against our previous hardware approach, and TNT, the fastest available parsimony program, which is also accelerated by the Indirect Calculation of Tree Lengths method. Acceleration rates between 34 to 45 per rearrangement, and 2 to 6 for the whole search, are obtained against our previous hardware approach. Acceleration rates between 2 to 36 per rearrangement, and 18 to 112 for the whole search, are obtained against TNT.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E100.D (2), 256-264, 2017
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282679355624576
-
- NII論文ID
- 130005306497
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 2241/00146072
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可