APPROXIMATE MATCHING USING INTERVAL JUMPING SEARCHING ALGORITHMS FOR DNA SEQUENCES

Abstract

In this paper, a novel algorithm for approximate pattern matching from multiple DNA or amino acid sequences is designed. To improve efficiencies in approximate matching, interval jumping searching algorithms and voting mechanism are combined and applied in this system. Since k-mismatch problem of DNA or amino acid sequences from the giant genomic database is usually time consuming, we developed a parametric encoding methodology to search tolerant sub-strings and reduce the time complexity. In this paper, we have shown that the system can rapidly identify potential binding motifs for the transcription factor, such as GAL4 in the promoter regions of gal4 and gal6, which are neither predicted nor demonstrated to be regulated by GAL4 previously.