A Guided Dynamic Programming Approach for Searching a Set of Similar DNA Sequences

A Rahman, M Nordin and Mohd Saman, Md Yazid and Ahmad, Aziz and M Tap, A Osman (2009) A Guided Dynamic Programming Approach for Searching a Set of Similar DNA Sequences. . Proc. of the 2nd International Conference on the Applications of Digital Information and Web Technologies. pp. 529-534. ISSN ISBN Print: 978-1-4244-4456-4

[img] Text
05273967.pdf
Restricted to Registered users only

Download (248Kb)

Abstract

Optimal estimation of similarity distance between DNA sequences is performed through alignment process. This optimal alignment process is done by using dynamic programming method which running in quadratic O(n×m) time complexity. Filtering process is a common technique introduced to improve this optimal alignment process. A filtering process applied in heuristic tools such as BLAST and FASTA consists of scanning the exact matches of subsequences in query sequence to the sequences in database. The main purpose of filtering is to discard the irrelevant subsequences from being performed for rigorous optimal alignment process. Differently, this paper addresses the technique of filtering the expected irrelevant sequences in database from being executed for rigorous optimal alignment process. An automaton-based algorithm is used to develop the filtering process proposed. A set of random patterns is generated from query sequence will placed in automaton machine before exact matching and scoring process is performed. Extensive experiments have been carried out on several parameters and the results show that the developed filtering technique removes the unrelated targeted sequences from being aligned with query sequence.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / Institute: Faculty of Informatics & Computing
Depositing User: Dr Mohd Nordin Abdul Rahman
Date Deposited: 03 Dec 2014 03:34
Last Modified: 08 Nov 2015 04:05
URI: http://erep.unisza.edu.my/id/eprint/1193

Actions (login required)

View Item View Item