Enhancement of n-gram-hirschberg algorithm using hash function
Loading...
Date
2008
Authors
Mohammad Abu-Hashem, Muhannad Abdul-Qader
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Current technologies in protein sequencing have produced enormous
biological data which need faster and scalable data analysis and data management
techniques. This gives new challenges to the computer scientists in producing fast
and efficient algorithms in order to analyze and organize large data. Pairwise
sequence alignment algorithm is the basic operation in protein sequence database
search, which is one of the activities of protein sequence analysis. Dynamic
programming-based algorithm such as Smith-Waterman algorithm, which produces
the most optimal result, has been known as one of the most used algorithm for
sequence alignment. Hirschberg algorithm is the space saving version of SmithWaterman
algorithm. However, both algorithms are still very computational
intensive. The N-Gram-Hirschberg algorithm is introduced to further reduced the
space requirement and at the same time, to speed up the sequences alignment
algorithm. This research aims to enhance the N-Gram-Hirschberg algorithm by
embedding the Hashing function, adopted from an exact string matching algorithm
called Karp-Rabin. The hash function is used to enhance the transformation process
for the algorithm. We further improve the computation time of Hashing-N-GramHirschberg
by using parallel methods at the two levels of parallelism. The new
method improves the processing time of the N-Gram-Hirschberg without sacrificing
the quality of the output. The best time enhancement we got was when word length is
two. This is the same word length as those produced by N-Gram-Hirschberg
algorithm and Smith-Waterman algorithm.
Description
Keywords
N-Gram-Hirschberg , Algorithm using