| 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 secrety. But, how to extract useful biological knowledge from massive biological data and clarify the structure and function hided in them is an important research field in bioinformatics. The motif discovery technology is exactly one of the basic methods which reveal the biological meaning hided in the sequence. It gets the characteristic motif hided in the sequence by finding the similar segment in the different sequences. In recent years, people has presented some effective algorithms in the study of motif discovery algorithms, these algorithms have shown a better performance in solving the motif discovery problems under small data scale. However, along with the expansion of the data scale, many algorithms can not solve the motif discovery problems in this case. So, studying more effective algorithms for motif discovery in large scale has become an important region in the biosequence research and attracted more and more attentions in the world.In this thesis, we firstly review the motif models which are used in different kinds of motif discovery algorithms. Also, we study and compare the motif discovery algorithms based on different models. Then we present an approach for motif discovery based on the graph theory. The approach converts the sequences database to a series of sub-graph under some restrictions. If there is a kind of motif in database, the motif instance can be represented by the vertexes of clique in the sub-graph. The consensus motif can be got through the efficient clique finding in the sub-graph. Finally, we have theoretical analysis and experiment simulations, which show that the algorithm can find motif and have good performance in the sequences. |
PDF Full Text Request