Paper Info
Title
Enhancing N-Gram-Hirschberg Algorithm by Using Hash Function
Abstract
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 Smith-Waterman 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. 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 for protein sequence length ranges between 100-1000.
Year
DOI
Venue
2009
10.1109/AMS.2009.112
Asia International Conference on Modelling and Simulation
Keywords
Field
DocType
hash function,enhancing n-gram-hirschberg algorithm,protein sequence length range,processing time,sequences alignment algorithm,n-gram-hirschberg algorithm,best time enhancement,hirschberg algorithm,hashing function,used algorithm,smith-waterman algorithm,computed tomography,cryptography,databases,probability density function,string matching algorithm,proteins,blood pressure,sequence alignment,string matching,geometry,protein sequence,stress,shape,data mining,algorithm design and analysis,surgery
Ramer–Douglas–Peucker algorithm,Algorithm design,In-place algorithm,Algorithm,FSA-Red Algorithm,Needleman–Wunsch algorithm,Hirschberg's algorithm,Rabin–Karp algorithm,Population-based incremental learning,Mathematics
Conference
Citations 
PageRank 
References 
1
0.36
4
Authors
2
Name
Order
Citations
PageRank
Muhannad A. Abu-Hashem181.23
Nur'Aini Abdul Rashid230.73