An enhancement of the smith -waterman algorithm applied in query by humming for music information retrieval
- Undergraduate Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2013.
ABSTRACT: The Smith-Waterman algorithm is a dynamic programming method for determining optimal local alignments between nucleotide or protein sequences. However, it suffers from quadratic time and space complexity. It also neglects some data in its computation and cannot handle large deletion in a given pattern for comparison. As a result, many algorithmic and architectural enhancements have been proposed to solve this problem, but at the cost of reduced sensitivity in the algorithms or significant expense in hardware, respectively. Hence, there exists a need to enhancement. The researchers applied divide and conquer strategy to solve its computational time drawback. In handling large deletion problem, incremental gap alignment was used to solve missed hits of match and consider the large gap brought by the deletion. Finally, the researchers compared the enhanced algorithm with the original Smith-Waterman. As for the result, the enhanced algorithm performs faster by up to 75 percent making its complexity to O (mn/t). In handling large deletion and missed data in the matrix, the enhanced algorithm improved its way in handling the subsequence and collects all information for the results to be outputted to handle large deletion and missed data in the matrix.
5
ABSTRACT: The Smith-Waterman algorithm is a dynamic programming method for determining optimal local alignments between nucleotide or protein sequences. However, it suffers from quadratic time and space complexity. It also neglects some data in its computation and cannot handle large deletion in a given pattern for comparison. As a result, many algorithmic and architectural enhancements have been proposed to solve this problem, but at the cost of reduced sensitivity in the algorithms or significant expense in hardware, respectively. Hence, there exists a need to enhancement. The researchers applied divide and conquer strategy to solve its computational time drawback. In handling large deletion problem, incremental gap alignment was used to solve missed hits of match and consider the large gap brought by the deletion. Finally, the researchers compared the enhanced algorithm with the original Smith-Waterman. As for the result, the enhanced algorithm performs faster by up to 75 percent making its complexity to O (mn/t). In handling large deletion and missed data in the matrix, the enhanced algorithm improved its way in handling the subsequence and collects all information for the results to be outputted to handle large deletion and missed data in the matrix.