An Iterative Method For DNA Sequence Motif Identification

DNA Sequence motifs are becoming increasingly important in the analysis of gene regulation, and the identification of motif in DNA sequences is a hot issue in computational biology. In this thesis, we introduce the problem of motif identification and propose a new method for motif identification. The main contents of the thesis are arranged as follows:Chapter1is the introduction part where we briefly introduce the biological background, the significance of motif identification problem and the state of the art in motif identification algorithms.Chapter2provides a biological introduction to gene expression including transcription and translation, and gene regulation including transcription factor and its binding sites.Chapter3describes the problem of motif identification in detail and introduces the motif representation including consensus sequence representation, matrix representation and logo representation. The evaluation function including IC, consensus score and total fitness score are also introduced.Chapter4describes several methods used in motif identification, which are GA, ACO, Gibbs Samper and its generalizations.Chapter5contains the main material of this paper. In this chapter, we propose an iterative method that employs the general GA framework and computes the motif from the shot motif length to the standard length with the operation of mutation in GA and a new operation called plus-one proposed by us. The experiment results on simulated data and real biological data show that the obtained motifs are consistent with the real ones. Moreover, our method gets higher score than the other three methods, Gibbs Sampler, GA and GARPSGARPS in terms of the data CRP.