Research And Implementation On An Algorithm Of The Limited Motif Discovery Problem

The motif is an important transcription regulatory element,or a common sequence fragment of a set of sequences.More often,it is the sequence associated with molecular function,structural properties,or family member,which mainly exist in proteins,RNA and DNA.The discovery of motif is of great significance to the study of gene expression.The discovery of motif is of great significance to the study of gene expression,and is a major research direction in bioinfomatics in the post gene era.At present,the motif discovery problems are mainly focused on find the transcription factor binding site motif discovery,that is,the sequence that has specific function and conservative in the given DNA sequence.At the same time,the restriction enzyme binding site discovery problem is also an important research point in the field of motif search.Different from the former,the latter problem added some limited conditions.The restriction enzyme binding site search problem refers to given two DNA sequence sets,positive set and negative set,specify the pattern P,at the same time,insure the instances of the motif which meet the pattern P can only appear in positive sequence set,and in the set of negative sequence cannot appear.For the completeness of the result,the reverse complementary sequences of the given sequences are also considered.Therefore,this problem can be considered as a kind of restricted motif discovery problem.According to the discovery of the restricted motif can deduce some new restriction enzymes,and according to the different exogenous DNA using corresponding enzyme destory the DNA structure to limit the invasion,which play the role of protect the information of original cell.At present,there have been a lot of transcription factor binding sites mining algorithms and the corresponding softwares,such as MEME,AlignACE,Sampler Gibbs,PMS series,etc.Most of these algorithms and its improved algorithms can well solve the problem of the transcription factor binding site discovery problems,but they cannot be directly used to restricted motif discovery problem.Therefore,in this paper,according to the demand of the special motif search problem,two kinds of algorithms are proposed,which are inverted index algorithm and L-PMS algorithm.Inverted index Algorithm first lists all instances I={I1...IN} of the given pattern P in the dictionary order,then contrast and verify each instance Ii.If the instance meet the requirements of appears in the positive sequence set and in negative sequence set does not appear,then the instance is the the final phantom to output.Algorithm L-PMS algorithm based on PMS8,algorithm PMS8 is one of a efficient algorithm of the planted motif search(PMS)problem.Algorithm L-PMS algorithm extend the algorithm of PMS8,which combined the plant instance(l,d)problem of PMS8 with the specified pattern can solve the positive and negative sequence set motif discovery problem very well.