A Cluster And Clique Refinement Approach To Motif Discovery

Expression of genes in organisms is usually finished with the aid of regulationprotein and the regulatory sites in DNA; the regulatory cites are usually upstream tothe regulatory regions, and conservative, which is called motif. As a result, motif dis-covery is significant on further research on gene regulatory mechanisms and findingBiological function sites. Therefore, motif discovery is one of the main research fieldsin bioinformatics. It is the core of Computational Biological and the hot research issuesin recent years.This paper introduces the background and significance of motif discovery, the re-presentation and evaluation standard of motif, the definition of motif discovery, and thecurrent situation of motif discovery. Then this paper proposes a cluster and clique re-finement approach to motif discovery (CCRMD) to solve the problem of motif discov-ery, its basic idea is to use cluster algorithm based on information entropy to obtain aseries of candidate motif instance sets(each set is a cluster), then change each candidatemotif instance set into a graph, and use the algorithm of finding all cliques of a graphto obtain a collection of similar strings which meets certain conditions for each candi-date motif instance set, then find motif instances in the input sequences according tothe homologous sequences of each collection of strings, finally obtain the motif.Experimental results demonstrate that CCRMD performs well on both simulatedand biological samples. The deficiency of this thesis is that CCRMD only solve theproblem with the assumption of exactly one occurrence (of motif instance) per se-quence, however, CCRMD can make out the more complex problem after improve-ment.