Constraint based method for finding motifs in DNA sequences

Abstract

Pattern discovery in unaligned DNA sequences is a fundamental problemin both computer science and molecular biology. It has important applicationsin locating regulatory sites and drug target identification. Thisthesis introduces two novel motif discovery algorithms based on the use ofconstraint mechanism and constraint rules respectively. The key idea isto convert sets of similar substrings on the DNA sequences into patterns,as early as possible, using constraint mechanism or constraint rules. Theadvantages are two folds. Firstly, the approach generates limited numberof patterns while still guaranteeing that the actual motifs are containedin the pattern set. Secondly, the procedure for deriving patterns is verycost-eA?ective since it can be considered as that we use many a??look aheada??to speed up the procedure. Therefore, the algorithms have the advantagesof the high sensitivity of pattern-driven algorithms as well as the efficiencyof sample-driven algorithms.