data types and tools evolve , predictive approaches developed for such work can also be directed at a number of closely connected issues . some of these include taking advantage in motif discovery of increasing numbers of genomes , including low - coverage sequences ; quantifying the contributions to motif discovery of different genomes or sets of genomes ; improving the predictive reliability of motifs by genome - scale clustering and co - occurrence ; determining a best minimal set of motif discovery methods , probably in a discovery approach that uses multiple methods ( 6 ) ; and using coexpression and other functional data types . in this report , we describe a new cisred database that contains predictions for whole - genome discovery of regulatory elements in mammals and other eukaryotes . we also describe the predictive system behind the database , which uses genome - scale approaches to predict deeply conserved ab initio motifs and identifies groups of similar motifs and co - occurring patterns of motifs . the system is designed to be readily maintained and extended in the context of rapidly evolving resources , data types and tools . the upstream section of the pipeline loads the database with significant discovered atomic motifs , and the section downstream of the database identifies groups of similar atomic motifs and co - occurring patterns of motifs . an atomic motif consists of a set of sequences , typically with a common length between 6 and 12 bp , members of which are present in a sequence region on the target species and in corresponding regions on other genomes . the system uses genome resources that are a combination of directly downloaded and processed sequences , annotations and relationships ( e.g. orthology , coexpression and interactions ) . these are stored in an automatically updated local resource that holds a wide range of public and commercial databases . motif discovery was carried out in a search region based on a single major transcript for each gene . an input target sequence set consisted of a sequence from the target species , and corresponding sequences from homologous vertebrate genes . the following rules were used to assemble target sequence sets for cisred 1.2e . we identified homologous genes by combining data from compara ( 7 ) , homologene ( 8) , inparanoid ( 9 ) and kegg ( 10 ) . for each target human gene and each of its orthologues , we took the major ensembl ( 7 ) transcript if its protein sequence was n - terminal complete . we further required that the human gene had an annotated ensembl 5-untranslated region ( 5-utr ) that was at least 10 bp long . for each target gene 's orthologue set , we required at least one of dog , mouse and rat , and at least one of chicken , frog , fugu , tetraodon and zebrafish . if the human 5-utr was < 500 bp , we applied no utr requirements to orthologues ; however , if the human 5-utr was > 500 bp , we required that all orthologues had annotated ensembl 5-utrs that were at least 10 bp long . after this filtering , for any orthologous region that was missing from an input sequence set , we added a sequence region from the current ucsc ( 11,12 ) multiple sequence alignment . for a small subset of the target genes , corresponding regions from encode - specific species were then added from the current encode multiple sequence alignment ( 13 ) . finally , regions were added from an internally processed version of the unannotated macaca mullata genome from . these rules delivered 7500 human target genes with sequence sets that contained a minimum of three and an average of six orthologous sequences from other genomes . sequence regions extended 1.5 kb upstream and 100 bp downstream of transcription start sites ( tss ) , net of all types of repeats except ltr / erv1 , ltr / ervl , ltr / malr and of coding sequences , which were masked . in addition to a target sequence set , we supplied each discovery program with a genomic background input file . the background input for each species consisted of 1000 concatenated search regions that were randomly selected from the genome 's entire set of search regions . we used multiple discovery methods in parallel , running each method with a range of parameter settings ; typically target motif width and motif occurrence model were varied . we used a compact but diverse base set of discovery methods that consisted of consensus ( 14 ) , meme ( 15 ) and motifsampler ( 16 ) . raw discovered motifs were post - processed , for example , to remove identical motifs reported by the same algorithm , and to merge strongly overlapped motifs . we assigned p - values to motifs discovered by multiple methods across large sets of target genes whose sequence sets varied in species composition , as follows . first , we identified a representative subset of target sequence sets that sampled the range of species compositions of the target sets . then , for each representative target sequence set , we created random sequence sets by retaining the original sequence from the target species and replacing each orthologous sequence with a synthetic sequence . the random synthetic sequence was generated from the target sequence by a tool we developed to simulate neutral evolution using published substitution rates and indel rates and lengths . we then submitted each target sequence set and all random sequence sets to identical motif discovery and post - processing procedures . we assigned method - independent ( mi ) scores to all motifs discovered in target and random sequence sets , using a trainable function that contained four non - negative parameters : 
 score()=(1+1d)(1+2cremote)(1+4w)(1+3(1cclose))b , 
 where coefficients took the following possible values : d , w  r , b  { 0 , 1 } and c  [ 0 , 1 ] . in the above equation , d characterized the number of site sequences in a motif ; w and b characterized the shape of a motif 's information content profile ; and c characterized motif sequence conservation . the score increased when the motif was conserved for species that are evolutionarily remote from the target , and decreased when the motif was not conserved for species that are close to the target ( primates , in the case of human ) . we used the distribution of mi scores for motifs from a target gene 's random sequences to transform the mi scores for the target gene 's motifs into p - values . finally , we loaded the database with motifs whose p - values were below a threshold ( which , for cisred 1.2e , was 0.05 ) . a library of known transcription factor binding sites , split into mutually exclusive training and testing fractions , was used to optimize the scoring function and to characterize the performance of the system . the library contained 1000 sites for 300 human genes from transfac v9.1 ( 17 ) , and 250 binding sites that we curated from the literature . we optimized the scoring function by simulated annealing , using a training fraction of known sites from randomly selected genes and two objective functions : the area under a receiver operating characteristic ( roc ) curve and the number of experimentally known motifs that were not predicted . we assessed the system 's predictive performance with a test fraction of known sites , using observables like sensitivity , specificity and positive predictive value ( ppv ) ( e.g. ) . although comparisons of method performance are constrained by many factors , current system performance compared favourably to results in a recent study ( 6 ) . to identify groups of similar motifs , we defined two pairwise motif similarity metrics . for the first metric , we used a version of the levenstein edit distance between two sequences that was modified to permit no internal gaps ( 18 ) . for each motif , m , and its reverse complement , rc(m ) , we scanned motif pairs relative to each other , and reported the overall minimum average mutual edit distance to motif k , i.e. min(d(m , k ) , d(rc(m),k ) ) . the second metric was based on the maximum information content shared between position frequency matrices derived for each motif , and also treated a motif and its reverse complement as equivalent . we hierarchically clustered pairwise dissimilarity matrices with the local density - based optics algorithm ( 19 ) . we extracted clusters from optics ' reachability output by applying an automatic cluster recognition method that identifies cluster boundaries as inflection points in the reachability plot ( 20 ) , then traversing these hierarchical segmentation results with an algorithm that traced a deepest available path , constrained by a maximum preset depth . the large size of mammalian genomes makes it challenging to organize the computational hardware and software infrastructure required to address such issues routinely . we did the large - scale discovery , similarity and co - occurrence calculations on a beowulf - style , 400 cpu ( pentium iii , xeon , opteron ) oscar cluster ( ) running red hat linux 9 ; and remotely on the beowulf 1700 cpu  glacier cluster at westgrid ( ) . we clustered motifs on a 12 dual - core cpu ( ultrasparc iv ) smp server with 96 gb of ram running solaris 9 . the database infrastructure is designed to evolve to hold results from a range of mammals , as well as results from model organisms . because promoter regions are enriched sources of regulatory elements , motif discovery and the cisred design were both based on regions around tsss . cisred human v1.2 contains motifs from promoter regions of 7500 human genes using ensembl v30 ( ncbi 35 ) data , as well as a pilot result set of 250 mouse genes . the current database design makes three types or levels of information available for regulatory elements : ( i ) atomic motifs , which are discovered independently in each target region sequence set ; ( ii ) groups of similar motifs , each of which is a putative model for the binding site of a single transcription factor ; and ( iii ) co - occurring patterns of models , which are putative regulatory modules . predicted regulatory elements can be viewed directly in cisred 's web user interface . from this interface , motifs can be viewed in the ucsc genome browser , in the ensembl genome browser via a das server , or in the sockeye comparative genomics workspace ( 21 ) . a user can filter the displayed motifs by criteria like the p - value threshold , the orthologous species present in a motif and the discovery method . the database contains a table of high - confidence globally coexpressed genes ( 22 ) ; genes coexpressed with each cisred target gene are listed on that gene 's page . the database also contains a table of single nucleotide polymorphisms ( snps ) from dbsnp ( 8) that occur in predicted motifs . when a predicted human motif contains a snp , the cisred atomic motif page highlights this variation on the target sequence of a motif site sequence set , and the highlighted base hyperlinks to the snp 's primary source information in dbsnp . a current schema diagram is available from the  databases & methods page , and direct sql queries can be run on the mysql databases at . a user can download the data , with sql files , as well as a compressed file that contains all input fasta sequence sets . because older versions of the database may not be compatible with the current user interface , only recent versions for each species can be accessed through the web or via a mysql client . however , historical releases of cisred databases are archived and can be downloaded . certain parts of the system 's software are available from a tab on the cisred home page . sockeye ( 21 ) permits , for example , a user to assess details of conserved regions relative to genomic annotations in multiple sequence alignments . the hitplotter visualizer displays large sets of discovered motifs from multiple - method discovery runs , and is available on request as a beta release . database contents will be extended to include large - scale results for human , mouse , rat , caenorhabditis elegans and drosophila melanogaster . the input sequence sets for this database were based on human tsss that were identified by considering ensembl ( 7 ) and refseq ( 23 ) annotations . to address the limitations of gene and transcript annotations for non - human species , corresponding vertebrate search regions were taken from ucsc ( 11,12 ) and encode multiple sequence alignments ( 13 ) . we are extending our ability to take advantage of unannotated and low - coverage genome sequence data . we are continuing to improve motif post - processing and scoring . optimizing the scoring function depends on having a large library of known motif sites ; we anticipate that a newly created web database for submitting and curating binding sites from the literature may help us to enlarge and improve this resource (; s. b. montgomery and o. l. griffith , manuscript in preparation ) . given a scalable clustering method , we continue to assess motif similarity metrics and how best to use the hierarchical information output from optics . given groups of similar motifs , we are applying group labels to atomic motifs , then identifying overrepresented co - occurring motif patterns using hypergeometric statistics , imposing separation constraints on neighbouring motifs , and searching in two stages for patterns larger than pairs ( 24,25 ) . we are implementing methods for annotating discovered motifs as known or novel against known site resources . given annotated motifs , we will annotate overrepresented co - occurring patterns of human motif pairs as known versus novel using the transcompel resource ( 26 ) . we are applying genome - scale motif clustering and co - occurrence as filters for predicted motifs that may improve the predictive reliability and the resulting catalogue of conserved regulatory elements . we have assembled a large multi - species coexpression resource that contains public microarray and sage data from diverse sources ( 22 ) ( table 1 ) . we have shown that combining global coexpression data from multiple platforms improves confidence in coexpression predictions when assessed against the gene ontology ( go ) ( 27 ) . from this , we established go - based pearson correlation thresholds that identified high - confidence globally coexpressed gene pairs . the coexpression database makes results available from this global analysis and from two other recent analyses ( 28,29 ) . although coexpressed genes can have similar regulatory elements , the system 's predictive performance improved only marginally when inputs included coexpressed genes in addition to orthologous genes ( data not shown ) . given these results , currently we are assessing an approach that includes no coexpressed genes in motif discovery inputs , but uses coexpression information to assess groups and co - occurring patterns identified in genome - scale sets of atomic motifs . we will extend the database user interface to offer more complex user filtering , as well as motif searches based on consensus strings or matrices . for work with classes of regulatory elements that are defined by wet lab data types based on , for example , chip or dnase i hypersensitivity ( e.g. see encode tracks within the ucsc genome browser ) ( 11,13 ) , we have designed a new schema that is based on search regions rather than on genes , and will extend the user interface to support this . we will continue to assess the contributions to regulatory element predictions of different genomes and sets of genomes . we will integrate and assess new motif discovery methods , and will identify a best minimal set of methods on an ongoing basis . data processing system for high - throughput motif discovery , clustering , co - occurrence , annotation and performance assessment . database contents and high - level links , from a web user perspective , as of cisred human v1.2 . groups are clusters of similar motifs that are identified by large - scale optics ( 19 ) clustering .
we describe cisred , a database for conserved regulatory elements that are identified and ranked by a genome - scale computational system ( ) . 
 the database and high - throughput predictive pipeline are designed to address diverse target genomes in the context of rapidly evolving data resources and tools . 
 motifs are predicted in promoter regions using multiple discovery methods applied to sequence sets that include corresponding sequence regions from vertebrates . 
 we estimate motif significance by applying discovery and post - processing methods to randomized sequence sets that are adaptively derived from target sequence sets , retain motifs with p - values below a threshold and identify groups of similar motifs and co - occurring motif patterns . 
 the database offers information on atomic motifs , motif groups and patterns . 
 it is web - accessible , and can be queried directly , downloaded or installed locally .