000			03406nam a2200301Ia 4500
001			76934
003			ft6136
005			20251107094600.0
008			190311n 000 0 eng d
040			_erda
041			_aengtag
050			_aQA76.9 M34 2013
082			_a.
100			_aRegine B. Magbiray and Antonio S. Ronda Jr.
245		0	_aAn enhancement of the smith -waterman algorithm applied in query by humming for music information retrieval
264			_a. _b. _cc2013
300			_bUndergraduate Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2013.
336			_b. _atext _2rdacontent
337			_30 _b. _aunmediated _2rdamedia
338			_30 _b. _avolume _2rdacarrier
505			_aABSTRACT: 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.
506			_a5
520			_aABSTRACT: 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.
526			_aF
540			_a5
655			_a.
942			_alcc _cMS _2ddc
999			_c25390 _d25390