Discovering Motifs in Ranked Lists of DNA Sequences
[['This paper examines the problem of discovering “interesting” sequence motifs in biological sequence data .', 'A widely accepted and more formal definition of this task is: given a target set and a background set of sequences ( or a background model ) , identify sequence motifs that are enriched in the target set compared with the background set .', 'The purpose of this paper is to extend this formulation and to make it more flexible so as to enable the determination of the target and background set in a data driven manner .', 'Discovery of sequences or attributes that are enriched in a target set compared with a background set ( or model ) has become increasingly useful in a wide range of applications in molecular biology research .', 'For example , discovery of DNA sequence motifs that are overabundant in a set of promoter regions of co-expressed genes ( determined by clustering of expression data ) can suggest an explanation for this co-expression .', 'Another example is the discovery of DNA sequences that are enriched in a set of promoter regions to which a certain transcription factor ( TF ) binds strongly , inferred from chromatin immuno-precipitation on a microarray ( ChIP–chip ) [1] measurements .', 'The same principle may be extended to many other applications such as discovery of genomic elements enriched in a set of highly methylated CpG island sequences [2] .', 'Due to its importance , this task of discovering enriched DNA subsequences and capturing their corresponding motif profile has gained much attention in the literature .', 'Any approach to motif discovery must address several fundamental issues .', 'The first issue is the way by which motifs are represented .', 'There are several strategies for motif representation: using a k-mer of IUPAC symbols where each symbol represents a fixed set of possible nucleotides at a single position ( examples of methods that use this representation include REDUCE [3] , YMF [4 , 5] , ANN-SPEC [6] , and a hypergeometric-based method [7] ) or using a position weight matrix ( PWM ) , which specifies the probability of observing each nucleotide at each motif position ( for example MEME [8] , BioProspector [9] , MotifBooster [10] , DME-X [11] , and AlignACE [12] ) .', 'Both representations assume base position independence .', 'Alternatively , higher order representations that capture positional dependencies have been proposed ( e . g . , HMM and Bayesian networks motif representations [13] ) .', 'While these representations circumvent the position independence assumption , they are more vulnerable to overfitting and lack of data for determining model parameters .', 'The method described in this paper uses the k-mer model with symbols above IUPAC .', 'The second issue is devising a motif scoring scheme .', 'Many strategies for scoring motifs have been suggested in the literature .', 'One simple yet powerful approach uses the hypergeometric distribution for identifying enriched motif kernels in a set of sequences and then expanding these motifs using an EM algorithm [7] .', 'The framework described in this paper is a natural extension of the approach of [7] .', 'YMF [4 , 5] is an exhaustive search algorithm which associates each motif with a z-score .', 'AlignACE [12] uses a Gibbs sampling algorithm for finding global sequence alignments and produces a MAP score .', 'This score is an internal metric used to determine the significance of an alignment .', 'MEME [8] uses an expectation maximization strategy and outputs the log-likelihood and relative entropy associated with each motif .', 'Once a scoring scheme is devised , a defined motif search space is scanned ( either heuristically or exhaustively ) and motifs with significantly high scores are identified .', 'To determine the statistical significance of the obtained scores , many methods resort to simulations or ad hoc thresholds .', 'Several excellent reviews narrate the different strategies for motif detection and use quantitative benchmarking to compare their performance [14–18] .', 'A related aspect of motif discovery , which is outside the scope of this paper , focuses on properties of clusters and modules of TF binding sites ( TFBS ) .', 'Examples of approaches that search for combinatorial patterns and modules underlying TF binding and gene expression include [19–23] .', 'One issue of motif discovery that is often overlooked concerns the partition of the input set of sequences into target and background sets .', 'Many methods rely on the user to provide these two sets and search for motifs that are overabundant in the former set compared with the latter .', 'The question of how to partition the data into target and background sets is left to the user .', 'However , the boundary between the sets is often unclear and the exact choice of sequences in each set arbitrary .', 'For example , suppose that one wishes to identify motifs within promoter sequences that constitute putative TFBS .', 'An obvious strategy would be to partition the set of promoter sequences into target and background sets according to the TF binding signal ( as measured by ChIP–chip experiments ) .', 'The two sets would contain the sequences to which the TF binds “strongly” and “weakly , ” respectively .', 'A motif detection algorithm could then be applied to find motifs that are overabundant in the target set compared with the background set .', 'In this scenario , the positioning of the cutoff between the strong and weak binding signal is somewhat arbitrary .', 'Obviously , the final outcome of the motif identification process can be highly dependent on this choice of cutoff .', 'A stringent cutoff will result in the exclusion of informative sequences from the target set while a promiscuous cutoff will cause inclusion of nonrelevant sequences—both extremes hinder the accuracy of motif prediction .', 'This example demonstrates a fundamental difficulty in partitioning most types of data .', 'Several methods attempt to circumvent this hurdle .', 'For example , REDUCE [3] uses a regression model on the entire set of sequences .', 'However , it is difficult to justify this model in the context of multiple motif occurrence ( as explained below ) .', 'In other work , a variant of the Kolmogorov-Smirnov test was used for motif discovery [24] .', 'This approach successfully circumvents arbitrary data partition .', 'However , it has other limitations such as the failure to address multiple motif occurrences in a single promoter , and the lack of an exact characterization of the null distribution .', 'Overall , the following four major challenges in motif discovery still require consideration: ( c1 ) the cutoff used to partition data into a target set and background set of sequences is often chosen arbitrarily; ( c2 ) lack of an exact statistical score and p-value for motif enrichment .', 'Current methods typically use arbitrarily set thresholds or simulations , which are inherently limited in precision and costly in terms of running time; ( c3 ) a need for an appropriate framework that accounts for multiple motif occurrences in a single promoter .', 'For example , how should one quantify the significance of a single motif occurrence in a promoter against two motif occurrences in a promoter ?', 'Linear models [3] assume that the weight of the latter is double that of the former .', 'However , it is difficult to justify this approach since biological systems do not necessarily operate in such a linear fashion .', 'Another issue related to motif multiplicity is low complexity or repetitive regions .', 'These regions often contain multiple copies of degenerate motifs ( e . g . , CA repeats ) .', 'Since the nucleotide frequency underlying these regions substantially deviates from the standard background frequency , they often cause false-motif discoveries .', 'Consequently , most methods mask these regions in the preprocessing stage and thereby lose vital information that might reside therein; ( c4 ) criticism has been made over the fact that motif discovery methods tend to report presumably significant motifs even when applied on randomly generated data [25] .', 'These motifs are clear cases of false positives and should be avoided .', 'In this paper we describe a novel method that attempts to solve the above-mentioned four challenges in a principled manner .', 'It exploits the following observation: data often lends itself to ranking in a natural manner , e . g . , ranking sequences according to TF binding signal: ranking according to CpG methylation signal , ranking according to distance in expression space from a set of co-expressed genes , ranking according to differential expression , etc .', 'We exploit this inherent ranking property of biological data in order to circumvent the need for an arbitrary and difficult-to-justify data partition .', 'Consequently , we propose the following formulation of the motif finding task: given a list of ranked sequences , identify motifs that are overabundant at either end of the list .', 'Our solution employs a statistical score termed mHG ( minimal hypergeometric ) [26] .', 'It is related to the concept of rank-imbalanced motifs , which are sequence motifs that tend to appear at either end of a ranked sequence list .', 'In previous work [26] , the authors used mHG to identify sequence motifs in expression data .', 'We use this simple yet powerful approach as the starting point for our study .', 'The rest of this paper is divided into two main parts , each of which is self-contained: in the Results we briefly outline our method and describe new biological findings that were obtained by applying this method to biological data .', 'We address challenge ( c4 ) by testing the algorithm on randomly ranked real genomic sequences .', 'In the Methods , we describe the mHG probabilistic and algorithmic framework and explain how we deal with challenges ( c1 ) – ( c3 ) .'], ['Based on the mHG framework , we developed a software tool termed DRIM ( discovery of rank imbalanced motifs ) for motif identification in DNA sequences .', 'A flow chart of DRIM is provided in Figure', '1 . The formal introduction and details of the mHG statistics are given in Methods .', 'However , to facilitate the explanation and interpretation of our biological results , we begin with a brief description of the method .', 'Suppose we are given a set of DNA sequences and some measured signal associated with each sequence .', 'We rank the sequences according to the signal .', 'Now , given a sequence motif , we wish to assess whether that motif tends to appear more often at the “top” of a list compared with the “remainder” of the list .', 'The mHG score captures this type of motif significance .', 'More precisely , the mHG score reflects the surprise of seeing the observed density of motif occurrences at the top of the list compared with the rest of the list under the null assumption that all configurations of motif occurrences in the list are equiprobable .', 'A unique feature of the mHG statistics is that the cutoff between the top and the rest of the list is chosen in a data-driven manner so as to maximize the motif enrichment .', 'This is done by computing the motif enrichment over all possible set partitions and identifying the cutoff at which maximal statistical significance is observed .', 'The search for this optimal cutoff introduces a multiple testing problem .', "To solve this without resorting to multiple testing corrections , which diminish the score's sensitivity , we provide a novel algorithm for computing the exact p-value of mHG scores ( see Methods , Calculating the p-value of the mHG score ) .", 'This eliminates the need to resort to simulations or exhaustively calculated tables .', 'Our method also includes a new approach to modeling motif multiplicity by incorporating a multidimensional hypergeometric framework ( see Methods , Multidimensional mHG score ) .', 'Unlike some models , which assume linearity ( e . g . , that two binding motifs have twice the binding capacity as one motif ) , our model does not make such pre-assumptions .', 'Instead , the degree of surprise is adjusted for each motif according to its own occurrence multiplicity distribution .', 'DRIM scans through a motif space , computes the mHG p-value of these motifs and reports the significant ones ( see Methods , The DRIM software ) .', 'We begin by testing our method on synthetically generated clear-cut positive and negative control cases .', 'We do this to verify that DRIM accurately identifies motifs in well-characterized and experimentally verified examples and at the same time avoids false identification of motifs in randomly ordered genomic sequences .', 'The latter objective is of particular importance since the issue of false identification has been mentioned as one of the main shortcomings of motif discovery approaches .', 'For example , in a previous study , six different motif discovery applications were used to search for TFBS motifs [25] .', 'Each of the programs attempted to measure the significance of its results using one or more enrichment scores .', 'The authors report that the applications outputted high-scoring motifs even when applied to random selections of intergenic regions .', 'A different paper reports clusters of genes whose expression patterns correlate to the expression of a particular TF [27] .', 'These clusters were then analyzed for enriched motifs .', 'Again , the authors report that random sets , with sizes matching those of the real clusters , contained a large number of motifs with significant scores .', "To test our method's false-prediction rate , we performed the following negative control experiment: five different random permutations of ChIP–chip data were generated by randomly selecting 400 promoters and randomly permuting their ranks .", 'DRIM was then applied to these ranked lists and scanned more than 100 , 000 different motifs in each one .', 'None of the motifs that were scanned had a significant corrected mHG p-value <10−3 .', 'Note that to get the corrected p-values , two levels of multiple test corrections are performed: correcting for the number motifs that are tested; and correcting for multiple cutoffs that are tested as part of the mHG optimization process .', 'How do the p-values of random motifs compare with those of true biological motifs ?', 'To test this , we chose five TFs ( BAS1 , GAL4 , CBF1 , INO2 , and LEU3 ) whose motif binding sites are well-characterized and experimentally verified .', 'We applied DRIM to the ChIP–chip data of these TFs as reported in [25] .', 'In all instances , the true motifs were identified with corrected p-values of 10−6 , 10−9 , 10−76 , 10−18 , and 10−8 , respectively .', 'A comparison of the p-value distribution of the motifs in the randomly ordered sequences with that of the verified TFBS motifs is given in Figure S3 .', 'In all instances the true TFBS motifs were predicted with p-values that were several orders of magnitude more significant than the best p-value of a motif in the randomly permuted data .', 'This indicates that the enrichment signals of true TFBS , as captured by the mHG p-value , are clearly distinct from the signals we expect to find in random rankings of genomic sequences .', 'To further test the effectiveness of our method , we used it for identification of TFBS in yeast by applying it to the Harbison and Lee–filtered ChIP–chip datasets [25 , 28] , containing measurements of 207 TF binding experiments in several conditions ( for details regarding dataset-filtering see Methods ) .', 'Interestingly , we observed that in many of these datasets longer intergenic regions are biased toward stronger TF binding .', 'We elaborate on this sequence length bias in the Methods section and in Figure S1 .', 'In each of the ChIP–chip experiments , we ranked the intergenic regions according to the TF binding signal ( we use the p-value of enrichment for the sequence represented on the array ) .', 'This was used as input for DRIM , which then searched for motifs that tend to appear densely at the top of the ranked lists .', "If such a motif does exist , with a p-value less than 10−3 , then we hypothesize that it is biologically significant and that it contributes to the TF's binding , either directly or indirectly .", 'The results on the Harbison filtered dataset are summarized in Table S2 .', 'A TF was assigned a motif if such was found in at least one condition .', 'We compared the DRIM predictions with previously reported TFBS discoveries in ChIP–chip that incorporated predictions of six other motif discovery methods and conservation data [25] .', 'The results of this comparison are summarized in Figure', '2 . Overall , DRIM identified 50 motifs that were not picked up by the six other methods as reported in [25] .', 'We further investigated these putative TFBS for additional evidence that they are biologically meaningful .', 'First , we found that seven of them ( ASH1 , GCR1 , HAP2 , MET31 , MIG1 , RIM101 , and RTG3 ) are in agreement with previously published results that are based on experimental techniques other than ChIP–chip .', 'Second , we compared them with a list of conserved regulatory sites in yeast that was recently inferred using conservation-based algorithms [29] .', 'Ten of our putative TFBS match these conserved sites ( ARG81 , ARO80 , ASH1 , CRZ1 , DAL81 , HAP2 , IME1 , MET31 , MIG1 , and RTG3 ) .', 'Taken together , these findings provide a strong indication that at least some of the new motifs identified by DRIM are true biological signals .', 'In the following subsections , we focus on a few of these putative TFBS ( see Figure 3 ) and present additional evidence that supports their biological role .', 'We use these findings to discover new interactions in the yeast genetic regulatory network .', "To examine our method's ability to predict sequence motifs that stem from data other than TF binding , DRIM was applied to a dataset containing the human cancer cell line–methylated CpG islands ( for dataset details , see Methods ) to seek for motifs that are enriched in hypermethylated regions .", 'The promoters were ranked according to methylation signal , with hypermethylated promoters at the top .', 'Note that different replicates of the same cell line may yield different ranking of the promoters .', 'DRIM identified significantly enriched motifs in each of the four cancer cell lines .', 'Table 1 shows all the motifs that were independently discovered in at least two different replicates of the same experiment or that are in agreement with previous work [2] .', 'Overall , DRIM discovered 13 motifs: ten novel motifs and three that have been previously predicted in hypermethylated CpG island promoters in the same cancer cell lines [2] .', 'Some of these motifs have also been independently identified in methylated CpG regions of other cell lines [39 , 40] .', 'Interestingly , nine of the novel ten motifs were independently identified in DNA regions to which the proteins of the Polycomb complex bind [41–43] .', 'The Polycomb complex is involved in gene repression through epigenetic silencing and chromatin remodeling , a process that involves histone methylation .', 'The fact that these two distinct key epigenetic repression systems , namely histone methylation and CpG methylation , bind to regions that share a similar set of sequence motifs suggests they are linked .', 'To further establish this link we applied DRIM to Polycomb complex bound promoters in human embryonic fibroblasts [44] .', 'We found four motifs that are similar to the CpG methylation motifs ( Table 1 ) .', 'Our findings are consistent with a recent paper that showed that the EZH2 Polycomb protein binds methyltransferases via the Polycomb complex [45] .', 'Most of the motifs we found are similar across more than one type of cancer cell line , e . g . , variants of the GCTGCT motif appear in Caco-2 , PC3 , and Polyp1 cancer cell lines .', 'This suggests that the same DNA binding factors are involved in CpG methylation of different types of cancers .', 'It is also important to note that some of the motifs we discovered are G–C rich .', 'The enrichment of these motifs may be partially attributed to the G–C content bias that is found in CpG methylation data .', 'The DRIM motif identification process can be used not only to identify novel motifs but also to partition the data in a biologically meaningful manner .', 'In [2] the authors used a fixed threshold on the methylation signal ( p-value < 0 . 001 ) to partition the dataset .', 'Consequently , they identified 135 hypermethylated promoters .', 'A data-driven partition would be to use the threshold that yielded the maximal motif enrichment .', 'For example , in the Caco2 cell line , we identified the same motif as in the previous work [2] .', 'However , the motif maximal enrichment was found in the top 209 promoters ( an increase of 54% in target set size ) .', "Human TFBS tend to be longer and “fuzzier” than TFBS of lower eukaryotes , and it is important to evaluate our method's performance on such motifs .", 'To this end , we applied DRIM to the ChIP–chip experiments of HNF1α , HNF4α , HNF6 in liver and pancreas islets [46] , as well as to that of CREB [47] .', 'For each of the TFs , we generated a list of sequences containing 1 , 000 bases upstream and 300 downstream of the transcription start site ( TSS ) .', 'We ranked the list according to the TF ChIP–chip signal and used it as input to DRIM .', 'DRIM successfully detected the TFBS of these TFs that are reported in TRANSFAC with extremely significant p-values: HNF1α liver—GTTAMWNATT ( p = 10−8 ) , HNF4α Islets—SCGGAAR ( p = 10−53 ) , HNF6 Liver—ATCRAT ( p = 10−57 ) , and HNF6 Islets—ATCRAT ( p = 10−61 ) .', 'In the CREB experiments we identified the palindromic motif TGACGTCA ( p = 10−16 ) , which is known to bind CREB [47] .', 'Three properties of the mHG enrichment score embodied in DRIM offer advantages over other motif discovery methods: the dynamic cutoff , the rigorous control over false positives , and the motif multiplicity model .'], ['In this paper we examine the problem of discovering “interesting” motif sequences in biological sequence data .', 'While this problem has often been regarded as tantamount to discovering enriched motifs in a target set versus a background set , we point out an inherent limitation to this formulation of the problem .', 'Specifically , in most cases , biological measurement data does not lend itself to a single , well-substantiated partition into target and background sets .', 'It does , however , lend itself to ranking in a natural manner .', 'Our approach exploits this natural ranking and attempts to solve challenges ( c1 ) – ( c4 ) ( see Introduction , Open challenges in motif discovery ) .', 'To address challenge ( c1 ) , instead of choosing an arbitrary cutoff for set partition , we search for a cutoff that partitions the data in a way that maximizes the motif enrichment .', 'We present evidence that shows that the flexible mHG cutoff outperforms the rigid cutoff .', 'One example of this is shown in Figure 5 , where the flexible cutoff yields better results for all the tested TFs .', 'Another example of the advantage of a flexible cutoff is the two motifs detected in three TFs involved in the sulfur amino acid pathway ( Met4 , Met31 , and Met32 ) .', 'Figure 7 shows the number of motif occurrences in each of the top 59 promoters that were ranked according to Met32 binding signal ( data from [25] ) .', 'The motifs are highly frequent in the top 18 promoters , after which a strong drop in motif frequency is observed .', 'DRIM identifies this , and partitions the set accordingly .', 'In comparison , relying on the standard cutoff of 10−3 results in a target set of the top 48 promoters , most of which do not contain this motif .', 'The signal-to-noise ratio is thus diminished , which may explain why these motifs were previously overlooked .', 'While the flexible cutoff is advantageous in many instances , it also introduces a multiple testing problem .', 'To circumvent this ( without resorting to strict multiple testing corrections that may mask the biological signal ) , we developed an efficient algorithm for computing the exact p-value of a given mHG score .', 'This addresses challenge ( c2 ) .', 'Another advantage of this exact statistical score is its straightforward biological interpretation: the mHG p-value reflects the probability of seeing the observed density of motif occurrences at the top of the ranked list under the null assumption that all configurations of motif occurrences are equiprobable .', 'Motif multiplicity is often indicative of biological function .', 'It is therefore paramount to incorporate this type of information into the motif prediction model .', 'We do so in a data-driven manner by developing the multi-mHG framework , thus addressing challenge ( c3 ) .', 'The advantages of the multi-mHG model over the binary model are presented in Results , Binary versus multidimensional enrichment .', 'False prediction of motifs in randomly generated data is often mentioned as one of the drawbacks of computational motif discovery [25] .', 'We report the testing of DRIM on random permutations of ranked sequences .', 'When tested on more than 100 , 000 motifs , DRIM did not identify any significant motifs , thus addressing challenge ( c4 ) .', 'The low false-positive prediction of our method is mainly attributed to the fact that it is based on rigorous statistics and relies on an exact p-value .', 'Another important issue that still requires consideration is the characterization of the motif search space .', 'In this study we performed an exhaustive scanning of a restricted motif space ( containing ∼105 motifs ) followed by a heuristic search for larger motifs .', 'However , the motif search space can be further extended to include motifs that are longer , “fuzzier , ” or more complex .', 'Additional considerations such as the distance of the motif from the transcription start site may be taken into account as well as logical relations between different motifs ( e . g . , “OR , ” “AND” operations ) .', 'It is clear that many of these features are required to correctly model complex regulation patterns that are observed in higher eukaryotes .', 'Two inherent limitations need to be considered when extending the search space: first , as the size of the motif search space increases , the problem of efficiently searching the defined space becomes more acute in terms of running time .', 'Second , since the size of the search space is virtually endless , the problem of multiple testing rapidly erodes the signal-to-noise ratio , requiring an appropriate refinement of the statistical models .', 'To test our method , we constructed a dataset containing ChIP–chip experiments of 203 putative TFs in Saccharomyces cerevisiae [25 , 28] .', 'Surprisingly , we discovered a significant length bias in roughly one-third of these experiments .', 'One possible explanation for this phenomenon is nonspecific binding between TFs and DNA , which causes longer sequences to bind more TFs .', 'This explanation is also consistent with the “TF sliding hypothesis” [48] .', 'Why only some TFs exhibit this length bias binding tendency remains an open question .', 'To avoid false positives due to this phenomenon , we opted to filter out all ChIP–chip experiments that had significant length bias .', 'Future work should address this point and focus on developing statistics that are insensitive to this type of bias .', 'We analyzed the filtered dataset using DRIM and report novel putative TFBS motifs .', 'Additional evidence that indicates the newly discovered motifs are biologically functional was also presented .', 'One interesting finding is that the Aro80 motif we identified , which exists only in seven copies throughout the entire yeast genome , resides in Aro80′s own promoter .', 'This finding suggests that Aro80 regulates its own transcription by binding to its own promoter .', 'Additionally , three GATA binding sites that reside in the Aro80 promoter adjacent to the motif occurrence lead us to speculate that Aro80′s putative self binding is inhibited by competing GATA binding factors ( for details see Figure 4B ) .', 'Another interesting observation is the CA repeat motifs , which we identified in seven different yeast TFs as well as in human DNA methylation .', 'This type of low complexity motifs have so far been mostly ignored or filtered out by other computational methods .', 'By contrast there is no need to resort to this type of artificial filtering when using the mHG statistics .', "Our findings in yeast suggest that for certain TFs there is a significant correlation between a sequence's capacity to bind a TF and the presence of a CA repeat in the sequence .", 'This supports a previous hypothesis that CA repeats alter the structure of DNA and thus contribute to TF binding [34] .', 'Our findings constitute concrete evidence of this phenomenon and suggest it may be more frequent than previously appreciated .', 'We also applied DRIM to high-throughput measurements of methylated CpG islands [2] in human cancer cells , in order to try to identify motifs that are enriched in hypermethylated regions .', 'Interestingly , we identified GA and CA repeat elements as highly enriched in methylated CpG regions of four different cancer cell lines .', 'This is in agreement with previous studies of CpG methylated regions in other cell lines [39 , 40] .', 'It is interesting to ask whether these repeat elements play some active role in CpG methylation .', 'In [40] the authors give statistical argumentation against such a hypothesis .', 'Instead , they hypothesize that CA ( or TG ) repeats are caused by an increased mutation rate of methylated CpGs that are deaminated into TpGs .', 'Even if true , this still does not explain the enrichment of the GA repeats .', 'Further experimental and bioinformatic interrogation of this point is therefore called upon .', 'Overall , DRIM discovered ten novel motifs in methylated CpG regions .', 'Strikingly , nine of them are similar to DNA sequence elements that bind the Polycomb complex in Drosophila and/or human [41 , 42 , 44] .', 'The Polycomb complex is involved in epigenetic silencing via histone methylation .', 'The suggested link between histone methylation and CpG methylation is in agreement with recent work that demonstrated the EZH2 protein interacts with DNA methyltransferases via the Polycomb complex [45] .', 'We also note that the DNA sequence motifs of the two pathways were conserved in Drosophila and human , which is complementary to the observation that the Polycomb proteins are evolutionarily conserved [44 , 49] .', 'Many of the motifs we found in the CpG methylation data are similar across different types of cancer cell lines .', 'This may suggest that the CpG methylation mechanism is orchestrated by DNA binding factors that are similar in different types of cancer cell lines .', 'Perhaps the most important conclusion that can be drawn from this study is that looking at biological sequence data in a ranked manner rather than using an arbitrary fixed cutoff to partition the data enables the detection of biological signals that are otherwise overlooked .', 'This suggests that other motif detection methods that rely on fixed cutoffs may benefit from dynamic partitioning .', 'While the effectiveness of our approach was demonstrated on ChIP–chip and methylation data , it can also be applied to a wide range of other data types such as expression data or GO analysis .', 'The DRIM application is publicly available at http://bioinfo . cs . technion . ac . il/drim .'], ['In this subsection we introduce the basics of the mHG statistics , and demonstrate how it can be applied in a straightforward manner to eliminate the need for an arbitrary choice of threshold .', 'To explain the biological motivation of mHG , consider the following scenario: suppose we have a set of promoter regions each associated with a measurement , e . g . , a TF binding signal as measured by ChIP–chip [1] .', 'We wish to determine whether a particular motif specified in IUPAC notation , say CASGTGW , is likely to be a TFBS motif .', 'We rank the promoters according to their binding signals—strong binding at the top of the list and the weak at the bottom ( Figure 1i ) .', 'Next , we generate a binary occurrence vector with one or zero entries dependent on whether or not the respective promoter contains a copy of the motif ( Figure 1ii ) .', 'For simplicity we ignore cases where a p
['Introduction', 'Results', 'Discussion', 'Materials and Methods', 'Supporting Information']
['Computational methods for discovery of sequence elements that are enriched in a target set compared with a background set are fundamental in molecular biology research .', 'One example is the discovery of transcription factor binding motifs that are inferred from ChIP–chip ( chromatin immuno-precipitation on a microarray ) measurements .', 'Several major challenges in sequence motif discovery still require consideration:', '( i ) the need for a principled approach to partitioning the data into target and background sets;', '( ii ) the lack of rigorous models and of an exact p-value for measuring motif enrichment;', '( iii ) the need for an appropriate framework for accounting for motif multiplicity;', '( iv ) the tendency , in many of the existing methods , to report presumably significant motifs even when applied to randomly generated data .', 'In this paper we present a statistical framework for discovering enriched sequence elements in ranked lists that resolves these four issues .', 'We demonstrate the implementation of this framework in a software application , termed DRIM ( discovery of rank imbalanced motifs ) , which identifies sequence motifs in lists of ranked DNA sequences .', 'We applied DRIM to ChIP–chip and CpG methylation data and obtained the following results .', '( i ) Identification of 50 novel putative transcription factor ( TF ) binding sites in yeast ChIP–chip data .', 'The biological function of some of them was further investigated to gain new insights on transcription regulation networks in yeast .', 'For example , our discoveries enable the elucidation of the network of the TF ARO80 .', 'Another finding concerns a systematic TF binding enhancement to sequences containing CA repeats .', '( ii ) Discovery of novel motifs in human cancer CpG methylation data .', 'Remarkably , most of these motifs are similar to DNA sequence elements bound by the Polycomb complex that promotes histone methylation .', 'Our findings thus support a model in which histone methylation and CpG methylation are mechanistically linked .', 'Overall , we demonstrate that the statistical framework embodied in the DRIM software tool is highly effective for identifying regulatory sequence elements in a variety of applications ranging from expression and ChIP–chip to CpG methylation data .', 'DRIM is publicly available at http://bioinfo . cs . technion . ac . il/drim .']
['A computational problem with many applications in molecular biology is to identify short DNA sequence patterns ( motifs ) that are significantly overrepresented in a target set of genomic sequences relative to a background set of genomic sequences .', 'One example is a target set that contains DNA sequences to which a specific transcription factor protein was experimentally measured as bound while the background set contains sequences to which the same transcription factor was not bound .', 'Overrepresented sequence motifs in the target set may represent a subsequence that is molecularly recognized by the transcription factor .', 'An inherent limitation of the above formulation of the problem lies in the fact that in many cases data cannot be clearly partitioned into distinct target and background sets in a biologically justified manner .', 'We describe a statistical framework for discovering motifs in a list of genomic sequences that are ranked according to a biological parameter or measurement ( e . g . , transcription factor to sequence binding measurements ) .', 'Our approach circumvents the need to partition the data into target and background sets using arbitrarily set parameters .', 'The framework is implemented in a software tool called DRIM .', 'The application of DRIM led to the identification of novel putative transcription factor binding sites in yeast and to the discovery of previously unknown motifs in CpG methylation regions in human cancer cell lines .']
['mathematics', 'saccharomyces', 'homo (human)', 'computational biology']