An Efficient SDA Algorithm For Motif Discovery

Since the 90's in the 20th century, there is a great breakthrough in the progress of life science research. With the beginning of the Human Genome Project and the development of modern biotechnology, people accumulate a lot of data about biological information, which provide foundation for exploring the life secret. Sequence analysis becomes an important research field in bioinformatics. Motif discovery is the key problem in sequence analysis, which relates to many biological problems such as gene finding, transcription factor binding site finding and promoter finding. It gets the characteristic motif hided in the sequence by finding the similar segment in the different sequences. In recent years, some effective algorithms have been developed for motif discovery. Unfortunately, with the expansion of the data scale, many algorithms are unable to solve the NP-complete problem. So, it has become an important problem for people to study effective algorithms for motif discovery. Also, it has attracted more and more attentions in the world.In this thesis, we focus on the algorithm for motif discovery. We introduce the motif discovery problem and provide a detailed analysis to the existing motif discovery algorithms. Also, we present an efficient SDA exhaustive searching algorithm for motif discovery. Firstly, we convert the large-scale sequence data sets to a series of sub-graph based on the idea of divide and conquer algorithm. Then we convert the motif discovery problem into the clique finding in sub-graph. We adopt depth first search strategy with trace back in a graph for clique finding. Theoretical analysis and experimental results show the algorithm has better performance than other algorithms and can be applied to practical motif discovery problem.