Show simple item record

AuthorRachid, Maan Haj
AuthorMalluhi, Qutaibah
AuthorAbouelhoda, Mohamed
Available date2016-05-16T10:55:23Z
Publication Date2014-04
Publication NameBioMed research international
ResourceScopus
CitationMaan Haj Rachid, Qutaibah Malluhi, and Mohamed Abouelhoda, "Using the Sadakane Compressed Suffix Tree to Solve the All-Pairs Suffix-Prefix Problem," BioMed Research International, vol. 2014, Article ID 745298, 11 pages, 2014.
ISSN2314-6141
URIhttp://dx.doi.org/10.1155/2014/745298
URIhttp://hdl.handle.net/10576/4526
AbstractThe all-pairs suffix-prefix matching problem is a basic problem in string processing. It has an application in the de novo genome assembly task, which is one of the major bioinformatics problems. Due to the large size of the input data, it is crucial to use fast and space efficient solutions. In this paper, we present a space-economical solution to this problem using the generalized Sadakane compressed suffix tree. Furthermore, we present a parallel algorithm to provide more speed for shared memory computers. Our sequential and parallel algorithms are optimized by exploiting features of the Sadakane compressed index data structure. Experimental results show that our solution based on the Sadakane's compressed index consumes significantly less space than the ones based on noncompressed data structures like the suffix tree and the enhanced suffix array. Our experimental results show that our parallel algorithm is efficient and scales well with increasing number of processors.
SponsorNPRP Grant no. 4-1454-1-233 from the Qatar National Research Fund (a member of Qatar Foundation).
Languageen
PublisherHindawi
SubjectAlgorithms
Animals
Caenorhabditis elegans
Computational Biology
Databases as topic
Statistics as topic
Time factors
TitleUsing the Sadakane compressed suffix tree to solve the all-pairs suffix-prefix problem
TypeArticle
Volume Number2014
dc.accessType Open Access


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record