Alphabet-dependent Parallel Algorithm for Suffix Tree Construction for Pattern Searching

Journal article

Authors/Editors

Research Areas

No matching items found.

Publication Details

Author list: Kaniwa F, Kuthadi VM, Dinakenyane O, Schroeder H

Place: TASMANIA

Publication year: 2017

Journal: INTERNATIONAL JOURNAL OF GRID AND DISTRIBUTED COMPUTING (2005-4262)

Journal acronym: INT J GRID DISTRIB

Volume number: 10

Issue number: 1

Start page: 9

End page: 20

Number of pages: 12

ISSN: 2005-4262

eISSN: 2207-6379

Languages: English-Great Britain (EN-GB)

View in Web of Science | View on publisher site | View citing articles in Web of Science

Abstract

Suffix trees have recently become very successful data structures in handling large data sequences such as DNA or Protein sequences. Consequently parallel architectures have become ubiquitous. We present a novel alphabet-dependent parallel algorithm which attempts to take advantage of the perverseness of the multicore architecture. Microsatellites are important for their biological relevance hence our algorithm is based on time efficient construction for identification of such. We experimentally achieved up to 15x speedup over the sequential algorithm on different input sizes of biological sequences.

Keywords

DNA Sequences, Parallel Algorithm, Suffix Trees

Documents

No matching items found.