Enhancement of n-gram-hirschberg algorithm using hash function
| dc.contributor.author | Mohammad Abu-Hashem, Muhannad Abdul-Qader | |
| dc.date.accessioned | 2015-07-30T06:12:54Z | |
| dc.date.available | 2015-07-30T06:12:54Z | |
| dc.date.issued | 2008 | |
| dc.description.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. | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/1065 | |
| dc.language.iso | en | en_US |
| dc.subject | N-Gram-Hirschberg | en_US |
| dc.subject | Algorithm using | en_US |
| dc.title | Enhancement of n-gram-hirschberg algorithm using hash function | en_US |
| dc.type | Thesis | en_US |
Files
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: