BACKGROUND
most mammals detect odorant chemicals using two sensory systems.
the main olfactory epithelium of the nose consists of olfactory sensory neurons that express odorant receptor  proteins  <cit> .
or proteins bind inspired odorants and generate action potentials that signal odorant information to the olfactory bulb  <cit> .
most mammals also possess a second chemosensory organ, the vomeronasal organ , whose chemosensory functions have been closely associated with reproductive processes  <cit> .
the sensory neurons of the vno express two types of receptors, v1r and v2r   <cit> .
these sensory neurons project to the "accessory olfactory bulb" located posterior to the main olfactory bulb  <cit> .
the or, v1r, and v2r proteins are members of the g-coupled-receptor  superfamily.
the mouse genome encodes ~ <dig> or genes  <cit> , ~ <dig> v1r genes  <cit> , and ~ <dig> v2r genes  <cit> .
the or and v1r genes have a compact gene structure comprising a single coding exon  and 1– <dig> short exons in their untranslated regions .
putative transcription start sites have been typically mapped to positions <  <dig> kb upstream of coding exons  <cit> .
these compact genes are predominantly organized in clusters at >  <dig> chromosomal loci in mouse  <cit> .
these clusters are rarely, if ever, interrupted by non-or/non-v1r genes.
each sensory neuron in the mouse olfactory epithelium and vno expresses only one allele of one gene from the large repertoire of ors and v1rs in the genome  <cit> .
mutually exclusive receptor expression permits the functional specialization of individual sensory neurons in both systems; i.e., individual sensory neurons in both the main nose/vno are specialized for the odorant-binding functions of the receptor allele expressed in that cell.
despite the fact that or and v1r proteins do not share sequence homology, transduce signals via different g proteins and are expressed in non-overlapping cell types  <cit> , this shared feature of mutually exclusive expression has fueled speculation that these systems may utilize a similar regulatory strategy.
mutually exclusive expression is accomplished in other systems by several diverse mechanisms.
typically, differential gene expression is governed by cis enhancers that bind transcription factor combinations, which in a deterministic way, dictate whether a gene is expressed or not at a given developmental time or place.
applying this model to mutually exclusive or transcription, such a mechanism predicts that each or promoter has a unique cis regulatory code, and that each sensory neuron would express a specific combination of transcription factors sufficient to activate only one or promoter.
the fact that duplicate or transgenes, with identical cis regulatory sequences, are not co-expressed in the same cells indicates that mutual exclusive or transcription is not regulated by a strict deterministic model  <cit> .
a second category of mechanisms includes non-deterministic or stochastic processes; e.g., competition for a single-copy regulatory complex in the nucleus.
one biological precedent for a stochastic competitive mechanism is the mutually exclusive expression of trypanosome variable surface glycoprotein genes by a single-copy "pol body" regulatory complex  <cit> .
this model proposes that a unique assembly of transcription factors in the nucleus is able to stably associate with only one gene at a time.
the recent observation that active or genes  interact with a unique locus in the nucleus  <cit> , termed the "h region", that was previously characterized as having strong enhancement activity  <cit> , is consistent with this model.
additional study of the "h region" will be required in order to elucidate its precise role in the establishment of mutually exclusive or transcription.
stochastic competition models predict that the competing genes share common cis regulatory sequences, which interact with common transcription factors that are part of the regulatory complex.
a recent study of the regulatory region of one mouse or gene revealed that a small transgene containing merely ~ <dig> bp upstream genome sequence is sufficient to drive mutual exclusive expression of this transgene  <cit> .
this, and other similar mini-transgene studies suggest that in general, putative "universal" cis regulatory elements are likely to reside close to transcription start sites.
while no v1r mini-transgene experiments have yet been reported, previous comparative genomic analysis of one v1r gene cluster suggests the presence of well-conserved promoter regions that similarly lie within  <dig> kb from transcription start sites  <cit> .
in this study, we developed a bioinformatic strategy to search for common putative regulatory motifs that might function in co-regulating v1r genes.
we based our bioinformatic strategy on two assumptions.
first, the v1r phylogenetic structure must be accommodated so that results are not biased by larger and more recently diverged subfamilies.
second, since transcription factor binding sites are typically degenerate, an information-based  search methodology will be most successful at finding universally shared regulatory motifs.
many traditional motif-searching methods, such as meme  <cit> , are not designed to accommodate phylogenetic structure, and therefore in this context, tend to report motifs that arise from conservation within subfamilies we already knew about.
one recently developed methodology designed to accommodate phylogenetic structure, phylogenetic footprinting  <cit> , depends on a reliable input tree on which to evaluate whether a resulting motif is unexpected with respect to the known phylogenetic relationships established in the tree.
the best use of this program, however, is in situations where the phylogeny is well established .
the v1r gene tree, in contrast, is poorly resolved due to the high divergence between subfamilies and frequent gene conversion events between paralogs  <cit> .
as described below, our strategy included the development of a new motif-searching approach that, like phylogenetic footprinting, overcomes biases due to phylogenetic structure , but unlike phylogenetic footprinting, is catered to the context of our problem in that it does not depend on input alignments/trees and utilizes information-based  methods.
our strategy to identify putative regulatory motifs involved in v1r co-regulation consisted of four steps:
1) we used comparative sequence analysis and 5' race to identify putative v1r promoter regions  that are well conserved within  subfamilies;
2) we aligned promoter sequences within subfamilies and represented the homology of each subfamily with a single sequence logo  <cit> , thereby permitting a second order processing of these logos in which each subfamily is represented equally;
3) we developed a new algorithm, logoalign, which seeks an alignment of the above input logos that maximizes total information within small, motif-sized  windows, and therefore designed to report motifs well represented across subfamilies;
4) we analyzed resulting motifs on several statistical grounds, including their total information as compared to controls, and their positioning near transcription start sites as compared to random positions in gene blocks.
RESULTS
a divergent set of v1r subfamilies have arisen by local gene duplication
the mouse v1r gene repertoire consists of ~ <dig> intact coding regions that partition into  <dig> major subfamilies   <cit> .
most of these v1rs  reside within large clusters at nine chromosomal locations  <cit>  .
three of these v1r clusters consist of more than one subfamily: the a and b subfamilies are co-clustered on mouse chromosome  <dig>  the j and k subfamilies are co-clustered on chromosome  <dig>  and the h and i subfamilies are co-clustered on chromosome  <dig>  three v1r subfamilies are found at more than one locus: the c subfamily is found at two locations on mouse chromosome  <dig>  the d subfamily is found at two locations on mouse chromosome  <dig>  and the e subfamily is clustered on both chromosome  <dig> and  <dig>
v1r subfamilies have expanded by local gene block duplication  <cit> .
most of these local duplications occurred recently enough that the extent of the duplicated block is evident by sequence homology .
typically, duplicated blocks are about  <dig> kb in size; most of the duplicated sequence is upstream of the coding regions.
we previously mapped the sequences of four transcriptional units from the a and b subfamilies onto their genomic blocks  <cit> .
each of these v1rs had a gene structure consisting of a ~1-kb coding exon located <  <dig> kb from the 3' end of the duplicated block, and one or two short untranslated exons located upstream of the coding region.
the putative transcription start sites  typically map <  <dig> kb from the 5' end of the duplicated blocks.
thus, the v1r gene block duplications seem to have efficiently captured putative promoter regions, utrs, and coding regions, with little surrounding sequence.
this observation hints that the sequence information sufficient to regulate individual v1r genes may be very proximal to transcription start sites.
each subfamily has conserved putative promoter regions
we previously identified putative promoter homology at the mouse chromosome- <dig> locus containing a cluster of v1rs from the a and b subfamilies  <cit> .
in this case, the putative promoter homology is shared between a and b genes.
this observation raises a question as to whether this homology is universal , or, whether each locus might have its own promoter homology.
in fact, neither seems to be the case.
first, no sequence similarity is evident between a/b promoters and the gene blocks of any other subfamily.
second, not all co-clustered subfamilies exhibit shared promoter homology, as was the case for the co-clustered a and b genes: the co-clustered j and k subfamilies do exhibit cross-subfamily non-coding homology, however, neither the co-clustered h and i subfamilies or the co-clustered e and f subfamilies exhibit cross-subfamily non-coding homology.
in general, we instead find that upstream non-coding homology is evident only within subfamilies, irrespective of genomic location.
thus, subfamilies distributed to multiple loci  do exhibit non-coding homology among members at both loci .
therefore, broad putative promoter homology is not universally shared, nor locus-specific, rather, it appears to be shared predominantly within subfamilies.
for subsequent analyses, we refer to "promoter subfamilies" to indicate the ten sets of genes that share upstream, non-coding homology .
as a first step in identifying putative regulatory motifs shared among v1r subfamilies, we decided to restrict our search to just the putative promoter regions .
as noted previously for the ab promoter subfamily  <cit> , putative promoters in this case were evident as upstream subregions of gene blocks that exhibited increased homology.
like the ab promoter subfamily, upstream islands of non-coding, putative promoter homology are evident in other promoter subfamilies; a striking example is shown in the pipmaker  <cit>  plot of the v1rf <dig> gene in figure 1a, in which a ~500-bp island of non-coding homology is evident ~ <dig> kb upstream of the coding region.
however, for most promoter subfamilies, the gene blocks have duplicated too recently to be able to detect block subsequences that are under more stringent selection.
for example, the pipmaker plot of the v1rc <dig> gene in figure 1a, shows homology among c promoter subfamily members that spans the entire ~ <dig> kb block .
in order to evaluate these less obvious cases, we made a second assumption about putative v1r regulatory sequences: in addition to exhibiting higher sequence identity, these regions are likely to be homologous among all promoter subfamily members.
pipmaker plots, like those shown in figure 1a, contain both types of information, since the vertical axis in a plot represents percent pairwise sequence identity, and the number of plots crossing any position in the block represents the number of subfamily members with homology at that position.
we transformed these two dimensions of "conservation" into a single "conservation score" at each position of each gene block.
the conservation score is the average percent identity at each position based on all the pipmaker plots that cross that position ; however, for each "missing gene"  we include a 0% identity in this average calculation.
in this way, the conservation score is severely penalized in regions where not all subfamily members exhibit homology.
using this approach, we identify two subregions of v1r blocks that are most well conserved within promoter subfamilies .
a prominent homology peak is generally observed across the coding regions and immediately upstream of the coding region.
the non-coding portion immediately upstream of the coding region presumably includes the coding exon acceptor site, as well as translation regulatory signals.
a second prominent homology peak is generally observed near the 5' end of the block, well upstream of the coding region and upstream of intervening low-homology non-coding sequence.
these upstream peaks  could represent promoter regions and selection of sequences containing transcriptional information.
the putative transcription start sites identified previously by 5' race pcr for four genes from the ab promoter subfamily map within the upstream peaks in their respective gene blocks .
these four start sites are located near the middle of their respective ~kilobase-size promoter homology, but do not map exactly to homologous positions.
similarly, two previously characterized cdnas of the d subfamily  <cit>  initiate transcription from near the middle of their respective peaks, but not from precisely the same relative positions.
therefore, if we assume that these cdnas accurately reveal transcription start sites  and are representative cases for v1rs in general, it would appear that v1r promoters exhibit variable relative initiation positions within these much larger regions of promoter homology.
we were next interested to know whether putative transcription start sites for other promoter subfamilies likewise mapped to their respective upstream peak regions.
using mouse vno-derived cdna, we generated 5' race pcr products using gene-specific primers on at least one member of each v1r subfamily .
as was the case for the ab and d promoter subfamilies, transcription start sites in all cases map to upstream peaks in their respective gene blocks .
we identified multiple race products for three v1rs.
in these cases, the putative tss maps to within  <dig> bp,  <dig> bp, and  <dig> bp, respectively, with identical exon-intron gene structures.
this slight variation in the length of race products might be due to degradation of rna templates or alternative start sites within promoters.
nevertheless, with this limited sample, we find no evidence for alternative splicing or alternative promoters.
therefore, our comparative sequence analysis of  <dig> v1r genes, as well as 5' race results for  <dig> of these v1rs, points to a single, well-conserved promoter region upstream of each gene.
further analysis of these putative promoter regions is likely to reveal promising candidate sequence elements that contribute to v1r transcriptional regulation.
we next analyzed sequence conservation within these putative promoter regions by examining nucleotide substitution rates within these regions as compared to coding and other non-coding regions.
we confined our search to pairs of genes within subfamilies that exhibit non-coding block substitution rates between 15–25% so that all gene pairs considered would have approximately the same elapsed time since common ancestry.
this substitution level range also permits comparisons between mouse-rat orthologous pairs, since mouse-rat orthologs are expected to exhibit 15–25% neutral substitution since the mouse-rat split  <cit> .
we find that coding sequences exhibit average substitution levels that are ~63% that of surrounding non-coding block sequences  .
we find that promoter regions  tend to fall into two discrete classes.
most promoter sequences exhibit substitution levels that are ~80–90% that of the surrounding non-coding block sequences .
however, a subset of promoters  exhibit much lower substitution levels that are comparable to levels observed in their coding regions.
interestingly, the pairs of a and g paralogous promoters that exhibit these lower substitution rates, do not exhibit lower substitution rates in orthologous comparisons .
this observation raises the possibility that gene conversions, which can only occur between paralogs and not orthologs, have contributed to homogenization of a and g promoters in mouse.
gene conversions might be favored in order to maintain sets of broad promoter sequences that would then compete approximately equally well for universal transcription factors.
it is also noteworthy that each of the promoter regions  exceeds  <dig> bp in size with few obvious breaks in homology.
such large and unbroken regions of homology seem unlikely to be the consequence of strict conservation of transcription factor binding sites, yet seem to be feasible target sizes for gene conversion events.
identification of cross-subfamily motifs using information-based techniques
to this point, we have identified upstream, non-coding sequences that exhibit elevated conservation scores and transcription start sites.
these putative promoter regions are hereafter referred to as "peaks" , whereas the remaining non-coding regions of a gene block are referred to as "blocks".
we next searched for "motifs" shared among peaks of the ten promoter subfamilies.
"motifs" are defined in terms of nucleotide frequencies and a motif's quality is measured in terms of information content.
the most common way to depict a motif is by a sequence logo  <cit> , in which the base frequencies at each position in the motif are summarized graphically by the height of each letter.
the units of a logo plot are bits of information.
a motif is more information-rich  when the base frequencies across the motif deviate more from expectation .
in this regard, a particular position in a set of aligned sequences need not be absolutely conserved to be information-rich.
indeed, according to information theory, a position in an aligned group of sequences that always is one of two bases can contain more information than a position that exhibits a clear majority of sequences with a single base, if in fact, the remaining sequences do not exhibit bias  <cit> .
thus, information profiling is a more refined method than percent identity for assessing the likelihood of a given base position containing part of a functional code.
this is especially likely to be the case for transcription factor binding sites, since these sites are often degenerate and not absolutely conserved.
some established motif-searching methods, such as meme  <cit> , are not suitable for this particular problem because they have no knowledge of the hierarchy of the dataset.
specifically, this dataset has two hierarchical levels due to very recent relationships between genes within subfamilies, yet very distant relationships between subfamilies.
thus, without knowledge of this hierarchy, algorithms like meme report within-subfamily sequence identities we already knew about, as opposed to less conserved cross-subfamily homology of interest.
another motif-searching strategy, phylogenetic footprinting  <cit>  solves this problem by utilizing an input tree that specifies the hierarchy of the dataset.
however, this method is inappropriate in the context where input sequences are not homologous, too distantly related to produce a reliable phylogenetic tree, or where the phylogeny is uncertain due to concerted evolution.
since it is not possible to produce a well resolved input v1r tree, and because we wished to design our algorithm for the analysis of unrelated input sequences  and also to use information-based  searching, we developed a solution catered to our particular problem.
our solution is to abstract away from individual sequences by first generating a representative sequence logo for each promoter subfamily, each logo  being derived from an alignment of the individual peak sequences of a single promoter subfamily.
this logo reflects all of the information contained within the individual peaks, yet permits a second order analysis to identify motifs shared between these representative logos, thus, across promoter subfamilies, without any one promoter subfamily being weighted more heavily .
the set of ten logos resulting from an alignment of the peak sequences for each of the ten promoter subfamilies, is provided in additional file  <dig>
in order to next find motifs shared among these ten logos , we designed an algorithm, logoalign, that performs a heuristic search for logo similarity within short, motif-sized windows .
briefly, this algorithm begins by randomly selecting a motif-sized window  in each of the ten input logos, combines the windows into a new motif-sized logo, and then calculates the total information contained in this new motif-sized logo.
the algorithm then selects one of the ten input logos, and searches all 12-bp windows in that logo and identifies the 12-bp window in that logo that produces a new motif-sized logo with the maximum of total information when aligned with the other nine stationary windows.
logoalign cycles through each of the other nine logos  in a similar manner, each time identifying the 12-bp window in the logo being processed that maximizes total information in the alignment.
the algorithm continues until window positions do not move for one complete cycle.
the result of one complete trial is therefore a "local maximum" of information  for an aligned set of 12-bp windows; this local maximum is referred to as a "motif" .
multiple trials, each with a set of random starting positions and cycling order, identified a distribution of information-rich motifs .
as described in the introduction, logoalign was developed specifically for this particular application because it does not depend on being able to align all taxa  while still being able to consider phylogenetic heirarchy in the dataset.
we note that two other motif-searching algorithms have been recently developed in consideration of these same issues.
the algorithm phylocon  <cit> , like logoalign, performs an information-based motif search on sequence logos created from multiple alignments.
however, phylocon uses an algorithm that we believe is suboptimal in our context for two reasons.
first, phylocon makes use of local, un-gapped, sub-optimal, multiple alignments, rather than gapped, global, multiple alignments.
using local alignments can be preferable if the sequences being aligned are not closely enough related to produce high-quality global alignments.
however, the subfamilies in our dataset have broad contiguous regions of exceptionally high homology, with which we can produce high-quality global multiple alignments.
global alignments can provide an additional layer of information, since the existence of gaps can indicate that an otherwise well-conserved region is not likely to bind a universally-utilized transcription factor  if the motif is interrupted in a subset of sequences.
second, phylocon searches the solution space using a deterministic greedy algorithm than will always progress to the same local maximum, but may never find the best global solution.
since logoalign does not progress deterministically, it has an increased probability of identifying the best global solution with multiple iterations.
a second, even newer program, phylogibbs  <cit>  is also similar to logoalign and phylocon in terms of its suitability for hierarchical datasets with incomplete phylogenies.
this program uses a "simulated annealing" algorithm  <cit> , and unlike phylocon, is non-deterministic and can utilize global  alignments.
thus, while phylogibbs differs from logoalign in specifics of its design, it generally approaches the motif-searching problem in a very similar way and may therefore be equally well-suited for our context.
we are currently testing the relative sensitivities and computational efficiencies of several motif-searching strategies in various contexts as part of a broader assessment of logoalign .
statistical validation of candidate motifs
we assessed resulting motifs based on three criteria.
first, we expect that multiple iterations of logoalign using randomly determined starting points should converge on a common set of information-rich motifs, as opposed to finding a different answer each iteration.
second, we expect that biologically meaningful motifs should contain more information than motifs identified in searches on random control sequences.
third, we expect that transcriptionally relevant motifs should more likely be positioned near transcription start sites than elsewhere in gene blocks, and/or exhibit common positioning relative to each other from gene to gene.
motif convergence
we conducted  <dig> trials of logoalign, each iteration with a different starting point  and path .
the resulting  <dig> motifs could immediately be collapsed into  <dig> non-identical motifs ; for example, the best motif was found  <dig> times.
we next partitioned the  <dig> non-identical motifs into  <dig> clusters of similar motifs, allowing us to ignore weaker versions of essentially identical higher-scoring motifs.
therefore, from  <dig> iterations, we observed > 97% convergence to merely  <dig> non-redundant solutions, suggesting that we might have sufficiently sampled the sequence space to find a global maximum.
significant information content
we conducted three control experiments to assess the significance of the total information of v1r promoter motifs identified by logoalign .
the first control establishes the noise level for randomly aligned sequences; the maximum total information in this case is ~ <dig> bits, whereas the minimum information context in the  <dig> iterations of logoalign has more than double this information content.
not surprisingly then, logoalign always progresses towards a more information-rich solution.
the second control establishes the relative contribution of individual subfamilies.
in this control, we establish that a biased distribution in which the most information-rich window from one logo is aligned with randomly selected windows from the other nine logos produces motifs only slightly above noise and significantly less than the information content in the experimental results.
the most important control is to ask how logoalign performs on random sequences.
to conduct this control, we shuffled v1r sequences not only in such a way to preserve base composition, but also to preserve the number, size, and diversity of subfamilies .
thus, our control was a set of sequences with exactly the same properties as the experimental set, only with putative motifs scrambled.
we find that the distribution of information in the control set versus the experimental set is bimodal , indicating that motifs identified in v1r promoters are more information-rich than those identified in random sequences.
note that while the majority of motifs identified in v1r promoters contain more information than the maximum information-rich motifs identified in the control, we presume based on the overlap of these distributions that the least information-rich v1r promoter motifs identified in this study are probably not biologically significant .
however, the best motifs  contain significantly more information than those found in the control , and ~81% of identified v1r promoter motifs contain information that is >  <dig> standard deviations above the mean for the control  .
non-random positioning
we next analyzed motif occurrences within v1r gene blocks using sequence walking techniques  <cit> .
the rationale for this test is that some sequence motifs , even if information-rich among v1rs, might occur frequently in background sequence .
therefore, some statistical measure is appropriate to ascertain that identified motifs are enriched specifically within v1r promoters, as opposed to random widespread occurrence elsewhere in the gene blocks.
for this analysis, we focused on the five best motifs .
generally, we find that these motifs tend to be located in better conserved parts of peaks, and the motifs found within peaks tend to be better conserved than motifs found elsewhere in gene blocks , suggesting that occurrence in promoter regions, but not in non-peak portions of blocks, are under the most stringent selective pressure.
we find that these motifs occur within  <dig> bp of putative transcription start sites with significantly greater frequency than within random  <dig> bp windows of their gene blocks .
note that this latter analysis assumes that putative transcription start sites in conserved v1r promoter subfamilies are located at homologous positions to empirically-determined start sites determined by race .
as discussed previously, while this is probably not precisely the case, the 500-bp window used in this analysis seems sufficiently large to accommodate the expected variability in relative start positions.
if all v1r transcription start sites were more precisely known, we expect we would observe an even greater relative enrichment of motif occurrences near tsss, since this knowledge would presumably permit the use of a smaller window size in the analysis.
we next focussed on only those  <dig> v1r genes in which transcription start sites were empirically determined by race in order to investigate more subtle patterning of our five most information-rich motifs identified in the study.
the most compelling observation is that the highest-scoring occurrence of motif  <dig> overlaps the 5' exon-intron junction for  <dig> of  <dig> v1rs where gene structures were determined by race, suggesting that this motif contains splice donor information for these upstream exons.
in one case  of the  <dig> race products analyzed, motif  <dig> is located precisely at the empirical transcription start site; however, for the other v1rs, the best version of this motif is found as far as  <dig> bp upstream and  <dig> bp downstream of empirical transcription start sites , and therefore it seems unlikely that this motif generally contains transcription initiation information.
if motif  <dig>  is excluded, the best occurrence of the other four motifs is found just upstream of empirically-determined transcription start sites in 33/ <dig> cases , within the 5' exons in 7/ <dig> cases , and within the upstream intron  in 8/ <dig> cases ; therefore, it seems likely that these motifs generally contain transcriptional information, as opposed to, for example, exon or splicing information.
we also explored the possibility that pairs of motifs might require critical spacing with respect to each other.
we do find examples of motif pairs that exhibit surprisingly similar spacing across the promoters of multiple subfamilies.
for example, the spacing between motif  <dig> and motif  <dig> is consistent within  <dig> bp for  <dig> different v1rs across five subfamilies.
however, we do not observe conserved relative spacing that encompasses all, or even nearly all v1rs, suggesting that stringent spacing among motifs tested is not required, as might be predicted for binding sites of transcription factors cooperating/interacting in a regulatory complex.
finally, we compared our five most information-rich motifs to a library of known transcription factor binding sites   <cit> .
the best occurrences of motifs  <dig> and  <dig> within v1r promoters frequently contain an "aagtt" that matches the core binding site for the myt <dig> zinc finger transcription factor; however, only ~a third of these motifs are recognized by the genomatix algorithm  <cit>  as a sufficient match to the myt <dig> site.
in general, while we find that our motifs bare resemblance to a number of transcription factor binding sites represented in the database, we do not identify a compelling example in which the conserved core of a binding site is also a conserved core within any of our five best motifs.
nevertheless, since few transcription factors have been investigated by chip-on-chip experiments to fully explore the range of actual binding sites in the genome, and indeed, in cases where transcription factor binding in the genome has been characterized in this comprehensive way, it appears bound sites can deviate significantly from consensus sequences  <cit> , we only very tentatively suggest that our five motifs do not resemble known transcription factor targets.
CONCLUSIONS
in summary, we have used a combination of existing and new bioinformatic tools to discover that every v1r subfamily has a broad and well conserved promoter region that contains empirical transcription start sites.
we speculate that the high level of conservation over such a large sequence territory might have resulted from gene conversions that would tend to broadly homogenize these sequences.
homogenization in turn, could permit all v1rs of a particular subfamily to compete equally well for common transcription factors or complexes.
we have developed a new information-based motif-searching strategy that permits sequence comparisons between different subfamilies , but is not dependent on the alignment of sequences across subfamilies, in order to identify candidate transcription factor binding motifs that are represented in all v1r promoters and present across all v1r subfamilies.
the best motifs contain >  <dig> bits of cumulative information, which is significantly more information than those identified in random sequences.
three of these motifs have relatively high gc content , and the best motif is identified near transcription start sites in 94% of all v1r promoter regions .
these observations suggest that these motifs are excellent candidate binding sites for v1r co-regulatory factors, a hypothesis we are now testing experimentally.
our algorithm, logoalign, has potential for use in a broader context of gene co-regulation.
two widely used approaches, exemplified by meme and phylogenetic footprinting, are appropriate in distinct contexts.
meme  is best used when analyzing sequences of comparable distances , but is not suitable when there is varying degrees of homology within the sequence set, because it does not correct for phylogenetic relatedness.
phylogenetic footprinting is best used when analyzing sequences with varying degrees of homology , but is not suitable when some of the sequences are unrelated, because it depends on an input tree that establishes phylogenetic relationships for all input sequences.
our algorithm, logoalign, as well others such as phylocon and phylogibbs, applies to a niche where there exists both varying degrees of homology and sets of unrelated sequences for which no phylogeny can be established.
an example of this particular context would be in the evaluation of regulons elucidated by microarray studies, where both related and unrelated target genes may be part of a downstream battery of genes under the control of a particular transcription factor.
we are currently conducting a broader comparative evaluation of the logoalign, phylocon, phylogibbs, and other related motif-searching strategies using synthetic controls in order to more rigorously assess relative sensitivities and context-dependent efficiencies of these various algorithmic approaches.

 most mammals detect odorant chemicals using two sensory systems. the main olfactory epithelium of the nose consists of olfactory sensory neurons that express odorant receptor proteins. or proteins bind inspired odorants and generate action potentials that signal odorant information to the olfactory bulb. most mammals also possess a second chemosensory organ, the vomeronasal organ, whose chemosensory functions have been closely associated with reproductive processes. the sensory neurons of the vno express two types of receptors, v1r and v2r. these sensory neurons project to the "accessory olfactory bulb" located posterior to the main olfactory bulb. the or, v1r, and v2r proteins are members of the g-coupled-receptor superfamily. the mouse genome encodes ~ or genes, ~ v1r genes, and ~ v2r genes. the or and v1r genes have a compact gene structure comprising a single coding exon and 1– short exons in their untranslated regions. putative transcription start sites have been typically mapped to positions < kb upstream of coding exons. these compact genes are predominantly organized in clusters at > chromosomal loci in mouse. these clusters are rarely, if ever, interrupted by non-or/non-v1r genes. each sensory neuron in the mouse olfactory epithelium and vno expresses only one allele of one gene from the large repertoire of ors and v1rs in the genome. mutually exclusive receptor expression permits the functional specialization of individual sensory neurons in both systems; i.e., individual sensory neurons in both the main nose/vno are specialized for the odorant-binding functions of the receptor allele expressed in that cell. despite the fact that or and v1r proteins do not share sequence homology, transduce signals via different g proteins and are expressed in non-overlapping cell types, this shared feature of mutually exclusive expression has fueled speculation that these systems may utilize a similar regulatory strategy. mutually exclusive expression is accomplished in other systems by several diverse mechanisms. typically, differential gene expression is governed by cis enhancers that bind transcription factor combinations, which in a deterministic way, dictate whether a gene is expressed or not at a given developmental time or place. applying this model to mutually exclusive or transcription, such a mechanism predicts that each or promoter has a unique cis regulatory code, and that each sensory neuron would express a specific combination of transcription factors sufficient to activate only one or promoter. the fact that duplicate or transgenes, with identical cis regulatory sequences, are not co-expressed in the same cells indicates that mutual exclusive or transcription is not regulated by a strict deterministic model. a second category of mechanisms includes non-deterministic or stochastic processes; e.g., competition for a single-copy regulatory complex in the nucleus. one biological precedent for a stochastic competitive mechanism is the mutually exclusive expression of trypanosome variable surface glycoprotein genes by a single-copy "pol body" regulatory complex. this model proposes that a unique assembly of transcription factors in the nucleus is able to stably associate with only one gene at a time. the recent observation that active or genes interact with a unique locus in the nucleus, termed the "h region", that was previously characterized as having strong enhancement activity, is consistent with this model. additional study of the "h region" will be required in order to elucidate its precise role in the establishment of mutually exclusive or transcription. stochastic competition models predict that the competing genes share common cis regulatory sequences, which interact with common transcription factors that are part of the regulatory complex. a recent study of the regulatory region of one mouse or gene revealed that a small transgene containing merely ~ bp upstream genome sequence is sufficient to drive mutual exclusive expression of this transgene. this, and other similar mini-transgene studies suggest that in general, putative "universal" cis regulatory elements are likely to reside close to transcription start sites. while no v1r mini-transgene experiments have yet been reported, previous comparative genomic analysis of one v1r gene cluster suggests the presence of well-conserved promoter regions that similarly lie within kb from transcription start sites. in this study, we developed a bioinformatic strategy to search for common putative regulatory motifs that might function in co-regulating v1r genes. we based our bioinformatic strategy on two assumptions. first, the v1r phylogenetic structure must be accommodated so that results are not biased by larger and more recently diverged subfamilies. second, since transcription factor binding sites are typically degenerate, an information-based search methodology will be most successful at finding universally shared regulatory motifs. many traditional motif-searching methods, such as meme, are not designed to accommodate phylogenetic structure, and therefore in this context, tend to report motifs that arise from conservation within subfamilies we already knew about. one recently developed methodology designed to accommodate phylogenetic structure, phylogenetic footprinting, depends on a reliable input tree on which to evaluate whether a resulting motif is unexpected with respect to the known phylogenetic relationships established in the tree. the best use of this program, however, is in situations where the phylogeny is well established. the v1r gene tree, in contrast, is poorly resolved due to the high divergence between subfamilies and frequent gene conversion events between paralogs. as described below, our strategy included the development of a new motif-searching approach that, like phylogenetic footprinting, overcomes biases due to phylogenetic structure, but unlike phylogenetic footprinting, is catered to the context of our problem in that it does not depend on input alignments/trees and utilizes information-based methods. our strategy to identify putative regulatory motifs involved in v1r co-regulation consisted of four steps: 1) we used comparative sequence analysis and 5' race to identify putative v1r promoter regions that are well conserved within subfamilies; 2) we aligned promoter sequences within subfamilies and represented the homology of each subfamily with a single sequence logo, thereby permitting a second order processing of these logos in which each subfamily is represented equally; 3) we developed a new algorithm, logoalign, which seeks an alignment of the above input logos that maximizes total information within small, motif-sized windows, and therefore designed to report motifs well represented across subfamilies; 4) we analyzed resulting motifs on several statistical grounds, including their total information as compared to controls, and their positioning near transcription start sites as compared to random positions in gene blocks.  a divergent set of v1r subfamilies have arisen by local gene duplication the mouse v1r gene repertoire consists of ~ intact coding regions that partition into major subfamilies. most of these v1rs reside within large clusters at nine chromosomal locations. three of these v1r clusters consist of more than one subfamily: the a and b subfamilies are co-clustered on mouse chromosome the j and k subfamilies are co-clustered on chromosome and the h and i subfamilies are co-clustered on chromosome three v1r subfamilies are found at more than one locus: the c subfamily is found at two locations on mouse chromosome the d subfamily is found at two locations on mouse chromosome and the e subfamily is clustered on both chromosome and v1r subfamilies have expanded by local gene block duplication. most of these local duplications occurred recently enough that the extent of the duplicated block is evident by sequence homology. typically, duplicated blocks are about kb in size; most of the duplicated sequence is upstream of the coding regions. we previously mapped the sequences of four transcriptional units from the a and b subfamilies onto their genomic blocks. each of these v1rs had a gene structure consisting of a ~1-kb coding exon located < kb from the 3' end of the duplicated block, and one or two short untranslated exons located upstream of the coding region. the putative transcription start sites typically map < kb from the 5' end of the duplicated blocks. thus, the v1r gene block duplications seem to have efficiently captured putative promoter regions, utrs, and coding regions, with little surrounding sequence. this observation hints that the sequence information sufficient to regulate individual v1r genes may be very proximal to transcription start sites. each subfamily has conserved putative promoter regions we previously identified putative promoter homology at the mouse chromosome- locus containing a cluster of v1rs from the a and b subfamilies. in this case, the putative promoter homology is shared between a and b genes. this observation raises a question as to whether this homology is universal, or, whether each locus might have its own promoter homology. in fact, neither seems to be the case. first, no sequence similarity is evident between a/b promoters and the gene blocks of any other subfamily. second, not all co-clustered subfamilies exhibit shared promoter homology, as was the case for the co-clustered a and b genes: the co-clustered j and k subfamilies do exhibit cross-subfamily non-coding homology, however, neither the co-clustered h and i subfamilies or the co-clustered e and f subfamilies exhibit cross-subfamily non-coding homology. in general, we instead find that upstream non-coding homology is evident only within subfamilies, irrespective of genomic location. thus, subfamilies distributed to multiple loci do exhibit non-coding homology among members at both loci. therefore, broad putative promoter homology is not universally shared, nor locus-specific, rather, it appears to be shared predominantly within subfamilies. for subsequent analyses, we refer to "promoter subfamilies" to indicate the ten sets of genes that share upstream, non-coding homology. as a first step in identifying putative regulatory motifs shared among v1r subfamilies, we decided to restrict our search to just the putative promoter regions. as noted previously for the ab promoter subfamily, putative promoters in this case were evident as upstream subregions of gene blocks that exhibited increased homology. like the ab promoter subfamily, upstream islands of non-coding, putative promoter homology are evident in other promoter subfamilies; a striking example is shown in the pipmaker plot of the v1rf gene in figure 1a, in which a ~500-bp island of non-coding homology is evident ~ kb upstream of the coding region. however, for most promoter subfamilies, the gene blocks have duplicated too recently to be able to detect block subsequences that are under more stringent selection. for example, the pipmaker plot of the v1rc gene in figure 1a, shows homology among c promoter subfamily members that spans the entire ~ kb block. in order to evaluate these less obvious cases, we made a second assumption about putative v1r regulatory sequences: in addition to exhibiting higher sequence identity, these regions are likely to be homologous among all promoter subfamily members. pipmaker plots, like those shown in figure 1a, contain both types of information, since the vertical axis in a plot represents percent pairwise sequence identity, and the number of plots crossing any position in the block represents the number of subfamily members with homology at that position. we transformed these two dimensions of "conservation" into a single "conservation score" at each position of each gene block. the conservation score is the average percent identity at each position based on all the pipmaker plots that cross that position; however, for each "missing gene" we include a 0% identity in this average calculation. in this way, the conservation score is severely penalized in regions where not all subfamily members exhibit homology. using this approach, we identify two subregions of v1r blocks that are most well conserved within promoter subfamilies. a prominent homology peak is generally observed across the coding regions and immediately upstream of the coding region. the non-coding portion immediately upstream of the coding region presumably includes the coding exon acceptor site, as well as translation regulatory signals. a second prominent homology peak is generally observed near the 5' end of the block, well upstream of the coding region and upstream of intervening low-homology non-coding sequence. these upstream peaks could represent promoter regions and selection of sequences containing transcriptional information. the putative transcription start sites identified previously by 5' race pcr for four genes from the ab promoter subfamily map within the upstream peaks in their respective gene blocks. these four start sites are located near the middle of their respective ~kilobase-size promoter homology, but do not map exactly to homologous positions. similarly, two previously characterized cdnas of the d subfamily initiate transcription from near the middle of their respective peaks, but not from precisely the same relative positions. therefore, if we assume that these cdnas accurately reveal transcription start sites and are representative cases for v1rs in general, it would appear that v1r promoters exhibit variable relative initiation positions within these much larger regions of promoter homology. we were next interested to know whether putative transcription start sites for other promoter subfamilies likewise mapped to their respective upstream peak regions. using mouse vno-derived cdna, we generated 5' race pcr products using gene-specific primers on at least one member of each v1r subfamily. as was the case for the ab and d promoter subfamilies, transcription start sites in all cases map to upstream peaks in their respective gene blocks. we identified multiple race products for three v1rs. in these cases, the putative tss maps to within bp, bp, and bp, respectively, with identical exon-intron gene structures. this slight variation in the length of race products might be due to degradation of rna templates or alternative start sites within promoters. nevertheless, with this limited sample, we find no evidence for alternative splicing or alternative promoters. therefore, our comparative sequence analysis of v1r genes, as well as 5' race results for of these v1rs, points to a single, well-conserved promoter region upstream of each gene. further analysis of these putative promoter regions is likely to reveal promising candidate sequence elements that contribute to v1r transcriptional regulation. we next analyzed sequence conservation within these putative promoter regions by examining nucleotide substitution rates within these regions as compared to coding and other non-coding regions. we confined our search to pairs of genes within subfamilies that exhibit non-coding block substitution rates between 15–25% so that all gene pairs considered would have approximately the same elapsed time since common ancestry. this substitution level range also permits comparisons between mouse-rat orthologous pairs, since mouse-rat orthologs are expected to exhibit 15–25% neutral substitution since the mouse-rat split. we find that coding sequences exhibit average substitution levels that are ~63% that of surrounding non-coding block sequences. we find that promoter regions tend to fall into two discrete classes. most promoter sequences exhibit substitution levels that are ~80–90% that of the surrounding non-coding block sequences. however, a subset of promoters exhibit much lower substitution levels that are comparable to levels observed in their coding regions. interestingly, the pairs of a and g paralogous promoters that exhibit these lower substitution rates, do not exhibit lower substitution rates in orthologous comparisons. this observation raises the possibility that gene conversions, which can only occur between paralogs and not orthologs, have contributed to homogenization of a and g promoters in mouse. gene conversions might be favored in order to maintain sets of broad promoter sequences that would then compete approximately equally well for universal transcription factors. it is also noteworthy that each of the promoter regions exceeds bp in size with few obvious breaks in homology. such large and unbroken regions of homology seem unlikely to be the consequence of strict conservation of transcription factor binding sites, yet seem to be feasible target sizes for gene conversion events. identification of cross-subfamily motifs using information-based techniques to this point, we have identified upstream, non-coding sequences that exhibit elevated conservation scores and transcription start sites. these putative promoter regions are hereafter referred to as "peaks", whereas the remaining non-coding regions of a gene block are referred to as "blocks". we next searched for "motifs" shared among peaks of the ten promoter subfamilies. "motifs" are defined in terms of nucleotide frequencies and a motif's quality is measured in terms of information content. the most common way to depict a motif is by a sequence logo, in which the base frequencies at each position in the motif are summarized graphically by the height of each letter. the units of a logo plot are bits of information. a motif is more information-rich when the base frequencies across the motif deviate more from expectation. in this regard, a particular position in a set of aligned sequences need not be absolutely conserved to be information-rich. indeed, according to information theory, a position in an aligned group of sequences that always is one of two bases can contain more information than a position that exhibits a clear majority of sequences with a single base, if in fact, the remaining sequences do not exhibit bias. thus, information profiling is a more refined method than percent identity for assessing the likelihood of a given base position containing part of a functional code. this is especially likely to be the case for transcription factor binding sites, since these sites are often degenerate and not absolutely conserved. some established motif-searching methods, such as meme, are not suitable for this particular problem because they have no knowledge of the hierarchy of the dataset. specifically, this dataset has two hierarchical levels due to very recent relationships between genes within subfamilies, yet very distant relationships between subfamilies. thus, without knowledge of this hierarchy, algorithms like meme report within-subfamily sequence identities we already knew about, as opposed to less conserved cross-subfamily homology of interest. another motif-searching strategy, phylogenetic footprinting solves this problem by utilizing an input tree that specifies the hierarchy of the dataset. however, this method is inappropriate in the context where input sequences are not homologous, too distantly related to produce a reliable phylogenetic tree, or where the phylogeny is uncertain due to concerted evolution. since it is not possible to produce a well resolved input v1r tree, and because we wished to design our algorithm for the analysis of unrelated input sequences and also to use information-based searching, we developed a solution catered to our particular problem. our solution is to abstract away from individual sequences by first generating a representative sequence logo for each promoter subfamily, each logo being derived from an alignment of the individual peak sequences of a single promoter subfamily. this logo reflects all of the information contained within the individual peaks, yet permits a second order analysis to identify motifs shared between these representative logos, thus, across promoter subfamilies, without any one promoter subfamily being weighted more heavily. the set of ten logos resulting from an alignment of the peak sequences for each of the ten promoter subfamilies, is provided in additional file in order to next find motifs shared among these ten logos, we designed an algorithm, logoalign, that performs a heuristic search for logo similarity within short, motif-sized windows. briefly, this algorithm begins by randomly selecting a motif-sized window in each of the ten input logos, combines the windows into a new motif-sized logo, and then calculates the total information contained in this new motif-sized logo. the algorithm then selects one of the ten input logos, and searches all 12-bp windows in that logo and identifies the 12-bp window in that logo that produces a new motif-sized logo with the maximum of total information when aligned with the other nine stationary windows. logoalign cycles through each of the other nine logos in a similar manner, each time identifying the 12-bp window in the logo being processed that maximizes total information in the alignment. the algorithm continues until window positions do not move for one complete cycle. the result of one complete trial is therefore a "local maximum" of information for an aligned set of 12-bp windows; this local maximum is referred to as a "motif". multiple trials, each with a set of random starting positions and cycling order, identified a distribution of information-rich motifs. as described in the introduction, logoalign was developed specifically for this particular application because it does not depend on being able to align all taxa while still being able to consider phylogenetic heirarchy in the dataset. we note that two other motif-searching algorithms have been recently developed in consideration of these same issues. the algorithm phylocon, like logoalign, performs an information-based motif search on sequence logos created from multiple alignments. however, phylocon uses an algorithm that we believe is suboptimal in our context for two reasons. first, phylocon makes use of local, un-gapped, sub-optimal, multiple alignments, rather than gapped, global, multiple alignments. using local alignments can be preferable if the sequences being aligned are not closely enough related to produce high-quality global alignments. however, the subfamilies in our dataset have broad contiguous regions of exceptionally high homology, with which we can produce high-quality global multiple alignments. global alignments can provide an additional layer of information, since the existence of gaps can indicate that an otherwise well-conserved region is not likely to bind a universally-utilized transcription factor if the motif is interrupted in a subset of sequences. second, phylocon searches the solution space using a deterministic greedy algorithm than will always progress to the same local maximum, but may never find the best global solution. since logoalign does not progress deterministically, it has an increased probability of identifying the best global solution with multiple iterations. a second, even newer program, phylogibbs is also similar to logoalign and phylocon in terms of its suitability for hierarchical datasets with incomplete phylogenies. this program uses a "simulated annealing" algorithm, and unlike phylocon, is non-deterministic and can utilize global alignments. thus, while phylogibbs differs from logoalign in specifics of its design, it generally approaches the motif-searching problem in a very similar way and may therefore be equally well-suited for our context. we are currently testing the relative sensitivities and computational efficiencies of several motif-searching strategies in various contexts as part of a broader assessment of logoalign. statistical validation of candidate motifs we assessed resulting motifs based on three criteria. first, we expect that multiple iterations of logoalign using randomly determined starting points should converge on a common set of information-rich motifs, as opposed to finding a different answer each iteration. second, we expect that biologically meaningful motifs should contain more information than motifs identified in searches on random control sequences. third, we expect that transcriptionally relevant motifs should more likely be positioned near transcription start sites than elsewhere in gene blocks, and/or exhibit common positioning relative to each other from gene to gene. motif convergence we conducted trials of logoalign, each iteration with a different starting point and path. the resulting motifs could immediately be collapsed into non-identical motifs; for example, the best motif was found times. we next partitioned the non-identical motifs into clusters of similar motifs, allowing us to ignore weaker versions of essentially identical higher-scoring motifs. therefore, from iterations, we observed > 97% convergence to merely non-redundant solutions, suggesting that we might have sufficiently sampled the sequence space to find a global maximum. significant information content we conducted three control experiments to assess the significance of the total information of v1r promoter motifs identified by logoalign. the first control establishes the noise level for randomly aligned sequences; the maximum total information in this case is ~ bits, whereas the minimum information context in the iterations of logoalign has more than double this information content. not surprisingly then, logoalign always progresses towards a more information-rich solution. the second control establishes the relative contribution of individual subfamilies. in this control, we establish that a biased distribution in which the most information-rich window from one logo is aligned with randomly selected windows from the other nine logos produces motifs only slightly above noise and significantly less than the information content in the experimental results. the most important control is to ask how logoalign performs on random sequences. to conduct this control, we shuffled v1r sequences not only in such a way to preserve base composition, but also to preserve the number, size, and diversity of subfamilies. thus, our control was a set of sequences with exactly the same properties as the experimental set, only with putative motifs scrambled. we find that the distribution of information in the control set versus the experimental set is bimodal, indicating that motifs identified in v1r promoters are more information-rich than those identified in random sequences. note that while the majority of motifs identified in v1r promoters contain more information than the maximum information-rich motifs identified in the control, we presume based on the overlap of these distributions that the least information-rich v1r promoter motifs identified in this study are probably not biologically significant. however, the best motifs contain significantly more information than those found in the control, and ~81% of identified v1r promoter motifs contain information that is > standard deviations above the mean for the control. non-random positioning we next analyzed motif occurrences within v1r gene blocks using sequence walking techniques. the rationale for this test is that some sequence motifs, even if information-rich among v1rs, might occur frequently in background sequence. therefore, some statistical measure is appropriate to ascertain that identified motifs are enriched specifically within v1r promoters, as opposed to random widespread occurrence elsewhere in the gene blocks. for this analysis, we focused on the five best motifs. generally, we find that these motifs tend to be located in better conserved parts of peaks, and the motifs found within peaks tend to be better conserved than motifs found elsewhere in gene blocks, suggesting that occurrence in promoter regions, but not in non-peak portions of blocks, are under the most stringent selective pressure. we find that these motifs occur within bp of putative transcription start sites with significantly greater frequency than within random bp windows of their gene blocks. note that this latter analysis assumes that putative transcription start sites in conserved v1r promoter subfamilies are located at homologous positions to empirically-determined start sites determined by race. as discussed previously, while this is probably not precisely the case, the 500-bp window used in this analysis seems sufficiently large to accommodate the expected variability in relative start positions. if all v1r transcription start sites were more precisely known, we expect we would observe an even greater relative enrichment of motif occurrences near tsss, since this knowledge would presumably permit the use of a smaller window size in the analysis. we next focussed on only those v1r genes in which transcription start sites were empirically determined by race in order to investigate more subtle patterning of our five most information-rich motifs identified in the study. the most compelling observation is that the highest-scoring occurrence of motif overlaps the 5' exon-intron junction for of v1rs where gene structures were determined by race, suggesting that this motif contains splice donor information for these upstream exons. in one case of the race products analyzed, motif is located precisely at the empirical transcription start site; however, for the other v1rs, the best version of this motif is found as far as bp upstream and bp downstream of empirical transcription start sites, and therefore it seems unlikely that this motif generally contains transcription initiation information. if motif is excluded, the best occurrence of the other four motifs is found just upstream of empirically-determined transcription start sites in 33/ cases, within the 5' exons in 7/ cases, and within the upstream intron in 8/ cases; therefore, it seems likely that these motifs generally contain transcriptional information, as opposed to, for example, exon or splicing information. we also explored the possibility that pairs of motifs might require critical spacing with respect to each other. we do find examples of motif pairs that exhibit surprisingly similar spacing across the promoters of multiple subfamilies. for example, the spacing between motif and motif is consistent within bp for different v1rs across five subfamilies. however, we do not observe conserved relative spacing that encompasses all, or even nearly all v1rs, suggesting that stringent spacing among motifs tested is not required, as might be predicted for binding sites of transcription factors cooperating/interacting in a regulatory complex. finally, we compared our five most information-rich motifs to a library of known transcription factor binding sites. the best occurrences of motifs and within v1r promoters frequently contain an "aagtt" that matches the core binding site for the myt zinc finger transcription factor; however, only ~a third of these motifs are recognized by the genomatix algorithm as a sufficient match to the myt site. in general, while we find that our motifs bare resemblance to a number of transcription factor binding sites represented in the database, we do not identify a compelling example in which the conserved core of a binding site is also a conserved core within any of our five best motifs. nevertheless, since few transcription factors have been investigated by chip-on-chip experiments to fully explore the range of actual binding sites in the genome, and indeed, in cases where transcription factor binding in the genome has been characterized in this comprehensive way, it appears bound sites can deviate significantly from consensus sequences, we only very tentatively suggest that our five motifs do not resemble known transcription factor targets.  in summary, we have used a combination of existing and new bioinformatic tools to discover that every v1r subfamily has a broad and well conserved promoter region that contains empirical transcription start sites. we speculate that the high level of conservation over such a large sequence territory might have resulted from gene conversions that would tend to broadly homogenize these sequences. homogenization in turn, could permit all v1rs of a particular subfamily to compete equally well for common transcription factors or complexes. we have developed a new information-based motif-searching strategy that permits sequence comparisons between different subfamilies, but is not dependent on the alignment of sequences across subfamilies, in order to identify candidate transcription factor binding motifs that are represented in all v1r promoters and present across all v1r subfamilies. the best motifs contain > bits of cumulative information, which is significantly more information than those identified in random sequences. three of these motifs have relatively high gc content, and the best motif is identified near transcription start sites in 94% of all v1r promoter regions. these observations suggest that these motifs are excellent candidate binding sites for v1r co-regulatory factors, a hypothesis we are now testing experimentally. our algorithm, logoalign, has potential for use in a broader context of gene co-regulation. two widely used approaches, exemplified by meme and phylogenetic footprinting, are appropriate in distinct contexts. meme is best used when analyzing sequences of comparable distances, but is not suitable when there is varying degrees of homology within the sequence set, because it does not correct for phylogenetic relatedness. phylogenetic footprinting is best used when analyzing sequences with varying degrees of homology, but is not suitable when some of the sequences are unrelated, because it depends on an input tree that establishes phylogenetic relationships for all input sequences. our algorithm, logoalign, as well others such as phylocon and phylogibbs, applies to a niche where there exists both varying degrees of homology and sets of unrelated sequences for which no phylogeny can be established. an example of this particular context would be in the evaluation of regulons elucidated by microarray studies, where both related and unrelated target genes may be part of a downstream battery of genes under the control of a particular transcription factor. we are currently conducting a broader comparative evaluation of the logoalign, phylocon, phylogibbs, and other related motif-searching strategies using synthetic controls in order to more rigorously assess relative sensitivities and context-dependent efficiencies of these various algorithmic approaches. 
we also find that the best motifs contain significantly more information than those identified in controls, and that these motifs are more likely to be found in the immediate vicinity of transcription start sites than elsewhere in gene blocks. results from a new motif-finding algorithm, logoalign, designed for this context and more generally for searching large, hierarchical datasets, suggest the existence of common information-rich regulatory motifs that are shared across otherwise divergent v1r subfamilies. in this study, we have characterized v1r promoter regions by comparative genomics and by mapping transcription start sites. therefore, these motifs are candidate binding sites for transcription factors involved in v1r co-regulation. while cross-subfamily homology is not evident by traditional methods, we developed a heuristic motif-searching tool, logoalign, and applied this tool to identify motifs shared within the promoters of all v1r genes. the sensory neurons of the vno express two types of chemosensory receptors, v1r and v2r. each sensory neuron of the apical compartment of the vno transcribes only one of the repertoire of v1r genes. we find that transcription is initiated from ~ kb promoter regions that are well conserved within v1r subfamilies. our analyses show that v1r subfamilies have broad and well conserved promoter regions from which transcription is initiated. this model predicts that the large repertoire of divergent v1r genes in the mouse genome contains common regulatory elements. there are ~ v1r genes in the mouse genome that have been classified into ~ divergent subfamilies. the best motifs occur near transcription start sites of ~90% of all v1r genes and across all of the divergent subfamilies.
 the mouse vomeronasal organ processes chemosensory information, including pheromone signals that influence reproductive behaviors. the sensory neurons of the vno express two types of chemosensory receptors, v1r and v2r. there are ~ v1r genes in the mouse genome that have been classified into ~ divergent subfamilies. each sensory neuron of the apical compartment of the vno transcribes only one of the repertoire of v1r genes. a model for mutually exclusive v1r transcription in these cells has been proposed in which each v1r gene might compete stochastically for a single transcriptional complex. this model predicts that the large repertoire of divergent v1r genes in the mouse genome contains common regulatory elements. in this study, we have characterized v1r promoter regions by comparative genomics and by mapping transcription start sites.  we find that transcription is initiated from ~ kb promoter regions that are well conserved within v1r subfamilies. while cross-subfamily homology is not evident by traditional methods, we developed a heuristic motif-searching tool, logoalign, and applied this tool to identify motifs shared within the promoters of all v1r genes. our motif-searching tool exhibits rapid convergence to a relatively small number of non-redundant solutions. we also find that the best motifs contain significantly more information than those identified in controls, and that these motifs are more likely to be found in the immediate vicinity of transcription start sites than elsewhere in gene blocks. the best motifs occur near transcription start sites of ~90% of all v1r genes and across all of the divergent subfamilies. therefore, these motifs are candidate binding sites for transcription factors involved in v1r co-regulation.  our analyses show that v1r subfamilies have broad and well conserved promoter regions from which transcription is initiated. results from a new motif-finding algorithm, logoalign, designed for this context and more generally for searching large, hierarchical datasets, suggest the existence of common information-rich regulatory motifs that are shared across otherwise divergent v1r subfamilies. 