Title :
Constructing Suffix Tree of Endogenous Feature on FPGA for High-Performance Identification of DNA Signatures
Author :
Feng, Lin ; Jean, Angela ; Leng, Chong Poh ; Danbo, Lai
Author_Institution :
Sch. of Comput. Eng., Nanyang Technol. Univ., Singapore, Singapore
Abstract :
Identification of DNA signatures is an important application which has been empowered by the increasing availability of thousands of bacterial and viral genomes through the next-generation sequencing (NGS) technologies. It is computationally challenging. In exploration for the solution, the suffix tree has been proposed as a data structure well suited to analyzing genomic sequences because it enables the storage of long strings in a logical, indexed manner for fast retrieval. We propose a new algorithm for identification of DNA signatures, based on exploitation of the endogenous features of a genomic sequence. These features are revealed in a construction of suffix array (an implementation of the generalized suffix tree). Furthermore, to greatly speed up the time-consuming process, the core algorithm is mapped and routed on to a Field-Programable Gate Array (FPGA) for parallel implementation. In this paper, we will focus primarily on the relationship of the data structure and the features associated. We will then describe the deployment of the hybrid computing system on a Hyper Transport compliant architecture. Illustrations are always given to clarify the technical details.
Keywords :
DNA; biology computing; field programmable gate arrays; genomics; hybrid simulation; molecular biophysics; parallel architectures; tree data structures; DNA signature identification; FPGA; HyperTransport compliant architecture; core algorithm; data structure; endogenous feature; field-programable gate array; genomic sequence; hybrid computing system; parallel implementation; suffix tree; Algorithm design and analysis; Arrays; Bioinformatics; DNA; Field programmable gate arrays; Genomics; Vegetation; DNA signature; Field-Programable Gate Array; endogenous feature; high-performance algorithm; suffix tree;
Conference_Titel :
Bioinformatics and Bioengineering (BIBE), 2011 IEEE 11th International Conference on
Conference_Location :
Taichung
Print_ISBN :
978-1-61284-975-1
DOI :
10.1109/BIBE.2011.48