Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment
The fundamental procedure of analyzing sequence content is sequence comparison. Sequence comparison can be defined as the problem of finding which parts of the sequences are similar and which parts are different, namely comparing two sequences to identify similarities and differences between them....
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Subjects: | |
| Online Access: | http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/1/Page%201-24.pdf http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/2/Full%20text.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
my-unimap-31259 |
|---|---|
| record_format |
uketd_dc |
| spelling |
my-unimap-312592014-01-16T13:10:36Z Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment Fatimah Noni, Muhamad The fundamental procedure of analyzing sequence content is sequence comparison. Sequence comparison can be defined as the problem of finding which parts of the sequences are similar and which parts are different, namely comparing two sequences to identify similarities and differences between them. A typical approach to solve this problem is to find a good and reasonable alignment between the two sequences. The main research in this project is to align the DNA sequences by using the Needleman-Wunsch algorithm for global alignment and Smith-Waterman algorithm for local alignment based on the Dynamic Programming algorithm. The Dynamic Programming Algorithm is guaranteed to find optimal alignment by exploring all possible alignments and choosing the best through the scoring and traceback techniques. The algorithms proposed and evaluated are to reduce the gaps in aligning sequences as well as the length of the sequences aligned without compromising the quality or correctness of results. In this project, a study on how to apply the computational power of Parallel Computing to speed up the lengthy process of comparing sequences without having to compromise on the optimal results. Parallelization is only applied to the Needleman-Wunsch algorithm. In order to verify the accuracy and consistency of measurements obtained in Needleman-Wunsch and Smith-Waterman algorithms the data is compared with Emboss (global) and Emboss (local) with 600 strands test data. Results show that the Needle and Smith programs are reduced gaps and mismatch, but do not affect the accuracy. Results on the parallelization of Needleman-Wunsch algorithm shows that the parallelization is only efficient for 3000 length of DNA sequences and above, but does not show any improvement for less than 500 lengths of DNA sequences although using multiple core platforms. Universiti Malaysia Perlis (UniMAP) 2011 Thesis en http://dspace.unimap.edu.my:80/dspace/handle/123456789/31259 http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/1/Page%201-24.pdf fc65ea1e7c181ffb0964a98d15044a8f http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/2/Full%20text.pdf 29c3ddba968da1268f7686c0a8850c19 http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/3/license.txt 8a4605be74aa9ea9d79846c1fba20a33 Sequence comparison DNA sequence alignment Needleman-Wunsch algorithm Dynamic Programming algorithm School of Computer and Communication Engineering |
| institution |
Universiti Malaysia Perlis |
| collection |
UniMAP Institutional Repository |
| language |
English |
| topic |
Sequence comparison DNA sequence alignment Needleman-Wunsch algorithm Dynamic Programming algorithm |
| spellingShingle |
Sequence comparison DNA sequence alignment Needleman-Wunsch algorithm Dynamic Programming algorithm Fatimah Noni, Muhamad Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment |
| description |
The fundamental procedure of analyzing sequence content is sequence comparison.
Sequence comparison can be defined as the problem of finding which parts of the
sequences are similar and which parts are different, namely comparing two sequences to identify similarities and differences between them. A typical approach to solve this problem is to find a good and reasonable alignment between the two sequences. The main research in this project is to align the DNA sequences by using the Needleman-Wunsch algorithm for global alignment and Smith-Waterman algorithm for local alignment based on the Dynamic Programming algorithm. The Dynamic Programming Algorithm is guaranteed to find optimal alignment by exploring all possible alignments and choosing the best through the scoring and traceback techniques. The algorithms proposed and evaluated are to reduce
the gaps in aligning sequences as well as the length of the sequences aligned without
compromising the quality or correctness of results. In this project, a study on how to apply
the computational power of Parallel Computing to speed up the lengthy process of
comparing sequences without having to compromise on the optimal results. Parallelization
is only applied to the Needleman-Wunsch algorithm. In order to verify the accuracy and
consistency of measurements obtained in Needleman-Wunsch and Smith-Waterman
algorithms the data is compared with Emboss (global) and Emboss (local) with 600 strands
test data. Results show that the Needle and Smith programs are reduced gaps and mismatch,
but do not affect the accuracy. Results on the parallelization of Needleman-Wunsch
algorithm shows that the parallelization is only efficient for 3000 length of DNA sequences
and above, but does not show any improvement for less than 500 lengths of DNA
sequences although using multiple core platforms. |
| format |
Thesis |
| author |
Fatimah Noni, Muhamad |
| author_facet |
Fatimah Noni, Muhamad |
| author_sort |
Fatimah Noni, Muhamad |
| title |
Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment |
| title_short |
Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment |
| title_full |
Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment |
| title_fullStr |
Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment |
| title_full_unstemmed |
Reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for DNA sequence alignment |
| title_sort |
reducing the search space and time complexity of needleman-wunsch algorithm (global alignment) and smith waterman algorithm (local alignment) for dna sequence alignment |
| granting_institution |
Universiti Malaysia Perlis (UniMAP) |
| granting_department |
School of Computer and Communication Engineering |
| url |
http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/1/Page%201-24.pdf http://dspace.unimap.edu.my:80/xmlui/bitstream/123456789/31259/2/Full%20text.pdf |
| _version_ |
1747836788210139136 |