A Graph-based Approach To Weak Motif Detection

With the beginning of the Human Genome Project and the development of modern biotechnology, people accumulate numerous data about biological information, which provide foundation for exploring the life secret. Sequence analysis becomes an important research field in bioinformatics. Motif is an expression of life password, detecting of motifs in biological sequences has become a central problem in computational biology. Besides, motif discovery is an NP-complete problem. People have already explored a number of effective algorithms, but these algorithms have some limitations more or less, for instant, they are inapplicable to the recognition of weak motifs in noisy datasets, where only a fraction of the sequences may contain motif instances. Therefore, to study more effective algorithms has become a major issue in motif discovery in biological sequences, and. drawn increasingly attention.This paper presents a graphical approach to deal with the real biological sequences, which are noisy in nature, and find potential weak motifs. The approach converts the sequences database to a series of sub-graph under some restrictions, the motif instance can be represented by the vertexes of clique in the sub-graph. The consensus motif can be got through the clique finding in the sub-graph. The theoretical analysis and the experimental results on the synthetic and real data show that this algorithm can detect the weak motif in noisy data sets efficiently with better performance than other algorithms and can be applied to practical motif discovery problem.