MersV1, Pmc, Corpus, bibRecord, 000A90

MotifClick: prediction of cis-regulatory binding sites via merging cliques

Identifieur interne : 000A90 ( Pmc/Corpus ); précédent : 000A89; suivant : 000A91

MotifClick: prediction of cis-regulatory binding sites via merging cliques

Auteurs : Shaoqiang Zhang ; Shan Li ; Meng Niu ; Phuc T. Pham ; Zhengchang Su

Source :

BMC Bioinformatics [ 1471-2105 ] ; 2011.

RBID : PMC:3225181

Abstract

Background

Although dozens of algorithms and tools have been developed to find a set of cis-regulatory binding sites called a motif in a set of intergenic sequences using various approaches, most of these tools focus on identifying binding sites that are significantly different from their background sequences. However, some motifs may have a similar nucleotide distribution to that of their background sequences. Therefore, such binding sites can be missed by these tools.

Results

Here, we present a graph-based polynomial-time algorithm, MotifClick, for the prediction of cis-regulatory binding sites, in particular, those that have a similar nucleotide distribution to that of their background sequences. To find binding sites with length k, we construct a graph using some 2(k-1)-mers in the input sequences as the vertices, and connect two vertices by an edge if the maximum number of matches of the local gapless alignments between the two 2(k-1)-mers is greater than a cutoff value. We identify a motif as a set of similar k-mers from a merged group of maximum cliques associated with some vertices.

Conclusions

When evaluated on both synthetic and real datasets of prokaryotes and eukaryotes, MotifClick outperforms existing leading motif-finding tools for prediction accuracy and balancing the prediction sensitivity and specificity in general. In particular, when the distribution of nucleotides of binding sites is similar to that of their background sequences, MotifClick is more likely to identify the binding sites than the other tools.

Url:

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3225181

DOI: 10.1186/1471-2105-12-238
PubMed: 21679436
PubMed Central: 3225181

Links to Exploration step

PMC:3225181

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">MotifClick: prediction of <italic>cis</italic>
-regulatory binding sites via merging cliques</title>
<author><name sortKey="Zhang, Shaoqiang" sort="Zhang, Shaoqiang" uniqKey="Zhang S" first="Shaoqiang" last="Zhang">Shaoqiang Zhang</name>
<affiliation><nlm:aff id="I2">College of Computer and Information Engineering, Tianjin Normal University, 393 Bin Shui Xi Road, Tianjin, 300387, China</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Li, Shan" sort="Li, Shan" uniqKey="Li S" first="Shan" last="Li">Shan Li</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Niu, Meng" sort="Niu, Meng" uniqKey="Niu M" first="Meng" last="Niu">Meng Niu</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Pham, Phuc T" sort="Pham, Phuc T" uniqKey="Pham P" first="Phuc T" last="Pham">Phuc T. Pham</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Su, Zhengchang" sort="Su, Zhengchang" uniqKey="Su Z" first="Zhengchang" last="Su">Zhengchang Su</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">21679436</idno>
<idno type="pmc">3225181</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3225181</idno>
<idno type="RBID">PMC:3225181</idno>
<idno type="doi">10.1186/1471-2105-12-238</idno>
<date when="2011">2011</date>
<idno type="wicri:Area/Pmc/Corpus">000A90</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000A90</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">MotifClick: prediction of <italic>cis</italic>
-regulatory binding sites via merging cliques</title>
<author><name sortKey="Zhang, Shaoqiang" sort="Zhang, Shaoqiang" uniqKey="Zhang S" first="Shaoqiang" last="Zhang">Shaoqiang Zhang</name>
<affiliation><nlm:aff id="I2">College of Computer and Information Engineering, Tianjin Normal University, 393 Bin Shui Xi Road, Tianjin, 300387, China</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Li, Shan" sort="Li, Shan" uniqKey="Li S" first="Shan" last="Li">Shan Li</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Niu, Meng" sort="Niu, Meng" uniqKey="Niu M" first="Meng" last="Niu">Meng Niu</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Pham, Phuc T" sort="Pham, Phuc T" uniqKey="Pham P" first="Phuc T" last="Pham">Phuc T. Pham</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Su, Zhengchang" sort="Su, Zhengchang" uniqKey="Su Z" first="Zhengchang" last="Su">Zhengchang Su</name>
<affiliation><nlm:aff id="I1">Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>Although dozens of algorithms and tools have been developed to find a set of <italic>cis</italic>
-regulatory binding sites called a motif in a set of intergenic sequences using various approaches, most of these tools focus on identifying binding sites that are significantly different from their background sequences. However, some motifs may have a similar nucleotide distribution to that of their background sequences. Therefore, such binding sites can be missed by these tools.</p>
</sec>
<sec><title>Results</title>
<p>Here, we present a graph-based polynomial-time algorithm, MotifClick, for the prediction of <italic>cis</italic>
-regulatory binding sites, in particular, those that have a similar nucleotide distribution to that of their background sequences. To find binding sites with length <italic>k</italic>
, we construct a graph using some 2(<italic>k</italic>
-1)-mers in the input sequences as the vertices, and connect two vertices by an edge if the maximum number of matches of the local gapless alignments between the two 2(<italic>k</italic>
-1)-mers is greater than a cutoff value. We identify a motif as a set of similar <italic>k</italic>
-mers from a merged group of maximum cliques associated with some vertices.</p>
</sec>
<sec><title>Conclusions</title>
<p>When evaluated on both synthetic and real datasets of prokaryotes and eukaryotes, MotifClick outperforms existing leading motif-finding tools for prediction accuracy and balancing the prediction sensitivity and specificity in general. In particular, when the distribution of nucleotides of binding sites is similar to that of their background sequences, MotifClick is more likely to identify the binding sites than the other tools.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Kim, Hd" uniqKey="Kim H">HD Kim</name>
</author>
<author><name sortKey="Shay, T" uniqKey="Shay T">T Shay</name>
</author>
<author><name sortKey="O Shea, Ek" uniqKey="O Shea E">EK O'Shea</name>
</author>
<author><name sortKey="Regev, A" uniqKey="Regev A">A Regev</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Reed, Jl" uniqKey="Reed J">JL Reed</name>
</author>
<author><name sortKey="Famili, I" uniqKey="Famili I">I Famili</name>
</author>
<author><name sortKey="Thiele, I" uniqKey="Thiele I">I Thiele</name>
</author>
<author><name sortKey="Palsson, Bo" uniqKey="Palsson B">BO Palsson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Guhathakurta, D" uniqKey="Guhathakurta D">D GuhaThakurta</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Aerts, S" uniqKey="Aerts S">S Aerts</name>
</author>
<author><name sortKey="Thijs, G" uniqKey="Thijs G">G Thijs</name>
</author>
<author><name sortKey="Coessens, B" uniqKey="Coessens B">B Coessens</name>
</author>
<author><name sortKey="Staes, M" uniqKey="Staes M">M Staes</name>
</author>
<author><name sortKey="Moreau, Y" uniqKey="Moreau Y">Y Moreau</name>
</author>
<author><name sortKey="De Moor, B" uniqKey="De Moor B">B De Moor</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gelfand, Ms" uniqKey="Gelfand M">MS Gelfand</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Das, Mk" uniqKey="Das M">MK Das</name>
</author>
<author><name sortKey="Dai, Hk" uniqKey="Dai H">HK Dai</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sandve, Gk" uniqKey="Sandve G">GK Sandve</name>
</author>
<author><name sortKey="Drablos, F" uniqKey="Drablos F">F Drablos</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Macisaac, Kd" uniqKey="Macisaac K">KD MacIsaac</name>
</author>
<author><name sortKey="Fraenkel, E" uniqKey="Fraenkel E">E Fraenkel</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Liu, Xs" uniqKey="Liu X">XS Liu</name>
</author>
<author><name sortKey="Brutlag, Dl" uniqKey="Brutlag D">DL Brutlag</name>
</author>
<author><name sortKey="Liu, Js" uniqKey="Liu J">JS Liu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pavesi, G" uniqKey="Pavesi G">G Pavesi</name>
</author>
<author><name sortKey="Mereghetti, P" uniqKey="Mereghetti P">P Mereghetti</name>
</author>
<author><name sortKey="Zambelli, F" uniqKey="Zambelli F">F Zambelli</name>
</author>
<author><name sortKey="Stefani, M" uniqKey="Stefani M">M Stefani</name>
</author>
<author><name sortKey="Mauri, G" uniqKey="Mauri G">G Mauri</name>
</author>
<author><name sortKey="Pesole, G" uniqKey="Pesole G">G Pesole</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pevzner, Pa" uniqKey="Pevzner P">PA Pevzner</name>
</author>
<author><name sortKey="Sze, Sh" uniqKey="Sze S">SH Sze</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Olman, V" uniqKey="Olman V">V Olman</name>
</author>
<author><name sortKey="Xu, D" uniqKey="Xu D">D Xu</name>
</author>
<author><name sortKey="Xu, Y" uniqKey="Xu Y">Y Xu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Liang, S" uniqKey="Liang S">S Liang</name>
</author>
<author><name sortKey="Samanta, Mp" uniqKey="Samanta M">MP Samanta</name>
</author>
<author><name sortKey="Biegel, Ba" uniqKey="Biegel B">BA Biegel</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fratkin, E" uniqKey="Fratkin E">E Fratkin</name>
</author>
<author><name sortKey="Naughton, Bt" uniqKey="Naughton B">BT Naughton</name>
</author>
<author><name sortKey="Brutlag, Dl" uniqKey="Brutlag D">DL Brutlag</name>
</author>
<author><name sortKey="Batzoglou, S" uniqKey="Batzoglou S">S Batzoglou</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Marschall, T" uniqKey="Marschall T">T Marschall</name>
</author>
<author><name sortKey="Rahmann, S" uniqKey="Rahmann S">S Rahmann</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lawrence, Ce" uniqKey="Lawrence C">CE Lawrence</name>
</author>
<author><name sortKey="Altschul, Sf" uniqKey="Altschul S">SF Altschul</name>
</author>
<author><name sortKey="Boguski, Ms" uniqKey="Boguski M">MS Boguski</name>
</author>
<author><name sortKey="Liu, Js" uniqKey="Liu J">JS Liu</name>
</author>
<author><name sortKey="Neuwald, Af" uniqKey="Neuwald A">AF Neuwald</name>
</author>
<author><name sortKey="Wootton, Jc" uniqKey="Wootton J">JC Wootton</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hughes, Jd" uniqKey="Hughes J">JD Hughes</name>
</author>
<author><name sortKey="Estep, Pw" uniqKey="Estep P">PW Estep</name>
</author>
<author><name sortKey="Tavazoie, S" uniqKey="Tavazoie S">S Tavazoie</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Thijs, G" uniqKey="Thijs G">G Thijs</name>
</author>
<author><name sortKey="Lescot, M" uniqKey="Lescot M">M Lescot</name>
</author>
<author><name sortKey="Marchal, K" uniqKey="Marchal K">K Marchal</name>
</author>
<author><name sortKey="Rombauts, S" uniqKey="Rombauts S">S Rombauts</name>
</author>
<author><name sortKey="De Moor, B" uniqKey="De Moor B">B De Moor</name>
</author>
<author><name sortKey="Rouze, P" uniqKey="Rouze P">P Rouze</name>
</author>
<author><name sortKey="Moreau, Y" uniqKey="Moreau Y">Y Moreau</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Liu, X" uniqKey="Liu X">X Liu</name>
</author>
<author><name sortKey="Brutlag, Dl" uniqKey="Brutlag D">DL Brutlag</name>
</author>
<author><name sortKey="Liu, Js" uniqKey="Liu J">JS Liu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bailey, Tl" uniqKey="Bailey T">TL Bailey</name>
</author>
<author><name sortKey="Elkan, C" uniqKey="Elkan C">C Elkan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Redhead, E" uniqKey="Redhead E">E Redhead</name>
</author>
<author><name sortKey="Bailey, Tl" uniqKey="Bailey T">TL Bailey</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fauteux, F" uniqKey="Fauteux F">F Fauteux</name>
</author>
<author><name sortKey="Blanchette, M" uniqKey="Blanchette M">M Blanchette</name>
</author>
<author><name sortKey="Stromvik, Mv" uniqKey="Stromvik M">MV Stromvik</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Valen, E" uniqKey="Valen E">E Valen</name>
</author>
<author><name sortKey="Sandelin, A" uniqKey="Sandelin A">A Sandelin</name>
</author>
<author><name sortKey="Winther, O" uniqKey="Winther O">O Winther</name>
</author>
<author><name sortKey="Krogh, A" uniqKey="Krogh A">A Krogh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sinha, S" uniqKey="Sinha S">S Sinha</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Benos, Pv" uniqKey="Benos P">PV Benos</name>
</author>
<author><name sortKey="Bulyk, Ml" uniqKey="Bulyk M">ML Bulyk</name>
</author>
<author><name sortKey="Stormo, Gd" uniqKey="Stormo G">GD Stormo</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zhang, S" uniqKey="Zhang S">S Zhang</name>
</author>
<author><name sortKey="Xu, M" uniqKey="Xu M">M Xu</name>
</author>
<author><name sortKey="Li, S" uniqKey="Li S">S Li</name>
</author>
<author><name sortKey="Su, Z" uniqKey="Su Z">Z Su</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Engel, Sr" uniqKey="Engel S">SR Engel</name>
</author>
<author><name sortKey="Balakrishnan, R" uniqKey="Balakrishnan R">R Balakrishnan</name>
</author>
<author><name sortKey="Binkley, G" uniqKey="Binkley G">G Binkley</name>
</author>
<author><name sortKey="Christie, Kr" uniqKey="Christie K">KR Christie</name>
</author>
<author><name sortKey="Costanzo, Mc" uniqKey="Costanzo M">MC Costanzo</name>
</author>
<author><name sortKey="Dwight, Ss" uniqKey="Dwight S">SS Dwight</name>
</author>
<author><name sortKey="Fisk, Dg" uniqKey="Fisk D">DG Fisk</name>
</author>
<author><name sortKey="Hirschman, Je" uniqKey="Hirschman J">JE Hirschman</name>
</author>
<author><name sortKey="Hitz, Bc" uniqKey="Hitz B">BC Hitz</name>
</author>
<author><name sortKey="Hong, El" uniqKey="Hong E">EL Hong</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gama Castro, S" uniqKey="Gama Castro S">S Gama-Castro</name>
</author>
<author><name sortKey="Jimenez Jacinto, V" uniqKey="Jimenez Jacinto V">V Jimenez-Jacinto</name>
</author>
<author><name sortKey="Peralta Gil, M" uniqKey="Peralta Gil M">M Peralta-Gil</name>
</author>
<author><name sortKey="Santos Zavaleta, A" uniqKey="Santos Zavaleta A">A Santos-Zavaleta</name>
</author>
<author><name sortKey="Penaloza Spinola, Mi" uniqKey="Penaloza Spinola M">MI Penaloza-Spinola</name>
</author>
<author><name sortKey="Contreras Moreira, B" uniqKey="Contreras Moreira B">B Contreras-Moreira</name>
</author>
<author><name sortKey="Segura Salazar, J" uniqKey="Segura Salazar J">J Segura-Salazar</name>
</author>
<author><name sortKey="Muniz Rascado, L" uniqKey="Muniz Rascado L">L Muniz-Rascado</name>
</author>
<author><name sortKey="Martinez Flores, I" uniqKey="Martinez Flores I">I Martinez-Flores</name>
</author>
<author><name sortKey="Salgado, H" uniqKey="Salgado H">H Salgado</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sierro, N" uniqKey="Sierro N">N Sierro</name>
</author>
<author><name sortKey="Makita, Y" uniqKey="Makita Y">Y Makita</name>
</author>
<author><name sortKey="De Hoon, M" uniqKey="De Hoon M">M de Hoon</name>
</author>
<author><name sortKey="Nakai, K" uniqKey="Nakai K">K Nakai</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Halfon, Ms" uniqKey="Halfon M">MS Halfon</name>
</author>
<author><name sortKey="Gallo, Sm" uniqKey="Gallo S">SM Gallo</name>
</author>
<author><name sortKey="Bergman, Cm" uniqKey="Bergman C">CM Bergman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Portales Casamar, E" uniqKey="Portales Casamar E">E Portales-Casamar</name>
</author>
<author><name sortKey="Thongjuea, S" uniqKey="Thongjuea S">S Thongjuea</name>
</author>
<author><name sortKey="Kwon, At" uniqKey="Kwon A">AT Kwon</name>
</author>
<author><name sortKey="Arenillas, D" uniqKey="Arenillas D">D Arenillas</name>
</author>
<author><name sortKey="Zhao, X" uniqKey="Zhao X">X Zhao</name>
</author>
<author><name sortKey="Valen, E" uniqKey="Valen E">E Valen</name>
</author>
<author><name sortKey="Yusuf, D" uniqKey="Yusuf D">D Yusuf</name>
</author>
<author><name sortKey="Lenhard, B" uniqKey="Lenhard B">B Lenhard</name>
</author>
<author><name sortKey="Wasserman, Ww" uniqKey="Wasserman W">WW Wasserman</name>
</author>
<author><name sortKey="Sandelin, A" uniqKey="Sandelin A">A Sandelin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
<author><name sortKey="Li, N" uniqKey="Li N">N Li</name>
</author>
<author><name sortKey="Bailey, Tl" uniqKey="Bailey T">TL Bailey</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
<author><name sortKey="De Moor, B" uniqKey="De Moor B">B De Moor</name>
</author>
<author><name sortKey="Eskin, E" uniqKey="Eskin E">E Eskin</name>
</author>
<author><name sortKey="Favorov, Av" uniqKey="Favorov A">AV Favorov</name>
</author>
<author><name sortKey="Frith, Mc" uniqKey="Frith M">MC Frith</name>
</author>
<author><name sortKey="Fu, Y" uniqKey="Fu Y">Y Fu</name>
</author>
<author><name sortKey="Kent, Wj" uniqKey="Kent W">WJ Kent</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hu, J" uniqKey="Hu J">J Hu</name>
</author>
<author><name sortKey="Li, B" uniqKey="Li B">B Li</name>
</author>
<author><name sortKey="Kihara, D" uniqKey="Kihara D">D Kihara</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Cliften, P" uniqKey="Cliften P">P Cliften</name>
</author>
<author><name sortKey="Sudarsanam, P" uniqKey="Sudarsanam P">P Sudarsanam</name>
</author>
<author><name sortKey="Desikan, A" uniqKey="Desikan A">A Desikan</name>
</author>
<author><name sortKey="Fulton, L" uniqKey="Fulton L">L Fulton</name>
</author>
<author><name sortKey="Fulton, B" uniqKey="Fulton B">B Fulton</name>
</author>
<author><name sortKey="Majors, J" uniqKey="Majors J">J Majors</name>
</author>
<author><name sortKey="Waterston, R" uniqKey="Waterston R">R Waterston</name>
</author>
<author><name sortKey="Cohen, Ba" uniqKey="Cohen B">BA Cohen</name>
</author>
<author><name sortKey="Johnston, M" uniqKey="Johnston M">M Johnston</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Stormo, Gd" uniqKey="Stormo G">GD Stormo</name>
</author>
<author><name sortKey="Hartzell, Gw" uniqKey="Hartzell G">GW Hartzell</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Cliften, Pf" uniqKey="Cliften P">PF Cliften</name>
</author>
<author><name sortKey="Hillier, Lw" uniqKey="Hillier L">LW Hillier</name>
</author>
<author><name sortKey="Fulton, L" uniqKey="Fulton L">L Fulton</name>
</author>
<author><name sortKey="Graves, T" uniqKey="Graves T">T Graves</name>
</author>
<author><name sortKey="Miner, T" uniqKey="Miner T">T Miner</name>
</author>
<author><name sortKey="Gish, Wr" uniqKey="Gish W">WR Gish</name>
</author>
<author><name sortKey="Waterston, Rh" uniqKey="Waterston R">RH Waterston</name>
</author>
<author><name sortKey="Johnston, M" uniqKey="Johnston M">M Johnston</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Mccue, L" uniqKey="Mccue L">L McCue</name>
</author>
<author><name sortKey="Thompson, W" uniqKey="Thompson W">W Thompson</name>
</author>
<author><name sortKey="Carmack, C" uniqKey="Carmack C">C Carmack</name>
</author>
<author><name sortKey="Ryan, Mp" uniqKey="Ryan M">MP Ryan</name>
</author>
<author><name sortKey="Liu, Js" uniqKey="Liu J">JS Liu</name>
</author>
<author><name sortKey="Derbyshire, V" uniqKey="Derbyshire V">V Derbyshire</name>
</author>
<author><name sortKey="Lawrence, Ce" uniqKey="Lawrence C">CE Lawrence</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Alkema, Wb" uniqKey="Alkema W">WB Alkema</name>
</author>
<author><name sortKey="Lenhard, B" uniqKey="Lenhard B">B Lenhard</name>
</author>
<author><name sortKey="Wasserman, Ww" uniqKey="Wasserman W">WW Wasserman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wels, M" uniqKey="Wels M">M Wels</name>
</author>
<author><name sortKey="Francke, C" uniqKey="Francke C">C Francke</name>
</author>
<author><name sortKey="Kerkhoven, R" uniqKey="Kerkhoven R">R Kerkhoven</name>
</author>
<author><name sortKey="Kleerebezem, M" uniqKey="Kleerebezem M">M Kleerebezem</name>
</author>
<author><name sortKey="Siezen, Rj" uniqKey="Siezen R">RJ Siezen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wang, T" uniqKey="Wang T">T Wang</name>
</author>
<author><name sortKey="Stormo, Gd" uniqKey="Stormo G">GD Stormo</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Blanchette, M" uniqKey="Blanchette M">M Blanchette</name>
</author>
<author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Blanchette, M" uniqKey="Blanchette M">M Blanchette</name>
</author>
<author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pavesi, G" uniqKey="Pavesi G">G Pavesi</name>
</author>
<author><name sortKey="Zambelli, F" uniqKey="Zambelli F">F Zambelli</name>
</author>
<author><name sortKey="Pesole, G" uniqKey="Pesole G">G Pesole</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Newberg, La" uniqKey="Newberg L">LA Newberg</name>
</author>
<author><name sortKey="Thompson, Wa" uniqKey="Thompson W">WA Thompson</name>
</author>
<author><name sortKey="Conlan, S" uniqKey="Conlan S">S Conlan</name>
</author>
<author><name sortKey="Smith, Tm" uniqKey="Smith T">TM Smith</name>
</author>
<author><name sortKey="Mccue, La" uniqKey="Mccue L">LA McCue</name>
</author>
<author><name sortKey="Lawrence, Ce" uniqKey="Lawrence C">CE Lawrence</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Siddharthan, R" uniqKey="Siddharthan R">R Siddharthan</name>
</author>
<author><name sortKey="Siggia, Ed" uniqKey="Siggia E">ED Siggia</name>
</author>
<author><name sortKey="Van Nimwegen, E" uniqKey="Van Nimwegen E">E van Nimwegen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sinha, S" uniqKey="Sinha S">S Sinha</name>
</author>
<author><name sortKey="Blanchette, M" uniqKey="Blanchette M">M Blanchette</name>
</author>
<author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Liu, Y" uniqKey="Liu Y">Y Liu</name>
</author>
<author><name sortKey="Liu, Xs" uniqKey="Liu X">XS Liu</name>
</author>
<author><name sortKey="Wei, L" uniqKey="Wei L">L Wei</name>
</author>
<author><name sortKey="Altman, Rb" uniqKey="Altman R">RB Altman</name>
</author>
<author><name sortKey="Batzoglou, S" uniqKey="Batzoglou S">S Batzoglou</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wang, T" uniqKey="Wang T">T Wang</name>
</author>
<author><name sortKey="Stormo, Gd" uniqKey="Stormo G">GD Stormo</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gordan, R" uniqKey="Gordan R">R Gordan</name>
</author>
<author><name sortKey="Narlikar, L" uniqKey="Narlikar L">L Narlikar</name>
</author>
<author><name sortKey="Hartemink, Aj" uniqKey="Hartemink A">AJ Hartemink</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Romer, Ka" uniqKey="Romer K">KA Romer</name>
</author>
<author><name sortKey="Kayombya, Gr" uniqKey="Kayombya G">GR Kayombya</name>
</author>
<author><name sortKey="Fraenkel, E" uniqKey="Fraenkel E">E Fraenkel</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hu, J" uniqKey="Hu J">J Hu</name>
</author>
<author><name sortKey="Yang, Yd" uniqKey="Yang Y">YD Yang</name>
</author>
<author><name sortKey="Kihara, D" uniqKey="Kihara D">D Kihara</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zhang, S" uniqKey="Zhang S">S Zhang</name>
</author>
<author><name sortKey="Li, S" uniqKey="Li S">S Li</name>
</author>
<author><name sortKey="Pham, Pt" uniqKey="Pham P">PT Pham</name>
</author>
<author><name sortKey="Su, Z" uniqKey="Su Z">Z Su</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sandve, Gk" uniqKey="Sandve G">GK Sandve</name>
</author>
<author><name sortKey="Abul, O" uniqKey="Abul O">O Abul</name>
</author>
<author><name sortKey="Walseng, V" uniqKey="Walseng V">V Walseng</name>
</author>
<author><name sortKey="Drablos, F" uniqKey="Drablos F">F Drablos</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kellis, M" uniqKey="Kellis M">M Kellis</name>
</author>
<author><name sortKey="Patterson, N" uniqKey="Patterson N">N Patterson</name>
</author>
<author><name sortKey="Endrizzi, M" uniqKey="Endrizzi M">M Endrizzi</name>
</author>
<author><name sortKey="Birren, B" uniqKey="Birren B">B Birren</name>
</author>
<author><name sortKey="Lander, Es" uniqKey="Lander E">ES Lander</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Mushegian, Ar" uniqKey="Mushegian A">AR Mushegian</name>
</author>
<author><name sortKey="Koonin, Ev" uniqKey="Koonin E">EV Koonin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Karp, Rm" uniqKey="Karp R">RM Karp</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
  <front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Bioinformatics</journal-id>
<journal-title-group><journal-title>BMC Bioinformatics</journal-title>
</journal-title-group>
<issn pub-type="epub">1471-2105</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">21679436</article-id>
<article-id pub-id-type="pmc">3225181</article-id>
<article-id pub-id-type="publisher-id">1471-2105-12-238</article-id>
<article-id pub-id-type="doi">10.1186/1471-2105-12-238</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Methodology Article</subject>
</subj-group>
</article-categories>
<title-group><article-title>MotifClick: prediction of <italic>cis</italic>
-regulatory binding sites via merging cliques</article-title>
</title-group>
<contrib-group><contrib contrib-type="author" id="A1"><name><surname>Zhang</surname>
<given-names>Shaoqiang</given-names>
</name>
<xref ref-type="aff" rid="I2">2</xref>
<email>sqzhang@163.com</email>
</contrib>
<contrib contrib-type="author" id="A2"><name><surname>Li</surname>
<given-names>Shan</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>sli13@uncc.edu</email>
</contrib>
<contrib contrib-type="author" id="A3"><name><surname>Niu</surname>
<given-names>Meng</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>mniu2@uncc.edu</email>
</contrib>
<contrib contrib-type="author" id="A4"><name><surname>Pham</surname>
<given-names>Phuc T</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>ptpham@uncc.edu</email>
</contrib>
<contrib contrib-type="author" corresp="yes" id="A5"><name><surname>Su</surname>
<given-names>Zhengchang</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>zcsu@uncc.edu</email>
</contrib>
</contrib-group>
<aff id="I1"><label>1</label>
Department of Bioinformatics and Genomics, Center for Bioinformatics Research, the University of North Carolina at Charlotte, 351 Bioinformatics Building, 9201 University City Blvd., Charlotte, NC 28223, USA</aff>
<aff id="I2"><label>2</label>
College of Computer and Information Engineering, Tianjin Normal University, 393 Bin Shui Xi Road, Tianjin, 300387, China</aff>
<pub-date pub-type="collection"><year>2011</year>
</pub-date>
<pub-date pub-type="epub"><day>16</day>
<month>6</month>
<year>2011</year>
</pub-date>
<volume>12</volume>
<fpage>238</fpage>
<lpage>238</lpage>
<history><date date-type="received"><day>23</day>
<month>12</month>
<year>2010</year>
</date>
<date date-type="accepted"><day>16</day>
<month>6</month>
<year>2011</year>
</date>
</history>
<permissions><copyright-statement>Copyright ©2011 Zhang et al; licensee BioMed Central Ltd.</copyright-statement>
<copyright-year>2011</copyright-year>
<copyright-holder>Zhang et al; licensee BioMed Central Ltd.</copyright-holder>
<license license-type="open-access" xlink:href="http://creativecommons.org/licenses/by/2.0"><license-p>This is an Open Access article distributed under the terms of the Creative Commons Attribution License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/2.0">http://creativecommons.org/licenses/by/2.0</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</license-p>
</license>
</permissions>
<self-uri xlink:href="http://www.biomedcentral.com/1471-2105/12/238"></self-uri>
<abstract><sec><title>Background</title>
<p>Although dozens of algorithms and tools have been developed to find a set of <italic>cis</italic>
-regulatory binding sites called a motif in a set of intergenic sequences using various approaches, most of these tools focus on identifying binding sites that are significantly different from their background sequences. However, some motifs may have a similar nucleotide distribution to that of their background sequences. Therefore, such binding sites can be missed by these tools.</p>
</sec>
<sec><title>Results</title>
<p>Here, we present a graph-based polynomial-time algorithm, MotifClick, for the prediction of <italic>cis</italic>
-regulatory binding sites, in particular, those that have a similar nucleotide distribution to that of their background sequences. To find binding sites with length <italic>k</italic>
, we construct a graph using some 2(<italic>k</italic>
-1)-mers in the input sequences as the vertices, and connect two vertices by an edge if the maximum number of matches of the local gapless alignments between the two 2(<italic>k</italic>
-1)-mers is greater than a cutoff value. We identify a motif as a set of similar <italic>k</italic>
-mers from a merged group of maximum cliques associated with some vertices.</p>
</sec>
<sec><title>Conclusions</title>
<p>When evaluated on both synthetic and real datasets of prokaryotes and eukaryotes, MotifClick outperforms existing leading motif-finding tools for prediction accuracy and balancing the prediction sensitivity and specificity in general. In particular, when the distribution of nucleotides of binding sites is similar to that of their background sequences, MotifClick is more likely to identify the binding sites than the other tools.</p>
</sec>
</abstract>
</article-meta>
</front>
<body><sec><title>Background</title>
<p>Deciphering complex genetic regulatory networks encoded in a genome is a challenging problem in the post-genomic era [<xref ref-type="bibr" rid="B1">1</xref>
]. Identifying <italic>cis</italic>
-regulatory binding sites recognized by transcription factors (TF) in a genome is the first step towards this goal [<xref ref-type="bibr" rid="B2">2</xref>
]. Since any segment of genomic sequence can be potentially a <italic>cis</italic>
-regulatory binding site, a binding site motif (In this paper, we call a set of similar <italic>cis</italic>
-regulatory binding sites recognized by the same TF a <italic>motif</italic>
) can only be predicted by comparing multiple sequences that potentially contain the <italic>cis</italic>
-regulatory binding sites sought after, based on the assumption that <italic>cis</italic>
-regulatory binding sites are usually more conserved than their flanking non-functional sequences [<xref ref-type="bibr" rid="B3">3</xref>
]. Therefore, the motif-finding problem is usually formulated to identify overrepresented segments of sequences from a set of input intergenic sequences that can be obtained by using a group of co-regulated genes in the same genome [<xref ref-type="bibr" rid="B4">4</xref>
], or obtained by using a group of orthologous genes from multiple appropriately related genomes. The latter procedure is also called phylogenetic footprinting [<xref ref-type="bibr" rid="B5">5</xref>
]. The motif-finding problem has promoted a large number of studies due to the importance of <italic>cis</italic>
-regulatory binding sites in gene transcriptional regulation. Here we can only briefly review some of recently developed methods that are relevant to our method, for more intensive reviews, see [<xref ref-type="bibr" rid="B6">6</xref>
-<xref ref-type="bibr" rid="B8">8</xref>
].</p>
<p>Motif-finding algorithms can be largely categorized into "word enumeration" based and "pattern recognition" based methods. The former methods use different strategies to exhaustively enumerate <italic>k</italic>
-mers in the input sequences. For example, MDScan [<xref ref-type="bibr" rid="B9">9</xref>
] employs a deterministic greedy algorithm and Weeder [<xref ref-type="bibr" rid="B10">10</xref>
] uses a suffix tree for the enumeration. Moreover, WINNOWER [<xref ref-type="bibr" rid="B11">11</xref>
], CUBIC [<xref ref-type="bibr" rid="B12">12</xref>
], cWINNOWER [<xref ref-type="bibr" rid="B13">13</xref>
] and MotifCut [<xref ref-type="bibr" rid="B14">14</xref>
] use graph-theoretic methods for the enumeration. Particularly, MotifCut represents each <italic>k</italic>
-mer in the input sequences as a vertex and searches for maximum density subgraphs as motifs using a minimum-cut algorithm [<xref ref-type="bibr" rid="B14">14</xref>
]. The more recently developed MoSDi algorithm [<xref ref-type="bibr" rid="B15">15</xref>
] attempts to identify IUPAC motifs by exhaustively searching a fraction of the motif space according to a compound Poisson approximation of the distribution of the number of motif occurrences. The major drawback of word enumeration based methods is their computational inefficiency and application limitation to short motifs.</p>
<p>On the other hand, pattern recognition based methods often employ a probabilistic model for the representation of binding sites in the form of position-specific scoring matrices (PSSM) and an optimization procedure to find motifs. For example, Gibbs sampler [<xref ref-type="bibr" rid="B16">16</xref>
], AlignACE [<xref ref-type="bibr" rid="B17">17</xref>
], MotifSampler [<xref ref-type="bibr" rid="B18">18</xref>
], and BioProspector [<xref ref-type="bibr" rid="B19">19</xref>
] use a Gibbs sampling strategy to search the PSSM space, whereas MEME [<xref ref-type="bibr" rid="B20">20</xref>
] uses an expectation-maximization (EM) strategy to find overrepresented sequences as possible binding sites. However, these optimization methods are known to be affected by local optima and can be very sensitive to small changes in the input sequences [<xref ref-type="bibr" rid="B6">6</xref>
]. Recently, DEME [<xref ref-type="bibr" rid="B21">21</xref>
], Seeder [<xref ref-type="bibr" rid="B22">22</xref>
] and MoAn [<xref ref-type="bibr" rid="B23">23</xref>
] were developed to find "discriminative" motifs, in which a motif is treated as a feature that leads to a good classification between a positive set of sequences containing binding sites and a negative (background) set of sequences [<xref ref-type="bibr" rid="B24">24</xref>
]. However these algorithms are limited because they can only find motifs that exist in one group of sequences but not in another group of sequences. Furthermore, when the distribution of nucleotides in a motif is not significantly different from that of the background sequences, the probabilistic model based algorithms may fail to find the binding sites (see Results).</p>
<p>In addition, it has been shown that a consensus sequence and PSSM may not fully capture all the subtleties of a DNA binding motif of a TF, while more complex models that incorporate position-dependence of binding sites may over fit the input sequences [<xref ref-type="bibr" rid="B25">25</xref>
]. Furthermore, the binding sites of a TF can be so degenerate that they can be divided into multiple distinct sub-motifs. For example, the experimentally verified 248 binding sites of the TF CRP in <italic>E. coli </italic>
K12 can be divided into at least three sub-motifs; i.e., a more information content-rich canonical palindromic sub-motif, a T-rich sub-motif, and an A-rich sub-motif although both the latter sub-motifs share a certain number of elements with the canonical sub-motif [<xref ref-type="bibr" rid="B26">26</xref>
]. Therefore, instead of predicting all the binding sites of a TF as a single motif, one should predict the binding sites of a TF as multiple sub-motifs and then merge them if possible. Since individual binding sites in such a sub-motif are likely to be highly similar to one another, if we treat each binding site in a sub-motif as a vertex of a graph, and connected two binding sites by an edge if their similarity is above a cut-off value, then these binding sites are likely to form a clique (complete subgraph). In other words, a sub-motif can be modelled as a clique from a graph-theoretic perspective. Therefore, finding sub-motifs of a TF is equivalent to finding some maximal cliques in a graph that represents the similarity of <italic>k</italic>
-mers in a set of intergenic sequences. In this paper, we present a polynomial-time algorithm, MotifClick, for the problem based on this formulation while considering the distributions of nucleotides in binding sites and their background sequences as well as other statistical properties of binding sites (see Methods). We have tested MotifClick using both synthetic and real datasets of prokaryotes and eukaryotes, and found that our algorithm almost always outperforms existing leading algorithms in prediction accuracy on all datasets tested and is more computationally efficient than other graph-theoretic based algorithms such as MotifCut [<xref ref-type="bibr" rid="B14">14</xref>
]. In addition, MotifClick seems to be the best among the leading algorithms at balancing the prediction sensitivity and specificity. More importantly, MotifClick is more likely than the existing tools to identify binding sites that have a similar nucleotide distribution to that of their background sequences.</p>
<sec><title>Overview of the MotifClick algorithm</title>
<p>Before giving a formal description of the MotifClick algorithm in Methods, we first outline its basic idea. To find a motif with length <italic>k </italic>
in a set of sequences, MotifClick first converts each of the input sequences into a collection of 2(<italic>k </italic>
- 1) -mers (Figure <xref ref-type="fig" rid="F1">1</xref>
). Specifically, for each sequence, we extract all 2(<italic>k </italic>
- 1)-mers with a step size <italic>k </italic>
-1 (the last string may be shorter than 2(<italic>k </italic>
- 1)), so that two adjacent 2(<italic>k </italic>
- 1)-mers have an overlap of <italic>k</italic>
-1 bases (Figure <xref ref-type="fig" rid="F1">1</xref>
). We construct a graph <italic>G </italic>
= (<italic>V</italic>
, <italic>E</italic>
), in which the vertices in <italic>V </italic>
represent the 2(<italic>k </italic>
- 1)-mers from all the input sequences. We connect each pair of vertices <italic>u </italic>
and <italic>v </italic>
by an edge with a weight <italic>w</italic>
(<italic>u</italic>
, <italic>v</italic>
) if <italic>w</italic>
(<italic>u</italic>
, <italic>v</italic>
) is above a cutoff <italic>α</italic>
. The weight measures the maximum similarity of all local gapless alignments of <italic>k</italic>
-mers between two 2(<italic>k </italic>
- 1) -mers. Clearly, if the binding sites of a TF are highly conserved, then they can be represented by a clique or a high-density subgraph [<xref ref-type="bibr" rid="B11">11</xref>
,<xref ref-type="bibr" rid="B14">14</xref>
]. However, as we mentioned earlier, a TF can bind a few distinct motifs with little similarity. This fact promoted us to re-define the motif-finding problem as the search for multiple maximal weighted cliques in the graph <italic>G </italic>
= (<italic>V</italic>
, <italic>E</italic>
) followed by merging them if possible.</p>
<fig id="F1" position="float"><label>Figure 1</label>
<caption><p><bold>Breakdown of an input sequence into a set of 2(<italic>k</italic>
-1)-mers</bold>
. Each pair of adjacent 2(<italic>k</italic>
-1)-mers overlap with each other by <italic>k</italic>
-1 letters. Each 2(<italic>k</italic>
-1)-mer will be used as a vertex to construct a graph.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-1"></graphic>
</fig>
<p>Furthermore, to measure the significance of difference between a binding site and its background sequence, we define the <italic>sum of squared distance </italic>
(SSD) between the nucleotide distribution {<italic>p</italic>
(<italic>b</italic>
)} of each binding site and that of its background intergenic sequence {<italic>q</italic>
(<italic>b</italic>
)} as <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i1.gif"></inline-graphic>
</inline-formula>
. Through analyzing the motifs collected in five databases, SGD [<xref ref-type="bibr" rid="B27">27</xref>
], RegulonDB [<xref ref-type="bibr" rid="B28">28</xref>
], DBTBS [<xref ref-type="bibr" rid="B29">29</xref>
], Redfly [<xref ref-type="bibr" rid="B30">30</xref>
] and JASPAR [<xref ref-type="bibr" rid="B31">31</xref>
], we found that a considerable portion of binding sites in the five databases have an SSD < 0.2 (Figure <xref ref-type="fig" rid="F2">2A</xref>
). Therefore, some binding sites in both bacteria and eukaryotes may not have a significantly different distribution of nucleotides frequency from that of their background intergenic sequences. This might explain why it is often difficult to find motifs whose elements have a small SSD using existing motif finding tools [<xref ref-type="bibr" rid="B32">32</xref>
] (see Results and discussion). To overcome this shortcoming of existing tools, we take SSD into account in our algorithm.</p>
<fig id="F2" position="float"><label>Figure 2</label>
<caption><p><bold>Analysis of binding sites in five databases</bold>
. (A). Distributions of the sum of squared distance (SSD) between the nucleotide distribution of each motif and that of its background sequences in five databases, SGD, RegulonDB, DBTBS, Redfly, and JASPAR. (B). Distributions of the ratio of maximum length of a segment of single-nucleotide in a binding site to the length of the binding site in the five databases.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-2"></graphic>
</fig>
</sec>
</sec>
<sec><title>Results and discussion</title>
<p>To evaluate the performance of MotifClick, we first compared it with four leading general purpose motif finding tools: BioProspector [<xref ref-type="bibr" rid="B19">19</xref>
], MEME [<xref ref-type="bibr" rid="B20">20</xref>
], MotifCut [<xref ref-type="bibr" rid="B14">14</xref>
], and Weeder [<xref ref-type="bibr" rid="B10">10</xref>
] on both synthetic and real datasets. We selected these tools for the comparison based on recent survey studies [<xref ref-type="bibr" rid="B32">32</xref>
,<xref ref-type="bibr" rid="B33">33</xref>
] and our own evaluation of multiple motif-find tools [<xref ref-type="bibr" rid="B26">26</xref>
]. For instance, Tompa <italic>et al</italic>
. [<xref ref-type="bibr" rid="B32">32</xref>
] assessed 13 motif-finding tools for the discovery of binding sites in eukaryotes using a dataset from the TRANSFAC database, and found that Weeder outperformed the others for most measures, and that MEME also performed well although not as good as Weeder. In another survey study, Hu <italic>et al</italic>
. [<xref ref-type="bibr" rid="B33">33</xref>
] evaluated five tools, AlignACE [<xref ref-type="bibr" rid="B17">17</xref>
], MEME, BioProspector, MDScan [<xref ref-type="bibr" rid="B9">9</xref>
], and MotifSampler [<xref ref-type="bibr" rid="B18">18</xref>
], for the prediction of binding sites in prokaryotes using a dataset from RegulonDB [<xref ref-type="bibr" rid="B28">28</xref>
], and found that MEME often achieved the highest sensitivity, while BioProspector often had the highest specificity. We included MotifCut for the comparison in the current study because it is also a graph-theoretic algorithm and is claimed to discover more known yeast motifs than do MEME and BioProspector. We also evaluated an option (-s 0) of our MotifClick program for finding more degenerate binding sites than the default setting. We excluded a few new methods, Seeder [<xref ref-type="bibr" rid="B22">22</xref>
] and DEME [<xref ref-type="bibr" rid="B21">21</xref>
], because they do not support the mode 'any-number of repetitions' (anr); MoAn [<xref ref-type="bibr" rid="B23">23</xref>
], because it requires a large and reasonable negative set; and MoSDi [<xref ref-type="bibr" rid="B15">15</xref>
], because its output format is IUPAC, making the comparison difficult.</p>
<p>Furthermore, with the availability of increasing numbers of sequenced genomes, phylogenetic footprinting has proved to be a powerful method for predicting <italic>cis</italic>
-regulatory binding sites in both eukaryotic [<xref ref-type="bibr" rid="B34">34</xref>
] and prokaryotic genomes [<xref ref-type="bibr" rid="B5">5</xref>
]. In this approach, one identifies well-conserved segments of sequences as potential binding sites from the intergenic sequences of a set of orthologous genes from a group of appropriately related genomes based on the assumption that binding sites of orthologous genes are largely conserved in closely related genomes. Several existing general purpose motif-finding algorithms such as AlignACE, Gibbs sampler, MEME, and CONSENSUS [<xref ref-type="bibr" rid="B35">35</xref>
] have been used for phylogenetic footprinting in both eukaryotes and prokaryotes [<xref ref-type="bibr" rid="B36">36</xref>
-<xref ref-type="bibr" rid="B40">40</xref>
]. We [<xref ref-type="bibr" rid="B26">26</xref>
] have recently evaluated six tools, BioProspector, CONSENSUS, CUBIC [<xref ref-type="bibr" rid="B12">12</xref>
], MDScan, MEME and MotifSampler for the prediction of binding sites in prokaryotes by phylogenetic footprinting, and found that MEME and BioProspector recovered more known binding sites than the others. Therefore, we also compared the MotifClick algorithm with the four leading general purpose motif-finding tools for phylogenetic footprinting on both prokaryotic and eukaryotic datasets.</p>
<p>In addition, motif-finding algorithms that are specifically for phylogenetic footprinting have also been developed, such as FootPrinter [<xref ref-type="bibr" rid="B41">41</xref>
,<xref ref-type="bibr" rid="B42">42</xref>
], WeederH (Weeder for homologous sequences) [<xref ref-type="bibr" rid="B43">43</xref>
], phylogenetic Gibbs sampler [<xref ref-type="bibr" rid="B44">44</xref>
], PhyloGibbs [<xref ref-type="bibr" rid="B45">45</xref>
], PhyME [<xref ref-type="bibr" rid="B46">46</xref>
], and CompareProspector [<xref ref-type="bibr" rid="B47">47</xref>
]. These algorithms typically take into account the phylogenetic relationships of the input sequences when identifying the most conserved <italic>k</italic>
-mers. Thus, besides the four leading general purpose motif-finding tools mentioned above, we also compared our algorithm with FootPrinter and WeederH. However, we excluded other phylogenetic motif-finding tools such as phylogenetic Gibbs sampler, PhyloGibbs, PhyME, and CompareProspector, because their input orthologous intergenic sequences need to be aligned by a multiple alignment tool, but many orthologous intergenic sequences are not alignable. We also excluded phylogenetic motif-finding tools such as PhyloCon [<xref ref-type="bibr" rid="B48">48</xref>
] and PRIORITY [<xref ref-type="bibr" rid="B49">49</xref>
] because they were designed to search for motifs that are both overrepresented in a set of sequences from a genome and conserved across related organisms (the so-called 'multiple genes, multiple species' approach).</p>
<sec><title>Evaluation on synthetic datasets</title>
<p>In order to obtain accurate false positive rates and avoid possible overtraining of the algorithm parameters, we evaluate MotifClick along with the four selected general purpose tools using the synthetic datasets.</p>
<sec><title>1. Motifs with a length of eight bases</title>
<p>We first evaluated our algorithm for identifying motifs with a length of eight bases implanted in the synthetic background sequences. In order to assess the ability of the tools for finding motifs with different SSDs, we selected two motifs from the SGD database [<xref ref-type="bibr" rid="B27">27</xref>
], CIN5 and PHD1, each contains 20 binding sites, with an average SSD of 0.06 and 0.1 respectively. We selected these two motifs for the evaluation since the majority of yeast binding sites have an SSD = 0.06 or SSD = 0.1 (Figure <xref ref-type="fig" rid="F2">2A</xref>
). Binding sites are implanted in 400-base background sequences. As shown in Figure <xref ref-type="fig" rid="F3">3</xref>
, for the motif CIN5, Weeder has the highest sensitivity, while MotifClick achieves the highest specificity, performance coefficient, and F-measure. However, for the motif PHD1, MotifCut outperforms the four other methods. Notably, MotifClick is the best at balancing specificity and sensitivity for both motifs. Furthermore, MotifClick and Weeder have a more consistent performance than the other methods on both motifs. This result might suggest that MotifClick performs better when the SSD is small. To further confirm this speculation, we evaluated MotifClick with the SSD option set to 0.06 and the other tools on more 8-mer motifs with an SSD ≤ 0.06 (e.g., CIN5, FKH1 and GCN4 from the SGD database) that are implanted in synthetic background sequences. As shown Table S1 in Additional file <xref ref-type="supplementary-material" rid="S1">1</xref>
, MotifClick generally has the smallest log-odds ratios with respect to the other programs, suggesting that it is able to find the most binding sites that are missed by the other tools.</p>
<fig id="F3" position="float"><label>Figure 3</label>
<caption><p><bold>Comparison of MotifClick with the default setting and the option (-s, 0) with four other tools for predicting binding sites of two 8-mer yeast motifs, CIN5 and PHD1</bold>
. The binding sites of both motifs were separately implanted in two sets of 20 400-base synthetic sequences.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-3"></graphic>
</fig>
<p>To further compare MotifClick with other tools for their ability to find binding sites located in different sizes of background sequences, we selected six motifs with a length of eight bases from SGD and six motifs with a length of eight bases from Redfly for the evaluation. All these motifs have an SSD < 0.15, and are available at <ext-link ext-link-type="uri" xlink:href="http://motifclick.uncc.edu">http://motifclick.uncc.edu</ext-link>
. Each binding site was implanted in a background sequence of a length of 400, 600, 800 and 1,000 bases. The average performance of each tool on the 12 motifs in each background sequence size (400 × 20, 600 × 20, 800 × 20 and 1,000 × 20) is shown in Figure <xref ref-type="fig" rid="F4">4</xref>
. Again, MotifClick achieves the highest specificity, performance coefficient, and F-measure while Weeder has the highest sensitivity, but the lowest specificity on each dataset among the programs. It should be pointed out that the default parameters were used for all the programs; however, we noted that the default of Weeder could search eight-base motifs with two mutations while the other programs did not specify the number of mutations allowed, so it may be unfair to the other programs.</p>
<fig id="F4" position="float"><label>Figure 4</label>
<caption><p><bold>Comparison of MotifClick with four other algorithms for predicting binding sites from yeast and fly implanted in synthetic sequences</bold>
. In these plots the X-axis represents the input size (the number of nucleotides in a sequence times the number of sequences) and the Y-axis the percentage of correctly identified binding sites.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-4"></graphic>
</fig>
</sec>
<sec><title>2. Motifs with a length of 16 bases</title>
<p>We then evaluated our algorithm for identifying binding sites with a length of 16 bases taken from RegulonDB and DBTBS and implanted in background sequences of different sizes. Now that the vast majority of motifs in RegulonDB and DBTBS have an SSD < 0.1 (Figure <xref ref-type="fig" rid="F2">2A</xref>
), we chose 10 motifs from RegulonDB and eight motifs from DBTBS with an average SSD < 0.1. These motifs and background sequences are available at <ext-link ext-link-type="uri" xlink:href="http://motifclick.uncc.edu">http://motifclick.uncc.edu</ext-link>
. Weeder was not evaluated on these datasets, because it only accepts motif lengths of even values between 6 and 12. As shown in Figure <xref ref-type="fig" rid="F5">5</xref>
, MotifClick achieves the highest sensitivity, performance coefficient and F-measure, while MotifCut has the highest specificity for all the datasets of different background sequence sizes.</p>
<fig id="F5" position="float"><label>Figure 5</label>
<caption><p><bold>Comparison of MotifClick with other three algorithms for predicting binding sites from <italic>E. coli </italic>
K12 and <italic>B. subtilis </italic>
implanted in synthetic sequences</bold>
. In these plots, the X-axis represents the input size (the number nucleotides in a sequence times the number sequences) and the Y-axis the percentage of correctly identified binding sites.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-5"></graphic>
</fig>
<p>To evaluate the noise tolerance of our algorithm, we added 5 and 10 additional background sequences (noises) of size 400 bases to each of the sequence sets in the 400 × 20 datasets constructed above for the 18 motifs, to form two datasets denoted as 400 × 25 (25% added noises) and 400 × 30 (50% added noises), respectively. No binding sites were implanted in any of these 5 or 10 additional sequences; therefore, they increased the noise levels in the original sequence sets. As shown in Figure S1 in Additional file <xref ref-type="supplementary-material" rid="S1">1</xref>
, with increasing levels of noise, MotifClick almost constantly outperforms the other programs, and the noise levels have only a small effect on its performance for all the evaluations. Therefore, besides its outstanding performance for prediction accuracy, our program is also rather noise-tolerant, comparable to the best tools evaluated such as MEME.</p>
<p>Furthermore, we found that all the motif-finding tools can accurately indentify motifs with an SSD > 0.1, such as CRP, LexA, and PhoB in RegulonDB, because they are easy to be separated from background. However, when evaluating MotifClick with the SSD option set to 0.06 and the other tools on the synthetic datasets implanted with the 16-base motifs having an SSD ≤ 0.06, such as ArgR, CpxR, H-NS, GerE, and PhoP, we found that MotifClick outperforms the other tools for identifying these motifs with an SSD ≤ 0.06, and can predict the most binding sites that are missed by other tools as indicated by its smallest log-odds ratios with respect to the other tools (Table S2 in Additional file <xref ref-type="supplementary-material" rid="S1">1</xref>
).</p>
<p>We evaluated the running time of MotifClick on an Intel Xeon processor using all the synthetic datasets described earlier with motifs of lengths 8, 12, and 16 implanted in sequence sets with nucleotide sizes 400 × 20, 600 × 20, 800 × 20, and 1000 × 20. As shown in Figure S2 in Additional file <xref ref-type="supplementary-material" rid="S1">1</xref>
, the running time of the program is from several seconds to a few minutes on these datasets, and increases almost linearly with the size of the input sequences. Thus, MotifClick's computational efficiency is also comparable to that of the other algorithms; especially it runs much faster than MotifCut though both are based on graph theory. For instance, it only takes MotifClick a few minutes (on average, about 5.7 minutes) to find a 16-mer motif in each dataset consisting of 1000 × 20 nucleotides (Figure S2 in Additional file <xref ref-type="supplementary-material" rid="S1">1</xref>
), while MotifCut needs more than 30 minutes, on the Intel Xeon processor. The main reason is that MotifClick only searches a portion of 2(<italic>k</italic>
-1)-mers while MotifCut uses all possible <italic>k</italic>
-mers as vertices.</p>
</sec>
</sec>
<sec><title>Evaluation on real datasets</title>
<sec><title>1. Sequences from the same genome</title>
<p>To evaluate our algorithm on real datasets, in addition to the 30 motifs that we have selected (10 from RegulonDB, eight from DBTBS, six from SGD, and six from Redfly), we selected another 30 motifs with lengths of 8~16 bases from JASPAR [<xref ref-type="bibr" rid="B31">31</xref>
], each contains at least five binding sites. These 60 motifs were placed back in their original locations of genomic sequences of a maximum length of 1,000 bases. To make the datasets more coherent, we removed binding sites that contain more than 30% degenerate bases and have an SSD > 0.3. However, we kept all binding sites in each sequence if there are two or more binding sites in it. These motifs and genomic sequences are available at <ext-link ext-link-type="uri" xlink:href="http://motifclick.uncc.edu">http://motifclick.uncc.edu</ext-link>
. As shown in Figure <xref ref-type="fig" rid="F6">6A</xref>
, MotifClick achieves the highest PC and F-measure, while Weeder has the highest sensitivity, and MotifCut has the highest specificity. Therefore MotifClick is also the best at balancing sensitivity and specificity on the real datasets.</p>
<fig id="F6" position="float"><label>Figure 6</label>
<caption><p><bold>Comparison of MotifClick with four other algorithms on real datasets</bold>
. (A) The results are the average performance of each algorithm on the 60 selected motifs located in their native genomic sequences. (B) The percentage of binding sites uniquely recovered by each algorithm and the percentage of binding sites shared with the four other algorithms on the real dataset of 20 motifs with an SSD ≤ 0.06.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-6"></graphic>
</fig>
<p>In order to evaluate the sensitivity of our program to the values of the option '-SSD' specified by a user, we ran the program on the 60 real datasets using eight different '-SSD' values in the range of [0.15, 0.5]. As shown in Figure S3 in Additional file <xref ref-type="supplementary-material" rid="S1">1</xref>
, although the binding sites of the 60 motifs have an SSD in the ranger of [0.05, 0.3], the performance of MotifClick only slightly decreased when the value of the option '-SSD' deviated from that of the motifs in the dataset, in particular when the former is larger than the latter. However, one should avoid using a smaller value of '-SSD' when the motif to be found may have a higher SSD. To further evaluate the ability of MotifClick to identify motifs with a low SSD that may be missed by other algorithm, we ran MotifClick with the SSD option set to 0.06 and the four other algorithms on 20 motifs with an SSD ≤ 0.06 from the 60 motifs of real datasets. As shown in Table <xref ref-type="table" rid="T1">1</xref>
, MotifClick generally had the smallest log-odds ratio with respect to each of the other algorithms. Therefore, MotifClick is indeed the best at predicting motifs with a low SSD that are missed by other algorithms (Figure <xref ref-type="fig" rid="F6">6B</xref>
).</p>
<table-wrap id="T1" position="float"><label>Table 1</label>
<caption><p>Log-odds ratios of pairs of programs for predicting binding sites with an SSD ≤ 0.06 in the real datasets</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th></th>
<th align="left">BioProspector</th>
<th align="left">MEME</th>
<th align="left">MotifCut</th>
<th align="left">Weeder</th>
</tr>
</thead>
<tbody><tr><td align="left">MotifClick</td>
<td align="left">0.21</td>
<td align="left">0.18</td>
<td align="left">0.23</td>
<td align="left">0.27</td>
</tr>
<tr><td align="left">Weeder</td>
<td align="left">0.28</td>
<td align="left">0.31</td>
<td align="left">0.29</td>
<td></td>
</tr>
<tr><td align="left">MotifCut</td>
<td align="left">0.37</td>
<td align="left">0.26</td>
<td></td>
<td></td>
</tr>
<tr><td align="left">MEME</td>
<td align="left">0.46</td>
<td></td>
<td></td>
<td></td>
</tr>
</tbody>
</table>
</table-wrap>
</sec>
<sec><title>2. Phylogenetic footprinting datasets from fungi and bacteria</title>
<p>To benchmark the performance of our algorithm for phylogenetic footprinting on real data, we compared MotifClick with the four general purpose motif-finding tools as well as two phylogenetic motif-finding tools, WeederH and FootPrinter, on orthologous intergenic sequence sets from the yeast (<italic>S. cerevisiae</italic>
) genome and other six closely related fungal genomes, as well as orthologous inter-operonic sequence sets from the <italic>E. coli </italic>
K12 genome and other 55 closely related γ -proteobacterial genomes.</p>
<sec><title>2.1 Yeast data</title>
<p>Because almost all of the seven motif-finding tools require to specify a length of the motifs to be predicted, and the majority of known binding sites in yeast have a length of about eight bases, we chose eight bases as the fixed motif length for motif-finding for all the tools except for Weeder and WeederH, for the former we used the option 'medium' as the motif length, and for the latter we used the default options. We applied each program in the 'anr' mode if available to the 5,137 orthologous intergenic sequence sets from the fungal genomes (see Methods), and considered the best predicted (top1), top 5, top 10, top 15, and top 20 motifs for the evaluation. We used the predictions from the yeast genome for the evaluation, because there are 2,932 known binding sites belonging to 99 TFs from the genome in the input intergenic sequences sets. However, since not all binding sites in the intergenic sequences in yeast are known, to evaluate prediction specificity, we define the low bound of specificity (lbSp) as the number of recovered known binding sites divided by the number of predicted sites. As shown in Table <xref ref-type="table" rid="T2">2</xref>
, Weeder recovers the highest number of known binding sites, but achieves the lowest lbSp, and BioProspector achieves the highest lbSp but recovers the fewest number of known binding sites among these programs for most of the top numbers of predictions. On the other hand, the results in Table <xref ref-type="table" rid="T2">2</xref>
 clearly show that MotifClick outperforms MEME and MotifCut in terms of both the coverage of known binding sites and lbSp. Furthermore, although Weeder recovers more known binding sites than does MotifClick for each top number of predictions, this is at the cost of its low prediction specificity. For instance, the number of predicted sites (24,916) in the best motifs (top 1) returned by Weeder is very close to that (23,417) of the top 5 motifs returned by MotifClick, but MotifClick recovers more known binding sites in its all top 5 motifs than does Weeder in its all best motifs (1,200 vs. 969). Therefore, Weeder is likely to have much more false positive predictions than the other tools, and MotifClick is the best at balancing the true positives and false positives. As shown in Table <xref ref-type="table" rid="T2">2</xref>
, the two phylogenetic motif-finding tools WeederH and FootPrinter do not perform very well on our dataset. The possible reason for WeederH could be that it only has the 'oops' mode ('one occurrence per sequence') while some of our input sequences contain more than one binding site.</p>
<table-wrap id="T2" position="float"><label>Table 2</label>
<caption><p>Evaluation on the phylogenetic footprinting datasets from fungal genomes using the predictions in the yeast genome</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th></th>
<th></th>
<th align="left">Top 1</th>
<th align="left">Top 5</th>
<th align="left">Top 10</th>
<th align="left">Top 15</th>
<th align="left">Top 20</th>
</tr>
</thead>
<tbody><tr><td align="left">MotifClick</td>
<td align="center">BS (MF)</td>
<td align="left">585 (67)</td>
<td align="left"><bold>1200 </bold>
(85)</td>
<td align="left">1638 (92)</td>
<td align="left">1923 (95)</td>
<td align="left">2107 (95)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">7158 (<bold>0.081</bold>
)</td>
<td align="left"><bold>24916 </bold>
(0.048)</td>
<td align="left">41752 (0.039)</td>
<td align="left">55084 (0.035)</td>
<td align="left">65852 (0.032)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">MEME</td>
<td align="center">BS (MF)</td>
<td align="left">754 (70)</td>
<td align="left"><bold>1202 </bold>
(85)</td>
<td align="left">1615 (87)</td>
<td align="left">1931 (92)</td>
<td align="left">2087 (95)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">10107 (0.074)</td>
<td align="left">34010 (0.035)</td>
<td align="left">49958 (0.032)</td>
<td align="left">60805 (0.031)</td>
<td align="left">69709 (0.030)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">MotifCut</td>
<td align="center">BS (MF)</td>
<td align="left">474 (65)</td>
<td align="left">1189 (85)</td>
<td align="left">1641 (86)</td>
<td align="left">1893 (93)</td>
<td align="left">1983 (95)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">7632 (0.062)</td>
<td align="left">28074 (0.041)</td>
<td align="left">47583 (0.034)</td>
<td align="left">61107 (0.031)</td>
<td align="left">67017 (0.030)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">BioProspecter</td>
<td align="center">BS (MF)</td>
<td align="left">780 (79)</td>
<td align="left">1145 (84)</td>
<td align="left">1465 (86)</td>
<td align="left">1701 (89)</td>
<td align="left">1911 (92)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">10049 (0.078)</td>
<td align="left">20418 (<bold>0.056</bold>
)</td>
<td align="left">31935 (0.046)</td>
<td align="left">42305 (0.040)</td>
<td align="left">52296 (0.037)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">Weeder</td>
<td align="center">BS (MF)</td>
<td align="left"><bold>969 </bold>
(77)</td>
<td align="left"><bold>1698 </bold>
(88)</td>
<td align="left">2063 (92)</td>
<td align="left">2255 (94)</td>
<td align="left">2396 (94)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left"><bold>23417 </bold>
(0.041)</td>
<td align="left">56440 (0.030)</td>
<td align="left">81374 (0.025)</td>
<td align="left">96046 (0.023)</td>
<td align="left">106872 (0.022)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">WeederH</td>
<td align="center">BS (MF)</td>
<td align="left">404 (64)</td>
<td align="left">1154 (79)</td>
<td align="left">1614 (89)</td>
<td align="left">1905 (91)</td>
<td align="left">2129 (94)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">5092 (0.079)</td>
<td align="left">25363 (0.045)</td>
<td align="left">49929 (0.032)</td>
<td align="left">74180 (0.026)</td>
<td align="left">97300 (0.022)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">FootPrinter</td>
<td align="center">BS (MF)</td>
<td align="left">452 (66)</td>
<td align="left">1148 (78)</td>
<td align="left">1579 (86)</td>
<td align="left">1854 (91)</td>
<td align="left">2073 (94)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">6173 (0.073)</td>
<td align="left">27451 (0.042)</td>
<td align="left">48533 (0.033)</td>
<td align="left">77249 (0.024)</td>
<td align="left">86437 (0.024)</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>BS, number of recovered known binding sites; MF, number of recovered motifs; PS, number of predicted sites; lbSp = BS/PS, lower bound of specificity.</p>
</table-wrap-foot>
</table-wrap>
</sec>
<sec><title>2.2 Bacterial datasets</title>
<p>To compare our program with the other programs for phylogenetic footprinting using the orthologous interoperonic sequence sets from <italic>E. coli </italic>
K12 and other 55 γ-protoebacterial genomes, we chose 16 bases as the fixed motif length for the motif-finding tools as most bacterial binding sites have a length of 12-22 bases [<xref ref-type="bibr" rid="B26">26</xref>
]. Weeder, WeederH, and FootPrinter were not evaluated here as they are not designed to find a binding site longer than 12 bases. As shown in Table <xref ref-type="table" rid="T3">3</xref>
, MotifClick and BioProspector achieve the highest lbSp in most cases among these tools, but MotifClick recovers more known binding sites than does BioProspector. Moreover, MotifClick and MEME recover the largest number of known binding sites in most cases among these tools, but MotifClick has higher lbSp than does MEME. Therefore MotifClick is the best not only for binding site coverage but also for lbSp.</p>
<table-wrap id="T3" position="float"><label>Table 3</label>
<caption><p>Evaluation on the phylogenetic footprinting datasets from γ-proteobacterial genomes using the predictions in the <italic>E. coli </italic>
K12 genome</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th></th>
<th></th>
<th align="left">Top 1</th>
<th align="left">Top 5</th>
<th align="left">Top 10</th>
<th align="left">Top 15</th>
<th align="left">Top 20</th>
</tr>
</thead>
<tbody><tr><td align="left">MotifClick</td>
<td align="left">BS (MF)</td>
<td align="left">331 (85)</td>
<td align="left">793 (108)</td>
<td align="left">1055 (114)</td>
<td align="left">1186 (114)</td>
<td align="left">1262 (117)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">2575 (<bold>0.129</bold>
)</td>
<td align="left">7706 (<bold>0.103</bold>
)</td>
<td align="left">11056 (0.095)</td>
<td align="left">12779 (0.093)</td>
<td align="left">13592 (<bold>0.093</bold>
)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">MEME</td>
<td align="center">BS (MF)</td>
<td align="left">298 (83)</td>
<td align="left">877 (109)</td>
<td align="left">1134 (115)</td>
<td align="left">1202 (117)</td>
<td align="left">1233 (117)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">3352 (0.089)</td>
<td align="left">14243 (0.062)</td>
<td align="left">20999 (0.054)</td>
<td align="left">23912 (0.050)</td>
<td align="left">25412 (0.049)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">MotifCut</td>
<td align="center">BS (MF)</td>
<td align="left">241 (75)</td>
<td align="left">487 (89)</td>
<td align="left">544 (96)</td>
<td align="left">640 (102)</td>
<td align="left">744 (107)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">1942 (0.124)</td>
<td align="left">4763 (0.102)</td>
<td align="left">6552 (0.083)</td>
<td align="left">9145 (0.070)</td>
<td align="left">10408 (0.071)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">BioProspecter</td>
<td align="center">BS (MF)</td>
<td align="left">354 (85)</td>
<td align="left">743 (102)</td>
<td align="left">953 (112)</td>
<td align="left">1056 (112)</td>
<td align="left">1150 (116)</td>
</tr>
<tr><td></td>
<td colspan="6"><hr></hr>
</td>
</tr>
<tr><td></td>
<td align="center">PS (lbSp)</td>
<td align="left">4950 (0.072)</td>
<td align="left">7678 (0.097)</td>
<td align="left">10090 (<bold>0.107</bold>
)</td>
<td align="left">11287 (<bold>0.094</bold>
)</td>
<td align="left">12306 (<bold>0.093</bold>
)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">MotifClick + MEME</td>
<td align="center">BS (MF)</td>
<td align="left">474 (98)</td>
<td align="left">1029 (114)</td>
<td align="left">1259 (118)</td>
<td align="left">1335 (120)</td>
<td align="left">1357 (120)</td>
</tr>
<tr><td colspan="7"><hr></hr>
</td>
</tr>
<tr><td align="left">MEME + BioProspector</td>
<td align="center">BS (MF)</td>
<td align="left">472 (92)</td>
<td align="left">1051 (115)</td>
<td align="left">1258 (118)</td>
<td align="left">1312 (119)</td>
<td align="left">1339 (119)</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>BS, number of recovered known binding sites; MF, number of recovered motifs; PS, number of predicted sites; lbSp = BS/PS, lower bound of specificity.</p>
</table-wrap-foot>
</table-wrap>
<p>In addition, we also evaluated the complementary effects of MotifClick with other two best performers MEME and BioProspector. As shown in the last four rows of Table <xref ref-type="table" rid="T3">3</xref>
, the combination of MotifClick and MEME recovers more binding sites and motifs than the combination of MEME and BioProspector, suggesting again that MotifClick is well complementary with other tools.</p>
</sec>
</sec>
</sec>
</sec>
<sec><title>Conclusions</title>
<p>We have developed a novel graph-theoretic algorithm, MotifClick, for <italic>cis</italic>
-regulatory binding site prediction, and have demonstrated that it outperforms several current leading motif-finding tools on both synthetic and real datasets, especially when the nucleotide distribution of a motif is similar to that of its background sequence. Furthermore, MotifClick is the best at balancing the prediction specificity and sensitivity among the tools evaluated. In addition, MotifClick is well complementary with a few other leading motif-finding tools, thus can be used in combination with these tools to improve binding site predictions in ensemble algorithms such as WebMOTIFS [<xref ref-type="bibr" rid="B50">50</xref>
], EMD [<xref ref-type="bibr" rid="B51">51</xref>
], GLECLUBS [<xref ref-type="bibr" rid="B26">26</xref>
] and eGLECLUBS[<xref ref-type="bibr" rid="B52">52</xref>
].</p>
<p>In the perspective of algorithm design, MotifClick has several main advantages over most existing methods in general: (a) Besides largely reducing the graph size, our use of 2(<italic>k </italic>
- 1) -mers avoids the drawbacks of directly using <italic>k</italic>
-mers by other algorithms, caused by the fact that two binding sites of a TF may sometimes have fewer matches than one of their neighboring <italic>k</italic>
-mers. (b) The merged cliques generated by our algorithm can capture more binding sites of a TF than the consensus and PSSM models, in particular, when the binding sites of a TF can be divided into distinct sub-motifs. (c) Although each clique is found by a greedy strategy, the enumeration of maximal cliques can guarantee our algorithm not to be trapped in a local optimum. And (d) since we ignore some <italic>k</italic>
-mers that are less likely to be true binding sites, although MotifClick is a word-based method, it does not exhaustively enumerate all the <italic>k</italic>
-mers.</p>
</sec>
<sec sec-type="methods"><title>Methods</title>
<sec><title>Datasets</title>
<sec><title>1. Binding sites and their background sequences</title>
<p>Binding sites from five databases SGD [<xref ref-type="bibr" rid="B27">27</xref>
], RegulonDB [<xref ref-type="bibr" rid="B28">28</xref>
], DBTBS [<xref ref-type="bibr" rid="B29">29</xref>
], Redfly [<xref ref-type="bibr" rid="B30">30</xref>
], and JASPAR [<xref ref-type="bibr" rid="B31">31</xref>
] were downloaded from their respective websites. The background sequences (i.e., genomic sequences in which the binding sites are located) of binding sites were downloaded from the NCBI ftp server (<ext-link ext-link-type="ftp" xlink:href="ftp://ftp.ncbi.nih.gov">ftp://ftp.ncbi.nih.gov</ext-link>
).</p>
</sec>
<sec><title>2. Synthetic datasets</title>
<p>Tompa <italic>et al</italic>
. [<xref ref-type="bibr" rid="B32">32</xref>
] have designed three benchmarks, i.e., the 'real', the 'generic', and the 'Markov' benchmarks using 56 eukaryotic motifs from TRANSFAC for evaluating the performance of motif-finding tools. More recently, Sandve <italic>et al</italic>
. [<xref ref-type="bibr" rid="B53">53</xref>
] designed an updated suite of three improved benchmarks using 114 motifs from TRANSFAC. However, it is probably inappropriate for us to employ Tompa's or Sandve's benchmarks to compare MotifClick with other tools because both benchmarks were created using only eukaryotic binding sites, and each sequence in Sandve's benchmarks contains exactly one binding site and MotifClick is not designed for the mode 'one occurrence per sequence' (i.e., 'oops'). Therefore, in order to test our algorithms in the 'any-number of repetitions' ('anr') mode and on finding binding sites of both prokaryotes and eukaryotes, we have designed our own synthetic datasets and real datasets while only using Sandve's benchmarks to train some cutoffs in the MotifClick algorithm.</p>
<p>To construct synthetic datasets for the evaluation of our algorithm, we selected motifs with a length of eight and 16 bases and information contents about 12 (i.e., almost six positions are conserved) and 16 bits (i.e., almost eight positions are conserved), respectively, from the downloaded datasets. Each motif consists of 20 binding sites. If the original motif contains more than 20 binding sites, then the binding sites were selected to maintain the level of information contents mentioned above. These two motif lengths were chosen for the evaluation, because the majority of eukaryotic motifs have a length from seven to 10 bases, and the majority of prokaryotic motifs have a length from 12 to 22 bases. In an experiment, the 20 binding sites in a motif are implanted in 20 background sequences of length 400, 600, 800 and 1,000 bases, respectively, by randomly replacing a segment of original sequence of the same size of the binding site. Specifically, for each background size, each of the 20 binding sites of a motif was randomly implanted in one of 20 background sequences generated by a third-order Markov model; some sequences may be implanted with more than one binding site (i.e., the 'anr' mode), while some sequence may not be implanted with any binding site at all. The transition probabilities of the third-order Markov models were estimated from all intergenic sequences of the host genomes (<italic>Saccharomyces cerevisiae </italic>
for the database SGD, <italic>Drosophila melanogaster </italic>
for Redfly, <italic>E. coli </italic>
K12 for RegulonDB, and <italic>B. subtilis </italic>
for DBTBS). For each background size, the results are the statistics of 100 repeated experiments of each motif with each binding site in the motif being implanted in 100 different sets of background sequences.</p>
</sec>
<sec><title>3. Phylogenetic footprinting datasets</title>
<sec><title>3.1 Fungal datasets</title>
<p>The intergenic sequence files of yeast (<italic>S. cerevisiae</italic>
) and other six fungal genomes (<italic>S. bayanus</italic>
, <italic>S. castellii</italic>
, <italic>S. kluyveri</italic>
, <italic>S. kudriavzevii</italic>
, <italic>S. mikatae</italic>
, and <italic>S. paradoxus</italic>
) were downloaded from the SGD ftp server (ftp://genome-ftp.stanford.edu/pub/yeast/data_download/sequence/fungal_genomes). The orthologous groups in SGD were compiled from two previous studies [<xref ref-type="bibr" rid="B34">34</xref>
,<xref ref-type="bibr" rid="B54">54</xref>
]. For each group of orthologous genes, we extracted up to 1,000 bases upstream intergenic region of each gene to form an orthologous sequence set. After deleting the sequence sets that contain fewer than five orthologs, we obtained 5,137 orthologous sequence sets, which contain 2,932 known binding sites belonging to 99 TFs in <italic>S. cerevisiae</italic>
.</p>
</sec>
<sec><title>3.2 Bacterial datasets</title>
<p>A total of 2,313 orthologous inter-operonic sequence sets from <italic>E. coli </italic>
K12 and other 55 closely-related γ-proteobacterial genomes were taken from our previous work [<xref ref-type="bibr" rid="B26">26</xref>
]. Orthologous genes between two genomes were predicted by bidirectional best hits (BDBH) method [<xref ref-type="bibr" rid="B55">55</xref>
] using BLASTP with an E-value cutoff 10<sup>-20 </sup>
for both searches. These sequences contain 1,411 known binding sites belonging to 122 TFs in <italic>E. coli </italic>
K12 according to the RegulonDB v6.0 database [<xref ref-type="bibr" rid="B28">28</xref>
]. All the datasets are available at: <ext-link ext-link-type="uri" xlink:href="http://motifclick.uncc.edu">http://motifclick.uncc.edu</ext-link>
.</p>
</sec>
</sec>
</sec>
<sec><title>The algorithm</title>
</sec>
<sec><title>1 Graph construction</title>
<p>Let <italic>S</italic>
<sub>1</sub>
, <italic>S</italic>
<sub>2</sub>
,... <italic>S</italic>
<sub><italic>n </italic>
</sub>
be the set of input sequences, and each sequence <italic>S</italic>
<sub><italic>i </italic>
</sub>
be a string of nucleotides (<italic>a</italic>
<sub><italic>i</italic>
1</sub>
,..., <italic>a</italic>
<sub><italic>iL</italic>
</sub>
). For each <italic>S</italic>
<sub><italic>i</italic>
</sub>
, we break it into a set of 2(<italic>k </italic>
- 1)-mers {<italic>s</italic>
<sub><italic>ij </italic>
</sub>
= (<italic>a</italic>
<sub><italic>i</italic>
,(<italic>k</italic>
-1)<italic>j</italic>
+1</sub>
,...,<italic>a</italic>
<sub><italic>i</italic>
,(<italic>k</italic>
-1)(<italic>j</italic>
+2)</sub>
)} for all possible <italic>j </italic>
(<italic>j </italic>
= 0, 1, ... ; the last string may be shorter than 2(<italic>k </italic>
- 1), but must be longer than <italic>k </italic>
- 1) (Figure <xref ref-type="fig" rid="F1">1</xref>
). Because any two such adjacent strings have (<italic>k </italic>
- 1) overlapping positions, any <italic>k</italic>
-mer in <italic>S</italic>
<sub><italic>i </italic>
</sub>
can be located in only one of the 2(<italic>k </italic>
- 1)-mers. We construct a graph <italic>G</italic>
=(<italic>V</italic>
,<italic>E</italic>
) using all of the strings {<italic>s</italic>
<sub><italic>ij</italic>
</sub>
} as the set of vertices <italic>V=</italic>
{ <italic>v</italic>
<sub><italic>ij </italic>
</sub>
}. We connect any two vertices <italic>v</italic>
<sub><italic>ij </italic>
</sub>
and <italic>v</italic>
<sub><italic>ht </italic>
</sub>
if the weight of the edge is greater than a cutoff <italic>α</italic>
. Therefore, <italic>G </italic>
is a graph in which any two vertices from any sequences (even the same sequence) can be joined by an edge. We now describe how to assign an appropriate weight to each edge.</p>
<p>Given two vertices <italic>v</italic>
<sub><italic>ij </italic>
</sub>
and <italic>v</italic>
<sub><italic>ht</italic>
</sub>
, let <italic>K</italic>
<sub><italic>ij </italic>
</sub>
and <italic>K</italic>
<sub><italic>ht </italic>
</sub>
be the sets of all <italic>k</italic>
-mers in the corresponding 2(<italic>k </italic>
- 1)-mers <italic>s</italic>
<sub><italic>ij </italic>
</sub>
and <italic>s</italic>
<sub><italic>ht </italic>
</sub>
respectively. The weight <italic>w</italic>
<sub><italic>ijht </italic>
</sub>
between <italic>v</italic>
<sub><italic>ij </italic>
</sub>
and <italic>v</italic>
<sub><italic>ht </italic>
</sub>
is defined as:<disp-formula id="bmcM1"><label>(1)</label>
<graphic xlink:href="1471-2105-12-238-i2.gif"></graphic>
</disp-formula>
</p>
<p>where <italic>M</italic>
(<italic>a</italic>
, <italic>b</italic>
) is the number of matches between a pair of <italic>k</italic>
-mers <italic>a </italic>
and <italic>b</italic>
. That is, the weight of an edge in <italic>E </italic>
is defined as the maximum number of matches of all of <italic>k</italic>
-mers in the corresponding two 2(<italic>k </italic>
- 1)-mers. However, we exclude some <italic>k</italic>
-mers in the strings <italic>s</italic>
<sub><italic>ij </italic>
</sub>
and <italic>s</italic>
<sub><italic>ht </italic>
</sub>
from the sets <italic>K</italic>
<sub><italic>ij </italic>
</sub>
and <italic>K</italic>
<sub><italic>ht</italic>
</sub>
, respectively, based on the following observations. First, as shown in Figure <xref ref-type="fig" rid="F2">2A</xref>
, over 95% known binding sites in the databases SGD [<xref ref-type="bibr" rid="B27">27</xref>
], RegulonDB [<xref ref-type="bibr" rid="B28">28</xref>
], DBTBS [<xref ref-type="bibr" rid="B29">29</xref>
], Redfly [<xref ref-type="bibr" rid="B30">30</xref>
] and JASPAR [<xref ref-type="bibr" rid="B31">31</xref>
] have an SSD < 0.3. Second, as shown in Figure <xref ref-type="fig" rid="F2">2B</xref>
, more than 97% binding sites in the five databases have the longest single-nucleotide segments shorter than 60% of the binding sites. Third, we also observe that more than 95% binding sites in the five databases consist of at least 3 of the 4 types of nucleotides A, C, G and T (data not shown). Therefore, we exclude in <italic>K</italic>
<sub><italic>ij </italic>
</sub>
the <italic>k</italic>
-mers 1) that have an SSD > 0.3, 2) that have a single-nucleotide segment longer than 60% of its length, or 3) that consist of at most 2 types of nucleotides. In the MotifClick program, we provide an option '-SSD' that allows a user to adjust the cutoff of SSD (the default cutoff is 0.3) in order to find motifs that have a similar nucleotide distribution to that of their background sequences.</p>
<p>In order to choose a proper weight cutoff <italic>α </italic>
for creating the edge set <italic>E</italic>
, we first randomly select a number <italic>N </italic>
= max{10, <italic>n</italic>
/4}of <italic>k</italic>
-mers from the sequence set <italic>S</italic>
<sub>1</sub>
, <italic>S</italic>
<sub>2</sub>
, ..., <italic>S</italic>
<sub><italic>n</italic>
</sub>
. For each of such <italic>k</italic>
-mer <italic>a </italic>
and each input sequence <italic>S</italic>
<sub><italic>i</italic>
</sub>
, we calculate the maximum number of matches <italic>M</italic>
(<italic>a</italic>
, <italic>S</italic>
<sub><italic>i</italic>
</sub>
) between <italic>a </italic>
and <italic>S</italic>
<sub><italic>i </italic>
</sub>
by scanning <italic>S</italic>
<sub><italic>i </italic>
</sub>
with <italic>a </italic>
(if <italic>a </italic>
is from <italic>S</italic>
<sub><italic>i</italic>
</sub>
, we skip the location of <italic>a </italic>
in <italic>S</italic>
<sub><italic>i</italic>
</sub>
.). Therefore, we have (<italic>n</italic>
-1)<italic>N </italic>
of such values. We calculate the average value <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i3.gif"></inline-graphic>
</inline-formula>
 of these match numbers after removing 5% minimum ones. To test possible bias of our sampling process for computing <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i4.gif"></inline-graphic>
</inline-formula>
, we ran the sampling procedure 1000 times on a set of 1000 × 40 input sequences to find 8-mers, 12-mers, and 16-mers, respectively, and found that <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i5.gif"></inline-graphic>
</inline-formula>
 values are identical for more than 99% of samples (data not shown). Therefore, our sampling strategy is not biased and sufficient. We assume that the average number of matches among the binding sites of a TF should be larger than that of the randomly selected <italic>k</italic>
-mers. Then we set the default weight cutoff <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i6.gif"></inline-graphic>
</inline-formula>
. In the MotifClick program, we also add an option (-s 0) for predicting more degenerate binding sites by setting <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i7.gif"></inline-graphic>
</inline-formula>
.</p>
<sec><title>2 Finding and merging cliques</title>
<p>A maximal clique is a clique that is not included in a larger clique in a graph. Listing all of the maximal cliques (the total number is an exponential function of the number of vertices) and finding the maximum clique in a graph is NP-hard [<xref ref-type="bibr" rid="B56">56</xref>
]. Therefore, instead of finding the maximum clique, we intend to find a maximum clique associated with each vertex <italic>v </italic>
in the graph <italic>G </italic>
= (<italic>V</italic>
,<italic>E</italic>
). To this end, we define the neighborhood subgraph <italic>N</italic>
(<italic>v</italic>
) of a vertex <italic>v </italic>
as the subgraph induced by <italic>v </italic>
and its neighbor vertices. Clearly, all maximal and maximum cliques containing the vertex <italic>v </italic>
must be in <italic>N</italic>
(<italic>v</italic>
). We use a greedy strategy to find exactly one maximal weighted clique associated with <italic>v </italic>
in <italic>N</italic>
(<italic>v</italic>
) by sequentially deleting its minimum-degree neighbor vertex until the degrees of the remaining vertices are equal to one another. If at least two vertices have the same minimum degree, we break the tie by deleting the one with the minimum sum of weights of its incident edges. An example of using this algorithm to find a clique is shown in Figure <xref ref-type="fig" rid="F7">7</xref>
. Note that this greedy strategy cannot guarantee the resulting clique is the maximum clique of the neighborhood subgraph <italic>N</italic>
(<italic>v</italic>
), but it can guarantee that the clique is a maximal one. The time complexity of the procedure is <italic>O</italic>
(<italic>d</italic>
<sup>2</sup>
(<italic>v</italic>
)) if the degree of the vertex <italic>v </italic>
is <italic>d</italic>
(<italic>v</italic>
). Since the graph <italic>G </italic>
is usually sparse, this greedy strategy is rather efficient. In practice, to ensure the sparsity of the graph, we reset <italic>α </italic>
= α + 1 until <italic>D </italic>
is smaller than the option value if the graph density <italic>D </italic>
= | <italic>V</italic>
 | / | <italic>E</italic>
 | is too high.</p>
<fig id="F7" position="float"><label>Figure 7</label>
<caption><p><bold>The procedure for finding the maximal clique associated with the black vertex in its neighborhood subgraph</bold>
. We first delete the grey vertex that has the minimum degree, and then break the tie of the dotted and streaked vertices by deleting the streaked one as it has a smaller sum of weights on the incident edges.</p>
</caption>
<graphic xlink:href="1471-2105-12-238-7"></graphic>
</fig>
<p>Clearly, by applying the greedy algorithm to the neighborhood graphs of all vertices, we can obtain |<italic>V</italic>
| maximal cliques. Therefore, this greedy algorithm ensures that each vertex is included in at least one of the resulting cliques, and it cannot be trapped into a local optimum. However, there may be overlapping or even redundant cliques in the |<italic>V</italic>
| maximal cliques. Moreover, as we indicated earlier, cliques are too strict for clustering the binding sites of the same TF, as the binding sites of the same TF can be divided into different cliques due to the low similarity of different sub-motifs of the TF. Therefore, we need to combine these cliques if possible.</p>
<p>To this end, we first select the clique with the maximum sum of edge weights as a core clique, denoted by <italic>C</italic>
. We initialize the group of merged cliques <italic>MC</italic>
: = {<italic>C</italic>
}. For each of the other cliques <italic>C'</italic>
, we calculate two overlapping rates between C and <italic>C'</italic>
 as follows:<disp-formula id="bmcM2"><label>(2)</label>
<graphic xlink:href="1471-2105-12-238-i8.gif"></graphic>
</disp-formula>
</p>
<p>If either r & ≥ γ or R & ≥ <italic>β</italic>
, where <italic>γ </italic>
and <italic>β </italic>
are two preset cutoff values, and <italic>γ </italic>
><italic>β </italic>
because in most cases | <italic>C'</italic>
 | ≤ | <italic>C </italic>
|, then we set <italic>MC</italic>
: = <italic>MC </italic>
∪ {<italic>C'</italic>
}. We obtain the final group of cliques <italic>MC </italic>
by traversing all cliques. We tested our program with different combinations of <italic>γ </italic>
and <italic>β</italic>
, where <italic>γ </italic>
and <italic>β </italic>
took values of 1/2, 2/3, 3/4, 3/5, 4/5, and 5/6, on the three benchmark suites ('algorithm Markov', 'algorithm real', and 'model real') proposed by Sandve <italic>et al</italic>
. [<xref ref-type="bibr" rid="B53">53</xref>
]. We found that the algorithm achieved the highest average nucleotide-level correlation coefficient (nCC) when (<italic>γ</italic>
,<italic>β</italic>
) = (3/4, 3/5) for the three suites (the average nCC = 0.062). The two cutoffs can be understood intuitionally: if <italic>C</italic>
' is a 4-vertex clique sharing a triangle (3-vertex clique) with <italic>C</italic>
, or <italic>C </italic>
is a 5-vertex clique sharing a triangle with <italic>C'</italic>
, then <italic>C </italic>
and <italic>C</italic>
' can be merged together.</p>
</sec>
<sec><title>3 Aligning and refining sequences in merged cliques</title>
<p>The sequences in merged cliques <italic>MC </italic>
are 2(<italic>k </italic>
-1)-mers, but some of them may not contain real binding sites. To find a true <italic>k</italic>
-mer motif in <italic>MC</italic>
, we need to filter out the spurious ones. To this end, we construct a multipartite graph <italic>C</italic>
' by connecting any two <italic>k</italic>
-mers from two different 2(<italic>k </italic>
- 1)-mers in <italic>MC </italic>
if the number of matches between them is not less than <inline-formula><inline-graphic xlink:href="1471-2105-12-238-i9.gif"></inline-graphic>
</inline-formula>
. We identify the largest neighborhood graph <italic>N</italic>
* as the final motif by enumerating the neighborhood subgraph <italic>N</italic>
(<italic>v'</italic>
) of each vertex <italic>v</italic>
' in <italic>G'</italic>
. If at least two neighborhood subgraphs have the same largest size, we break the tie by selecting the one with the maximum sum of edge weights. The similarity between each pair of <italic>k</italic>
-mers in <italic>N</italic>
* is generally high because of the high density of the merged cliques <italic>MC</italic>
.</p>
<p>In practice, one often wants to find more than one motif from a set of input sequences. We achieve this goal by repeatedly applying the merging and refining steps described above on the remaining maximal cliques after removing those that are merged into <italic>MC</italic>
. Notably, a sequence could appear in different top motifs due to its appearance in multiple cliques. However, any two returned motifs usually cannot overlap with each other in a large scale because of the clique-merging step.</p>
</sec>
</sec>
<sec><title>Performance and complementarity measurements</title>
<p>We consider that a binding site is identified by a motif-finding tool if at least 50% nucleotides of the binding site overlap with the predicted sequence. For the evaluations on the synthetic datasets, we define the following accuracy metrics: (1) Sensitivity: Sn = TP/(TP + FN), (2) Specificity: Sp = TP/(TP + FP), (3) Performance coefficient: PC = TP/(TP + FP + FN), and (4) F-measure or Harmonic mean: F = 2*Sn*Sp/(Sn + Sp), where TP, FP, and FN are the numbers of true positive, false positive, and false negative predictions, respectively. PC is an integrated measurement of sensitivity and specificity, while F-measure is an overall performance measurement. Hu <italic>et al</italic>
. [<xref ref-type="bibr" rid="B33">33</xref>
] have shown that PC has several advantages over correlation coefficient (CC), and that F-measure tends to penalize more the imbalance of sensitivity and specificity than does geometric or arithmetic mean.</p>
<p>We hope that MotifClick can identify some binding sites that are missed by other algorithms, in particular, when the SSD of a binding site is low, thus it is complementary to these tools. To evaluate the complementarity of the predictions of two tools, we compute a log-odds ratio as used in MotifCut [<xref ref-type="bibr" rid="B14">14</xref>
], which measures the correlation between the performance of two tools <italic>A </italic>
and <italic>B </italic>
as follows:<disp-formula id="bmcM3"><label>(3)</label>
<graphic xlink:href="1471-2105-12-238-i10.gif"></graphic>
</disp-formula>
</p>
<p>Where <italic>P</italic>
(<italic>A </italic>
∩ <italic>B</italic>
) is the probability of a binding site being correctly identified by the both algorithms <italic>A </italic>
and <italic>B</italic>
, and <italic>P</italic>
(<italic>X</italic>
) is the probability of a binding site being correctly identified by algorithm <italic>X</italic>
. Clearly, <italic>P</italic>
(<italic>A </italic>
∩ <italic>B</italic>
) = <italic>P</italic>
(<italic>A</italic>
) · <italic>P</italic>
(<italic>B</italic>
) if <italic>A </italic>
and <italic>B </italic>
are independent. Note that we restrict the log-odds ratio to the binding sites found by at least one algorithm and missed by at least one other algorithm. Unlike the Pearson correlation coefficient that may evaluate two high-performing algorithms to be highly correlated, because some binding sites may be found by both algorithms, and some others may be also missed by both algorithms, the log-odds ratio is able to capture the subtle difference in the results of two high-performing algorithms.</p>
</sec>
</sec>
<sec><title>Availability</title>
<p>The programs of MotifClick were implemented in standard C++. The source code, executables and a web server of MotifClick are freely and publicly available at: <ext-link ext-link-type="uri" xlink:href="http://motifclick.uncc.edu/">http://motifclick.uncc.edu/</ext-link>
.</p>
</sec>
<sec><title>Abbreviations</title>
<p>TF: transcription factor; PSSM: position-specific scoring matrices; oops: one occurrence per sequence; anr: any-number of repetitions; SSD: sum of squared distance; nCC: nucleotide-level correlation coefficient; CC: correlation coefficient; TP: true positive; FP: false positive; FN: false negative; Sn: sensitivity; Sp: specificity; PC: performance coefficient; lbSp: low bound of specificity; BDBH: bidirectional best hits; <italic>E. coli</italic>
: <italic>Escherichia coli</italic>
; <italic>B. subtilis</italic>
: <italic>Bacillus subtilis</italic>
; <italic>S. cerevisiae</italic>
: <italic>Saccharomyces cerevisiae</italic>
; <italic>S. bayanus</italic>
: <italic>Saccharomyces bayanus</italic>
; <italic>S. castellii</italic>
: <italic>Saccharomyces castellii</italic>
; <italic>S. kluyveri</italic>
: <italic>Saccharomyces kluyveri</italic>
; <italic>S. kudriavzevii</italic>
: <italic>Saccharomyces kudriavzevii</italic>
; <italic>S. mikatae</italic>
: <italic>Saccharomyces mikatae</italic>
; <italic>S. paradoxus</italic>
: <italic>Saccharomyces paradoxus.</italic>
</p>
</sec>
<sec><title>Competing interests</title>
<p>The authors declare that they have no competing interests.</p>
</sec>
<sec><title>Authors' contributions</title>
<p>ZS conceived the project. SZ designed and conducted the experiment. SL, MN, and PP helped conduct some analysis. ZS and SZ wrote the manuscript. All authors read and approved the final manuscript.</p>
</sec>
<sec sec-type="supplementary-material"><title>Supplementary Material</title>
<supplementary-material content-type="local-data" id="S1"><caption><title>Additional file 1</title>
<p><bold>Additional file </bold>
<xref ref-type="supplementary-material" rid="S1">1</xref>
<bold>consists of two tables and 3 figures</bold>
. Table S1: Log-odds ratios of pairs of programs for predicting binding sites of eight bases with an SSD ≤ 0.06 in the synthetic datasets. Table S2: Log-odds ratios of pairs of programs for predicting binding sites of 16 bases with an SSD ≤ 0.06 in the synthetic datasets. Figure S1: Comparison of MotifClick with other three algorithms for noise tolerance. These algorithms were evaluated on three groups of synthetic datasets with sizes 400*20 (without added noise), 400*25 (with 25% added noise, and 400*30 (with 50% added noise) bases. Figure S2: Average running time of MotifClick for finding motifs of different length in different sizes of input sequence sets. The corresponding standard errors are denoted by vertical barbs. Figure S3: Evaluation of sensitivity (Sn) and specificity (Sp) of the algorithm on real datasets with different SSD values.</p>
</caption>
<media xlink:href="1471-2105-12-238-S1.PDF" mimetype="application" mime-subtype="pdf"><caption><p>Click here for file</p>
</caption>
</media>
</supplementary-material>
</sec>
</body>
<back><sec><title>Acknowledgements</title>
<p>This work was supported by grants EF0849615 and CCF1048261 from National Science Foundation to ZS and a grant from Natural Science Funding of Tianjin for Scholarly Exchange to SZ.</p>
</sec>
<ref-list><ref id="B1"><mixed-citation publication-type="journal"><name><surname>Kim</surname>
<given-names>HD</given-names>
</name>
<name><surname>Shay</surname>
<given-names>T</given-names>
</name>
<name><surname>O'Shea</surname>
<given-names>EK</given-names>
</name>
<name><surname>Regev</surname>
<given-names>A</given-names>
</name>
<article-title>Transcriptional regulatory circuits: predicting numbers from alphabets</article-title>
<source>Science</source>
<year>2009</year>
<volume>325</volume>
<issue>5939</issue>
<fpage>429</fpage>
<lpage>432</lpage>
<pub-id pub-id-type="pmid">19628860</pub-id>
</mixed-citation>
</ref>
<ref id="B2"><mixed-citation publication-type="journal"><name><surname>Reed</surname>
<given-names>JL</given-names>
</name>
<name><surname>Famili</surname>
<given-names>I</given-names>
</name>
<name><surname>Thiele</surname>
<given-names>I</given-names>
</name>
<name><surname>Palsson</surname>
<given-names>BO</given-names>
</name>
<article-title>Towards multidimensional genome annotation</article-title>
<source>Nat Rev Genet</source>
<year>2006</year>
<volume>7</volume>
<issue>2</issue>
<fpage>130</fpage>
<lpage>141</lpage>
<pub-id pub-id-type="doi">10.1038/nrg1769</pub-id>
<pub-id pub-id-type="pmid">16418748</pub-id>
</mixed-citation>
</ref>
<ref id="B3"><mixed-citation publication-type="journal"><name><surname>GuhaThakurta</surname>
<given-names>D</given-names>
</name>
<article-title>Computational identification of transcriptional regulatory elements in DNA sequence</article-title>
<source>Nucleic Acids Res</source>
<year>2006</year>
<volume>34</volume>
<issue>12</issue>
<fpage>3585</fpage>
<lpage>3598</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gkl372</pub-id>
<pub-id pub-id-type="pmid">16855295</pub-id>
</mixed-citation>
</ref>
<ref id="B4"><mixed-citation publication-type="journal"><name><surname>Aerts</surname>
<given-names>S</given-names>
</name>
<name><surname>Thijs</surname>
<given-names>G</given-names>
</name>
<name><surname>Coessens</surname>
<given-names>B</given-names>
</name>
<name><surname>Staes</surname>
<given-names>M</given-names>
</name>
<name><surname>Moreau</surname>
<given-names>Y</given-names>
</name>
<name><surname>De Moor</surname>
<given-names>B</given-names>
</name>
<article-title>Toucan: deciphering the cis-regulatory logic of coregulated genes</article-title>
<source>Nucleic Acids Res</source>
<year>2003</year>
<volume>31</volume>
<issue>6</issue>
<fpage>1753</fpage>
<lpage>1764</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gkg268</pub-id>
<pub-id pub-id-type="pmid">12626717</pub-id>
</mixed-citation>
</ref>
<ref id="B5"><mixed-citation publication-type="journal"><name><surname>Gelfand</surname>
<given-names>MS</given-names>
</name>
<article-title>Recognition of regulatory sites by genomic comparison</article-title>
<source>Res Microbiol</source>
<year>1999</year>
<volume>150</volume>
<fpage>755</fpage>
<lpage>771</lpage>
<pub-id pub-id-type="doi">10.1016/S0923-2508(99)00117-5</pub-id>
<pub-id pub-id-type="pmid">10673013</pub-id>
</mixed-citation>
</ref>
<ref id="B6"><mixed-citation publication-type="journal"><name><surname>Das</surname>
<given-names>MK</given-names>
</name>
<name><surname>Dai</surname>
<given-names>HK</given-names>
</name>
<article-title>A survey of DNA motif finding algorithms</article-title>
<source>BMC Bioinformatics</source>
<year>2007</year>
<volume>8</volume>
<issue>Suppl 7</issue>
<fpage>S21</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-8-S7-S21</pub-id>
<pub-id pub-id-type="pmid">18047721</pub-id>
</mixed-citation>
</ref>
<ref id="B7"><mixed-citation publication-type="journal"><name><surname>Sandve</surname>
<given-names>GK</given-names>
</name>
<name><surname>Drablos</surname>
<given-names>F</given-names>
</name>
<article-title>A survey of motif discovery methods in an integrated framework</article-title>
<source>Biol Direct</source>
<year>2006</year>
<volume>1</volume>
<fpage>11</fpage>
<pub-id pub-id-type="doi">10.1186/1745-6150-1-11</pub-id>
<pub-id pub-id-type="pmid">16600018</pub-id>
</mixed-citation>
</ref>
<ref id="B8"><mixed-citation publication-type="journal"><name><surname>MacIsaac</surname>
<given-names>KD</given-names>
</name>
<name><surname>Fraenkel</surname>
<given-names>E</given-names>
</name>
<article-title>Practical strategies for discovering regulatory DNA sequence motifs</article-title>
<source>PLoS Comput Biol</source>
<year>2006</year>
<volume>2</volume>
<issue>4</issue>
<fpage>e36</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pcbi.0020036</pub-id>
<pub-id pub-id-type="pmid">16683017</pub-id>
</mixed-citation>
</ref>
<ref id="B9"><mixed-citation publication-type="journal"><name><surname>Liu</surname>
<given-names>XS</given-names>
</name>
<name><surname>Brutlag</surname>
<given-names>DL</given-names>
</name>
<name><surname>Liu</surname>
<given-names>JS</given-names>
</name>
<article-title>An algorithm for finding protein-DNA binding sites with applications to chromatin-immunoprecipitation microarray experiments</article-title>
<source>Nat Biotechnol</source>
<year>2002</year>
<volume>20</volume>
<issue>8</issue>
<fpage>835</fpage>
<lpage>839</lpage>
<pub-id pub-id-type="pmid">12101404</pub-id>
</mixed-citation>
</ref>
<ref id="B10"><mixed-citation publication-type="journal"><name><surname>Pavesi</surname>
<given-names>G</given-names>
</name>
<name><surname>Mereghetti</surname>
<given-names>P</given-names>
</name>
<name><surname>Zambelli</surname>
<given-names>F</given-names>
</name>
<name><surname>Stefani</surname>
<given-names>M</given-names>
</name>
<name><surname>Mauri</surname>
<given-names>G</given-names>
</name>
<name><surname>Pesole</surname>
<given-names>G</given-names>
</name>
<article-title>MoD Tools: regulatory motif discovery in nucleotide sequences from co-regulated or homologous genes</article-title>
<source>Nucleic Acids Res</source>
<year>2006</year>
<volume>34</volume>
<issue>Web Server issue</issue>
<fpage>W566</fpage>
<lpage>570</lpage>
<pub-id pub-id-type="pmid">16845071</pub-id>
</mixed-citation>
</ref>
<ref id="B11"><mixed-citation publication-type="journal"><name><surname>Pevzner</surname>
<given-names>PA</given-names>
</name>
<name><surname>Sze</surname>
<given-names>SH</given-names>
</name>
<article-title>Combinatorial approaches to finding subtle signals in DNA sequences</article-title>
<source>Proc Int Conf Intell Syst Mol Biol</source>
<year>2000</year>
<volume>8</volume>
<fpage>269</fpage>
<lpage>278</lpage>
<pub-id pub-id-type="pmid">10977088</pub-id>
</mixed-citation>
</ref>
<ref id="B12"><mixed-citation publication-type="journal"><name><surname>Olman</surname>
<given-names>V</given-names>
</name>
<name><surname>Xu</surname>
<given-names>D</given-names>
</name>
<name><surname>Xu</surname>
<given-names>Y</given-names>
</name>
<article-title>CUBIC: identification of regulatory binding sites through data clustering</article-title>
<source>J Bioinform Comput Biol</source>
<year>2003</year>
<volume>1</volume>
<issue>1</issue>
<fpage>21</fpage>
<lpage>40</lpage>
<pub-id pub-id-type="doi">10.1142/S0219720003000162</pub-id>
<pub-id pub-id-type="pmid">15290780</pub-id>
</mixed-citation>
</ref>
<ref id="B13"><mixed-citation publication-type="journal"><name><surname>Liang</surname>
<given-names>S</given-names>
</name>
<name><surname>Samanta</surname>
<given-names>MP</given-names>
</name>
<name><surname>Biegel</surname>
<given-names>BA</given-names>
</name>
<article-title>cWINNOWER algorithm for finding fuzzy dna motifs</article-title>
<source>J Bioinform Comput Biol</source>
<year>2004</year>
<volume>2</volume>
<issue>1</issue>
<fpage>47</fpage>
<lpage>60</lpage>
<pub-id pub-id-type="doi">10.1142/S0219720004000466</pub-id>
<pub-id pub-id-type="pmid">15272432</pub-id>
</mixed-citation>
</ref>
<ref id="B14"><mixed-citation publication-type="journal"><name><surname>Fratkin</surname>
<given-names>E</given-names>
</name>
<name><surname>Naughton</surname>
<given-names>BT</given-names>
</name>
<name><surname>Brutlag</surname>
<given-names>DL</given-names>
</name>
<name><surname>Batzoglou</surname>
<given-names>S</given-names>
</name>
<article-title>MotifCut: regulatory motifs finding with maximum density subgraphs</article-title>
<source>Bioinformatics</source>
<year>2006</year>
<volume>22</volume>
<issue>14</issue>
<fpage>e150</fpage>
<lpage>157</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btl243</pub-id>
<pub-id pub-id-type="pmid">16873465</pub-id>
</mixed-citation>
</ref>
<ref id="B15"><mixed-citation publication-type="journal"><name><surname>Marschall</surname>
<given-names>T</given-names>
</name>
<name><surname>Rahmann</surname>
<given-names>S</given-names>
</name>
<article-title>Efficient exact motif discovery</article-title>
<source>Bioinformatics</source>
<year>2009</year>
<volume>25</volume>
<issue>12</issue>
<fpage>i356</fpage>
<lpage>364</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btp188</pub-id>
<pub-id pub-id-type="pmid">19478010</pub-id>
</mixed-citation>
</ref>
<ref id="B16"><mixed-citation publication-type="journal"><name><surname>Lawrence</surname>
<given-names>CE</given-names>
</name>
<name><surname>Altschul</surname>
<given-names>SF</given-names>
</name>
<name><surname>Boguski</surname>
<given-names>MS</given-names>
</name>
<name><surname>Liu</surname>
<given-names>JS</given-names>
</name>
<name><surname>Neuwald</surname>
<given-names>AF</given-names>
</name>
<name><surname>Wootton</surname>
<given-names>JC</given-names>
</name>
<article-title>Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment</article-title>
<source>Science</source>
<year>1993</year>
<volume>262</volume>
<fpage>208</fpage>
<lpage>214</lpage>
<pub-id pub-id-type="doi">10.1126/science.8211139</pub-id>
<pub-id pub-id-type="pmid">8211139</pub-id>
</mixed-citation>
</ref>
<ref id="B17"><mixed-citation publication-type="journal"><name><surname>Hughes</surname>
<given-names>JD</given-names>
</name>
<name><surname>Estep</surname>
<given-names>PW</given-names>
</name>
<name><surname>Tavazoie</surname>
<given-names>S</given-names>
</name>
<name><surname>Church</surname>
<given-names>GM</given-names>
</name>
<article-title>Computational identification of cis-regulatory elements associated with groups of functionally related genes in Saccharomyces cerevisiae</article-title>
<source>J Mol Biol</source>
<year>2000</year>
<volume>296</volume>
<issue>5</issue>
<fpage>1205</fpage>
<lpage>1214</lpage>
<pub-id pub-id-type="doi">10.1006/jmbi.2000.3519</pub-id>
<pub-id pub-id-type="pmid">10698627</pub-id>
</mixed-citation>
</ref>
<ref id="B18"><mixed-citation publication-type="journal"><name><surname>Thijs</surname>
<given-names>G</given-names>
</name>
<name><surname>Lescot</surname>
<given-names>M</given-names>
</name>
<name><surname>Marchal</surname>
<given-names>K</given-names>
</name>
<name><surname>Rombauts</surname>
<given-names>S</given-names>
</name>
<name><surname>De Moor</surname>
<given-names>B</given-names>
</name>
<name><surname>Rouze</surname>
<given-names>P</given-names>
</name>
<name><surname>Moreau</surname>
<given-names>Y</given-names>
</name>
<article-title>A higher-order background model improves the detection of promoter regulatory elements by Gibbs sampling</article-title>
<source>Bioinformatics</source>
<year>2001</year>
<volume>17</volume>
<issue>12</issue>
<fpage>1113</fpage>
<lpage>1122</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/17.12.1113</pub-id>
<pub-id pub-id-type="pmid">11751219</pub-id>
</mixed-citation>
</ref>
<ref id="B19"><mixed-citation publication-type="other"><name><surname>Liu</surname>
<given-names>X</given-names>
</name>
<name><surname>Brutlag</surname>
<given-names>DL</given-names>
</name>
<name><surname>Liu</surname>
<given-names>JS</given-names>
</name>
<article-title>BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes</article-title>
<source>PacSympBiocomput: 2001</source>
<year>2001</year>
<fpage>127</fpage>
<lpage>138</lpage>
</mixed-citation>
</ref>
<ref id="B20"><mixed-citation publication-type="journal"><name><surname>Bailey</surname>
<given-names>TL</given-names>
</name>
<name><surname>Elkan</surname>
<given-names>C</given-names>
</name>
<article-title>Fitting a mixture model by expectation maximization to discover motifs in biopolymers</article-title>
<source>Proc Int Conf Intell Syst Mol Biol</source>
<year>1994</year>
<volume>2</volume>
<fpage>28</fpage>
<lpage>36</lpage>
<pub-id pub-id-type="pmid">7584402</pub-id>
</mixed-citation>
</ref>
<ref id="B21"><mixed-citation publication-type="journal"><name><surname>Redhead</surname>
<given-names>E</given-names>
</name>
<name><surname>Bailey</surname>
<given-names>TL</given-names>
</name>
<article-title>Discriminative motif discovery in DNA and protein sequences using the DEME algorithm</article-title>
<source>BMC Bioinformatics</source>
<year>2007</year>
<volume>8</volume>
<fpage>385</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-8-385</pub-id>
<pub-id pub-id-type="pmid">17937785</pub-id>
</mixed-citation>
</ref>
<ref id="B22"><mixed-citation publication-type="journal"><name><surname>Fauteux</surname>
<given-names>F</given-names>
</name>
<name><surname>Blanchette</surname>
<given-names>M</given-names>
</name>
<name><surname>Stromvik</surname>
<given-names>MV</given-names>
</name>
<article-title>Seeder: discriminative seeding DNA motif discovery</article-title>
<source>Bioinformatics</source>
<year>2008</year>
<volume>24</volume>
<issue>20</issue>
<fpage>2303</fpage>
<lpage>2307</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btn444</pub-id>
<pub-id pub-id-type="pmid">18718942</pub-id>
</mixed-citation>
</ref>
<ref id="B23"><mixed-citation publication-type="journal"><name><surname>Valen</surname>
<given-names>E</given-names>
</name>
<name><surname>Sandelin</surname>
<given-names>A</given-names>
</name>
<name><surname>Winther</surname>
<given-names>O</given-names>
</name>
<name><surname>Krogh</surname>
<given-names>A</given-names>
</name>
<article-title>Discovery of regulatory elements is improved by a discriminatory approach</article-title>
<source>PLoS Comput Biol</source>
<year>2009</year>
<volume>5</volume>
<issue>11</issue>
<fpage>e1000562</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pcbi.1000562</pub-id>
<pub-id pub-id-type="pmid">19911049</pub-id>
</mixed-citation>
</ref>
<ref id="B24"><mixed-citation publication-type="journal"><name><surname>Sinha</surname>
<given-names>S</given-names>
</name>
<article-title>Discriminative motifs</article-title>
<source>J Comput Biol</source>
<year>2003</year>
<volume>10</volume>
<issue>3-4</issue>
<fpage>599</fpage>
<lpage>615</lpage>
<pub-id pub-id-type="doi">10.1089/10665270360688219</pub-id>
<pub-id pub-id-type="pmid">12935347</pub-id>
</mixed-citation>
</ref>
<ref id="B25"><mixed-citation publication-type="journal"><name><surname>Benos</surname>
<given-names>PV</given-names>
</name>
<name><surname>Bulyk</surname>
<given-names>ML</given-names>
</name>
<name><surname>Stormo</surname>
<given-names>GD</given-names>
</name>
<article-title>Additivity in protein-DNA interactions: how good an approximation is it?</article-title>
<source>Nucleic Acids Res</source>
<year>2002</year>
<volume>30</volume>
<issue>20</issue>
<fpage>4442</fpage>
<lpage>4451</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gkf578</pub-id>
<pub-id pub-id-type="pmid">12384591</pub-id>
</mixed-citation>
</ref>
<ref id="B26"><mixed-citation publication-type="journal"><name><surname>Zhang</surname>
<given-names>S</given-names>
</name>
<name><surname>Xu</surname>
<given-names>M</given-names>
</name>
<name><surname>Li</surname>
<given-names>S</given-names>
</name>
<name><surname>Su</surname>
<given-names>Z</given-names>
</name>
<article-title>Genome-wide de novo prediction of cis-regulatory binding sites in prokaryotes</article-title>
<source>Nucleic Acids Res</source>
<year>2009</year>
<volume>37</volume>
<issue>10</issue>
<fpage>e72</fpage>
<pub-id pub-id-type="doi">10.1093/nar/gkp248</pub-id>
<pub-id pub-id-type="pmid">19383880</pub-id>
</mixed-citation>
</ref>
<ref id="B27"><mixed-citation publication-type="journal"><name><surname>Engel</surname>
<given-names>SR</given-names>
</name>
<name><surname>Balakrishnan</surname>
<given-names>R</given-names>
</name>
<name><surname>Binkley</surname>
<given-names>G</given-names>
</name>
<name><surname>Christie</surname>
<given-names>KR</given-names>
</name>
<name><surname>Costanzo</surname>
<given-names>MC</given-names>
</name>
<name><surname>Dwight</surname>
<given-names>SS</given-names>
</name>
<name><surname>Fisk</surname>
<given-names>DG</given-names>
</name>
<name><surname>Hirschman</surname>
<given-names>JE</given-names>
</name>
<name><surname>Hitz</surname>
<given-names>BC</given-names>
</name>
<name><surname>Hong</surname>
<given-names>EL</given-names>
</name>
<etal></etal>
<article-title>Saccharomyces Genome Database provides mutant phenotype data</article-title>
<source>Nucleic Acids Res</source>
<year>2010</year>
<volume>38</volume>
<issue>Database issue</issue>
<fpage>D433</fpage>
<lpage>436</lpage>
<pub-id pub-id-type="pmid">19906697</pub-id>
</mixed-citation>
</ref>
<ref id="B28"><mixed-citation publication-type="journal"><name><surname>Gama-Castro</surname>
<given-names>S</given-names>
</name>
<name><surname>Jimenez-Jacinto</surname>
<given-names>V</given-names>
</name>
<name><surname>Peralta-Gil</surname>
<given-names>M</given-names>
</name>
<name><surname>Santos-Zavaleta</surname>
<given-names>A</given-names>
</name>
<name><surname>Penaloza-Spinola</surname>
<given-names>MI</given-names>
</name>
<name><surname>Contreras-Moreira</surname>
<given-names>B</given-names>
</name>
<name><surname>Segura-Salazar</surname>
<given-names>J</given-names>
</name>
<name><surname>Muniz-Rascado</surname>
<given-names>L</given-names>
</name>
<name><surname>Martinez-Flores</surname>
<given-names>I</given-names>
</name>
<name><surname>Salgado</surname>
<given-names>H</given-names>
</name>
<etal></etal>
<article-title>RegulonDB (version 6.0): gene regulation model of Escherichia coli K-12 beyond transcription, active (experimental) annotated promoters and Textpresso navigation</article-title>
<source>Nucleic Acids Res</source>
<year>2008</year>
<volume>36</volume>
<issue>Database issue</issue>
<fpage>D120</fpage>
<lpage>124</lpage>
<pub-id pub-id-type="pmid">18158297</pub-id>
</mixed-citation>
</ref>
<ref id="B29"><mixed-citation publication-type="journal"><name><surname>Sierro</surname>
<given-names>N</given-names>
</name>
<name><surname>Makita</surname>
<given-names>Y</given-names>
</name>
<name><surname>de Hoon</surname>
<given-names>M</given-names>
</name>
<name><surname>Nakai</surname>
<given-names>K</given-names>
</name>
<article-title>DBTBS: a database of transcriptional regulation in Bacillus subtilis containing upstream intergenic conservation information</article-title>
<source>Nucleic Acids Res</source>
<year>2008</year>
<volume>36</volume>
<issue>Database issue</issue>
<fpage>D93</fpage>
<lpage>96</lpage>
<pub-id pub-id-type="pmid">17962296</pub-id>
</mixed-citation>
</ref>
<ref id="B30"><mixed-citation publication-type="journal"><name><surname>Halfon</surname>
<given-names>MS</given-names>
</name>
<name><surname>Gallo</surname>
<given-names>SM</given-names>
</name>
<name><surname>Bergman</surname>
<given-names>CM</given-names>
</name>
<article-title>REDfly 2.0: an integrated database of cis-regulatory modules and transcription factor binding sites in Drosophila</article-title>
<source>Nucleic Acids Res</source>
<year>2008</year>
<volume>36</volume>
<issue>Database issue</issue>
<fpage>D594</fpage>
<lpage>598</lpage>
<pub-id pub-id-type="pmid">18039705</pub-id>
</mixed-citation>
</ref>
<ref id="B31"><mixed-citation publication-type="other"><name><surname>Portales-Casamar</surname>
<given-names>E</given-names>
</name>
<name><surname>Thongjuea</surname>
<given-names>S</given-names>
</name>
<name><surname>Kwon</surname>
<given-names>AT</given-names>
</name>
<name><surname>Arenillas</surname>
<given-names>D</given-names>
</name>
<name><surname>Zhao</surname>
<given-names>X</given-names>
</name>
<name><surname>Valen</surname>
<given-names>E</given-names>
</name>
<name><surname>Yusuf</surname>
<given-names>D</given-names>
</name>
<name><surname>Lenhard</surname>
<given-names>B</given-names>
</name>
<name><surname>Wasserman</surname>
<given-names>WW</given-names>
</name>
<name><surname>Sandelin</surname>
<given-names>A</given-names>
</name>
<article-title>JASPAR 2010: the greatly expanded open-access database of transcription factor binding profiles</article-title>
<source>Nucleic Acids Res</source>
<volume>38</volume>
<issue>Database</issue>
<fpage>D105</fpage>
<lpage>110</lpage>
</mixed-citation>
</ref>
<ref id="B32"><mixed-citation publication-type="journal"><name><surname>Tompa</surname>
<given-names>M</given-names>
</name>
<name><surname>Li</surname>
<given-names>N</given-names>
</name>
<name><surname>Bailey</surname>
<given-names>TL</given-names>
</name>
<name><surname>Church</surname>
<given-names>GM</given-names>
</name>
<name><surname>De Moor</surname>
<given-names>B</given-names>
</name>
<name><surname>Eskin</surname>
<given-names>E</given-names>
</name>
<name><surname>Favorov</surname>
<given-names>AV</given-names>
</name>
<name><surname>Frith</surname>
<given-names>MC</given-names>
</name>
<name><surname>Fu</surname>
<given-names>Y</given-names>
</name>
<name><surname>Kent</surname>
<given-names>WJ</given-names>
</name>
<etal></etal>
<article-title>Assessing computational tools for the discovery of transcription factor binding sites</article-title>
<source>Nat Biotechnol</source>
<year>2005</year>
<volume>23</volume>
<issue>1</issue>
<fpage>137</fpage>
<lpage>144</lpage>
<pub-id pub-id-type="doi">10.1038/nbt1053</pub-id>
<pub-id pub-id-type="pmid">15637633</pub-id>
</mixed-citation>
</ref>
<ref id="B33"><mixed-citation publication-type="journal"><name><surname>Hu</surname>
<given-names>J</given-names>
</name>
<name><surname>Li</surname>
<given-names>B</given-names>
</name>
<name><surname>Kihara</surname>
<given-names>D</given-names>
</name>
<article-title>Limitations and potentials of current motif discovery algorithms</article-title>
<source>Nucleic Acids Res</source>
<year>2005</year>
<volume>33</volume>
<issue>15</issue>
<fpage>4899</fpage>
<lpage>4913</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gki791</pub-id>
<pub-id pub-id-type="pmid">16284194</pub-id>
</mixed-citation>
</ref>
<ref id="B34"><mixed-citation publication-type="journal"><name><surname>Cliften</surname>
<given-names>P</given-names>
</name>
<name><surname>Sudarsanam</surname>
<given-names>P</given-names>
</name>
<name><surname>Desikan</surname>
<given-names>A</given-names>
</name>
<name><surname>Fulton</surname>
<given-names>L</given-names>
</name>
<name><surname>Fulton</surname>
<given-names>B</given-names>
</name>
<name><surname>Majors</surname>
<given-names>J</given-names>
</name>
<name><surname>Waterston</surname>
<given-names>R</given-names>
</name>
<name><surname>Cohen</surname>
<given-names>BA</given-names>
</name>
<name><surname>Johnston</surname>
<given-names>M</given-names>
</name>
<article-title>Finding functional features in Saccharomyces genomes by phylogenetic footprinting</article-title>
<source>Science</source>
<year>2003</year>
<volume>301</volume>
<issue>5629</issue>
<fpage>71</fpage>
<lpage>76</lpage>
<pub-id pub-id-type="doi">10.1126/science.1084337</pub-id>
<pub-id pub-id-type="pmid">12775844</pub-id>
</mixed-citation>
</ref>
<ref id="B35"><mixed-citation publication-type="journal"><name><surname>Stormo</surname>
<given-names>GD</given-names>
</name>
<name><surname>Hartzell</surname>
<given-names>GW</given-names>
<suffix>III</suffix>
</name>
<article-title>Identifying protein-binding sites from unaligned DNA fragments</article-title>
<source>Proc Natl Acad Sci USA</source>
<year>1989</year>
<volume>86</volume>
<issue>4</issue>
<fpage>1183</fpage>
<lpage>1187</lpage>
<pub-id pub-id-type="doi">10.1073/pnas.86.4.1183</pub-id>
<pub-id pub-id-type="pmid">2919167</pub-id>
</mixed-citation>
</ref>
<ref id="B36"><mixed-citation publication-type="journal"><name><surname>Cliften</surname>
<given-names>PF</given-names>
</name>
<name><surname>Hillier</surname>
<given-names>LW</given-names>
</name>
<name><surname>Fulton</surname>
<given-names>L</given-names>
</name>
<name><surname>Graves</surname>
<given-names>T</given-names>
</name>
<name><surname>Miner</surname>
<given-names>T</given-names>
</name>
<name><surname>Gish</surname>
<given-names>WR</given-names>
</name>
<name><surname>Waterston</surname>
<given-names>RH</given-names>
</name>
<name><surname>Johnston</surname>
<given-names>M</given-names>
</name>
<article-title>Surveying Saccharomyces genomes to identify functional elements by comparative DNA sequence analysis</article-title>
<source>Genome Res</source>
<year>2001</year>
<volume>11</volume>
<issue>7</issue>
<fpage>1175</fpage>
<lpage>1186</lpage>
<pub-id pub-id-type="doi">10.1101/gr.182901</pub-id>
<pub-id pub-id-type="pmid">11435399</pub-id>
</mixed-citation>
</ref>
<ref id="B37"><mixed-citation publication-type="journal"><name><surname>McCue</surname>
<given-names>L</given-names>
</name>
<name><surname>Thompson</surname>
<given-names>W</given-names>
</name>
<name><surname>Carmack</surname>
<given-names>C</given-names>
</name>
<name><surname>Ryan</surname>
<given-names>MP</given-names>
</name>
<name><surname>Liu</surname>
<given-names>JS</given-names>
</name>
<name><surname>Derbyshire</surname>
<given-names>V</given-names>
</name>
<name><surname>Lawrence</surname>
<given-names>CE</given-names>
</name>
<article-title>Phylogenetic footprinting of transcription factor binding sites in proteobacterial genomes</article-title>
<source>Nucleic Acids Res</source>
<year>2001</year>
<volume>29</volume>
<issue>3</issue>
<fpage>774</fpage>
<lpage>782</lpage>
<pub-id pub-id-type="doi">10.1093/nar/29.3.774</pub-id>
<pub-id pub-id-type="pmid">11160901</pub-id>
</mixed-citation>
</ref>
<ref id="B38"><mixed-citation publication-type="journal"><name><surname>Alkema</surname>
<given-names>WB</given-names>
</name>
<name><surname>Lenhard</surname>
<given-names>B</given-names>
</name>
<name><surname>Wasserman</surname>
<given-names>WW</given-names>
</name>
<article-title>Regulog analysis: detection of conserved regulatory networks across bacteria: application to Staphylococcus aureus</article-title>
<source>Genome Res</source>
<year>2004</year>
<volume>14</volume>
<issue>7</issue>
<fpage>1362</fpage>
<lpage>1373</lpage>
<pub-id pub-id-type="doi">10.1101/gr.2242604</pub-id>
<pub-id pub-id-type="pmid">15231752</pub-id>
</mixed-citation>
</ref>
<ref id="B39"><mixed-citation publication-type="journal"><name><surname>Wels</surname>
<given-names>M</given-names>
</name>
<name><surname>Francke</surname>
<given-names>C</given-names>
</name>
<name><surname>Kerkhoven</surname>
<given-names>R</given-names>
</name>
<name><surname>Kleerebezem</surname>
<given-names>M</given-names>
</name>
<name><surname>Siezen</surname>
<given-names>RJ</given-names>
</name>
<article-title>Predicting cis-acting elements of Lactobacillus plantarum by comparative genomics with different taxonomic subgroups</article-title>
<source>Nucleic Acids Res</source>
<year>2006</year>
<volume>34</volume>
<issue>7</issue>
<fpage>1947</fpage>
<lpage>1958</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gkl138</pub-id>
<pub-id pub-id-type="pmid">16614445</pub-id>
</mixed-citation>
</ref>
<ref id="B40"><mixed-citation publication-type="journal"><name><surname>Wang</surname>
<given-names>T</given-names>
</name>
<name><surname>Stormo</surname>
<given-names>GD</given-names>
</name>
<article-title>Identifying the conserved network of cis-regulatory sites of a eukaryotic genome</article-title>
<source>Proc Natl Acad Sci USA</source>
<year>2005</year>
<volume>102</volume>
<issue>48</issue>
<fpage>17400</fpage>
<lpage>17405</lpage>
<pub-id pub-id-type="doi">10.1073/pnas.0505147102</pub-id>
<pub-id pub-id-type="pmid">16301543</pub-id>
</mixed-citation>
</ref>
<ref id="B41"><mixed-citation publication-type="journal"><name><surname>Blanchette</surname>
<given-names>M</given-names>
</name>
<name><surname>Tompa</surname>
<given-names>M</given-names>
</name>
<article-title>Discovery of regulatory elements by a computational method for phylogenetic footprinting</article-title>
<source>Genome Res</source>
<year>2002</year>
<volume>12</volume>
<fpage>739</fpage>
<lpage>748</lpage>
<pub-id pub-id-type="doi">10.1101/gr.6902</pub-id>
<pub-id pub-id-type="pmid">11997340</pub-id>
</mixed-citation>
</ref>
<ref id="B42"><mixed-citation publication-type="journal"><name><surname>Blanchette</surname>
<given-names>M</given-names>
</name>
<name><surname>Tompa</surname>
<given-names>M</given-names>
</name>
<article-title>FootPrinter: A program designed for phylogenetic footprinting</article-title>
<source>Nucleic Acids Res</source>
<year>2003</year>
<volume>31</volume>
<issue>13</issue>
<fpage>3840</fpage>
<lpage>3842</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gkg606</pub-id>
<pub-id pub-id-type="pmid">12824433</pub-id>
</mixed-citation>
</ref>
<ref id="B43"><mixed-citation publication-type="journal"><name><surname>Pavesi</surname>
<given-names>G</given-names>
</name>
<name><surname>Zambelli</surname>
<given-names>F</given-names>
</name>
<name><surname>Pesole</surname>
<given-names>G</given-names>
</name>
<article-title>WeederH: an algorithm for finding conserved regulatory motifs and regions in homologous sequences</article-title>
<source>BMC Bioinformatics</source>
<year>2007</year>
<volume>8</volume>
<fpage>46</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-8-46</pub-id>
<pub-id pub-id-type="pmid">17286865</pub-id>
</mixed-citation>
</ref>
<ref id="B44"><mixed-citation publication-type="journal"><name><surname>Newberg</surname>
<given-names>LA</given-names>
</name>
<name><surname>Thompson</surname>
<given-names>WA</given-names>
</name>
<name><surname>Conlan</surname>
<given-names>S</given-names>
</name>
<name><surname>Smith</surname>
<given-names>TM</given-names>
</name>
<name><surname>McCue</surname>
<given-names>LA</given-names>
</name>
<name><surname>Lawrence</surname>
<given-names>CE</given-names>
</name>
<article-title>A phylogenetic Gibbs sampler that yields centroid solutions for cis-regulatory site prediction</article-title>
<source>Bioinformatics</source>
<year>2007</year>
<volume>23</volume>
<issue>14</issue>
<fpage>1718</fpage>
<lpage>1727</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btm241</pub-id>
<pub-id pub-id-type="pmid">17488758</pub-id>
</mixed-citation>
</ref>
<ref id="B45"><mixed-citation publication-type="journal"><name><surname>Siddharthan</surname>
<given-names>R</given-names>
</name>
<name><surname>Siggia</surname>
<given-names>ED</given-names>
</name>
<name><surname>van Nimwegen</surname>
<given-names>E</given-names>
</name>
<article-title>PhyloGibbs: a Gibbs sampling motif finder that incorporates phylogeny</article-title>
<source>PLoS Comput Biol</source>
<year>2005</year>
<volume>1</volume>
<issue>7</issue>
<fpage>e67</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pcbi.0010067</pub-id>
<pub-id pub-id-type="pmid">16477324</pub-id>
</mixed-citation>
</ref>
<ref id="B46"><mixed-citation publication-type="journal"><name><surname>Sinha</surname>
<given-names>S</given-names>
</name>
<name><surname>Blanchette</surname>
<given-names>M</given-names>
</name>
<name><surname>Tompa</surname>
<given-names>M</given-names>
</name>
<article-title>PhyME: a probabilistic algorithm for finding motifs in sets of orthologous sequences</article-title>
<source>BMC Bioinformatics</source>
<year>2004</year>
<volume>5</volume>
<fpage>170</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-5-170</pub-id>
<pub-id pub-id-type="pmid">15511292</pub-id>
</mixed-citation>
</ref>
<ref id="B47"><mixed-citation publication-type="journal"><name><surname>Liu</surname>
<given-names>Y</given-names>
</name>
<name><surname>Liu</surname>
<given-names>XS</given-names>
</name>
<name><surname>Wei</surname>
<given-names>L</given-names>
</name>
<name><surname>Altman</surname>
<given-names>RB</given-names>
</name>
<name><surname>Batzoglou</surname>
<given-names>S</given-names>
</name>
<article-title>Eukaryotic regulatory element conservation analysis and identification using comparative genomics</article-title>
<source>Genome Res</source>
<year>2004</year>
<volume>14</volume>
<issue>3</issue>
<fpage>451</fpage>
<lpage>458</lpage>
<pub-id pub-id-type="doi">10.1101/gr.1327604</pub-id>
<pub-id pub-id-type="pmid">14993210</pub-id>
</mixed-citation>
</ref>
<ref id="B48"><mixed-citation publication-type="journal"><name><surname>Wang</surname>
<given-names>T</given-names>
</name>
<name><surname>Stormo</surname>
<given-names>GD</given-names>
</name>
<article-title>Combining phylogenetic data with co-regulated genes to identify regulatory motifs</article-title>
<source>Bioinformatics</source>
<year>2003</year>
<volume>19</volume>
<issue>18</issue>
<fpage>2369</fpage>
<lpage>2380</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btg329</pub-id>
<pub-id pub-id-type="pmid">14668220</pub-id>
</mixed-citation>
</ref>
<ref id="B49"><mixed-citation publication-type="other"><name><surname>Gordan</surname>
<given-names>R</given-names>
</name>
<name><surname>Narlikar</surname>
<given-names>L</given-names>
</name>
<name><surname>Hartemink</surname>
<given-names>AJ</given-names>
</name>
<article-title>Finding regulatory DNA motifs using alignment-free evolutionary conservation information</article-title>
<source>Nucleic Acids Res</source>
<volume>38</volume>
<issue>6</issue>
<fpage>e90</fpage>
</mixed-citation>
</ref>
<ref id="B50"><mixed-citation publication-type="journal"><name><surname>Romer</surname>
<given-names>KA</given-names>
</name>
<name><surname>Kayombya</surname>
<given-names>GR</given-names>
</name>
<name><surname>Fraenkel</surname>
<given-names>E</given-names>
</name>
<article-title>WebMOTIFS: automated discovery, filtering and scoring of DNA sequence motifs using multiple programs and Bayesian approaches</article-title>
<source>Nucleic Acids Res</source>
<year>2007</year>
<volume>35</volume>
<issue>Web Server</issue>
<fpage>W217</fpage>
<lpage>220</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gkm376</pub-id>
<pub-id pub-id-type="pmid">17584794</pub-id>
</mixed-citation>
</ref>
<ref id="B51"><mixed-citation publication-type="journal"><name><surname>Hu</surname>
<given-names>J</given-names>
</name>
<name><surname>Yang</surname>
<given-names>YD</given-names>
</name>
<name><surname>Kihara</surname>
<given-names>D</given-names>
</name>
<article-title>EMD: an ensemble algorithm for discovering regulatory motifs in DNA sequences</article-title>
<source>BMC Bioinformatics</source>
<year>2006</year>
<volume>7</volume>
<fpage>342</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-7-342</pub-id>
<pub-id pub-id-type="pmid">16839417</pub-id>
</mixed-citation>
</ref>
<ref id="B52"><mixed-citation publication-type="journal"><name><surname>Zhang</surname>
<given-names>S</given-names>
</name>
<name><surname>Li</surname>
<given-names>S</given-names>
</name>
<name><surname>Pham</surname>
<given-names>PT</given-names>
</name>
<name><surname>Su</surname>
<given-names>Z</given-names>
</name>
<article-title>Simultaneous prediction of transcription factor binding sites in a group of prokaryotic genomes</article-title>
<source>BMC Bioinformatics</source>
<year>2010</year>
<volume>11</volume>
<fpage>397</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-11-397</pub-id>
<pub-id pub-id-type="pmid">20653963</pub-id>
</mixed-citation>
</ref>
<ref id="B53"><mixed-citation publication-type="journal"><name><surname>Sandve</surname>
<given-names>GK</given-names>
</name>
<name><surname>Abul</surname>
<given-names>O</given-names>
</name>
<name><surname>Walseng</surname>
<given-names>V</given-names>
</name>
<name><surname>Drablos</surname>
<given-names>F</given-names>
</name>
<article-title>Improved benchmarks for computational motif discovery</article-title>
<source>BMC Bioinformatics</source>
<year>2007</year>
<volume>8</volume>
<fpage>193</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-8-193</pub-id>
<pub-id pub-id-type="pmid">17559676</pub-id>
</mixed-citation>
</ref>
<ref id="B54"><mixed-citation publication-type="journal"><name><surname>Kellis</surname>
<given-names>M</given-names>
</name>
<name><surname>Patterson</surname>
<given-names>N</given-names>
</name>
<name><surname>Endrizzi</surname>
<given-names>M</given-names>
</name>
<name><surname>Birren</surname>
<given-names>B</given-names>
</name>
<name><surname>Lander</surname>
<given-names>ES</given-names>
</name>
<article-title>Sequencing and comparison of yeast species to identify genes and regulatory elements</article-title>
<source>Nature</source>
<year>2003</year>
<volume>423</volume>
<issue>6937</issue>
<fpage>241</fpage>
<lpage>254</lpage>
<pub-id pub-id-type="doi">10.1038/nature01644</pub-id>
<pub-id pub-id-type="pmid">12748633</pub-id>
</mixed-citation>
</ref>
<ref id="B55"><mixed-citation publication-type="journal"><name><surname>Mushegian</surname>
<given-names>AR</given-names>
</name>
<name><surname>Koonin</surname>
<given-names>EV</given-names>
</name>
<article-title>A minimal gene set for cellular life derived by comparison of complete bacterial genomes</article-title>
<source>ProcNatlAcadSciUSA</source>
<year>1996</year>
<volume>93</volume>
<fpage>10268</fpage>
<lpage>10273</lpage>
</mixed-citation>
</ref>
<ref id="B56"><mixed-citation publication-type="book"><name><surname>Karp</surname>
<given-names>RM</given-names>
</name>
<person-group person-group-type="editor">R. E. Miller and J. W. Thatcher</person-group>
<article-title>Reducibility Among Combinatorial Problems</article-title>
<source>Complexity of Computer Computations</source>
<year>1972</year>
<publisher-name>New York: Plenum</publisher-name>
<fpage>85</fpage>
<lpage>103</lpage>
</mixed-citation>
</ref>
</ref-list>
</back>
</pmc>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A90 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000A90 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Sante
   |area=    MersV1
   |flux=    Pmc
   |étape=   Corpus
   |type=    RBID
   |clé=     PMC:3225181
   |texte=   MotifClick: prediction of cis-regulatory binding sites via merging cliques
}}

Pour générer des pages wiki

HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i   -Sk "pubmed:21679436" \
       | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd   \
       | NlmPubMed2Wicri -a MersV1

This area was generated with Dilib version V0.6.33.
Data generation: Mon Apr 20 23:26:43 2020. Site generation: Sat Mar 27 09:06:09 2021

	Serveur d'exploration MERS
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration MERS

MotifClick: prediction of cis-regulatory binding sites via merging cliques

MotifClick: prediction of cis-regulatory binding sites via merging cliques

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

Pour générer des pages wiki