BACKGROUND
in  <dig>  bejerano et al.
<cit>  made the startling discovery that there are hundreds of long genomic sequences extraordinarily conserved across human, mouse, and rat, most of them in noncoding regions and some of them very distant from the nearest human gene.
they defined an "ultraconserved element" to be at least  <dig> consecutive alignment columns, 100% of these columns perfectly conserved in human, mouse, and rat.
they reported  <dig> such elements across the human genome, exclusive of rrna genes.
they also reported incidentally that some fraction  of these ultraconserved elements are also well conserved in dog, in chicken, and in fugu, though with fewer than 100% of the columns perfectly conserved in these other species even in this fraction of elements.
their introduction of ultraconserved elements stimulated a flurry of subsequent research.
derti et al.
<cit>  compiled lists of similarly perfectly conserved elements in human-mouse-dog and in human-chicken, and observed a surprisingly small overlap in these three sets of ultraconserved elements.
sakuraba et al.
<cit>  compiled a list of elements each more than  <dig> bp long and each more than 95% identical between human and mouse, and observed that only 9-14% of these have conserved matches in fishes.
visel et al.
<cit>  showed that the noncoding ultraconserved elements of bejerano et al.
<cit>  were only a subset of elements under similar constraint and with similar regulatory function.
they generated this larger set of elements using gumby scores  <cit> , and showed that this larger set of noncoding ultraconserved elements is highly enriched in mouse enhancer activity.
rather than using percent of perfectly conserved columns, siepel et al.
<cit>  incorporated the phylogeny into the measure of conservation by using a phylogenetic hidden markov model, and defined highly conserved elements to be those with the highest log-odds scores, measuring how much more likely they are to be generated in the conserved than the nonconserved state of the model.
most of these works defined their conserved elements in terms of conservation across just  <dig> or  <dig> species, siepel et al.
<cit>  being an exception.
in this paper we extend the notion of ultraconserved elements in a very natural way to an arbitrarily large collection of species.
suppose that you are given a whole-genome multiple sequence alignment, such as the current 44-vertebrate whole-genome alignment available through the ucsc genome browser  <cit> .
you are interested in finding long regions of this alignment that are extraordinarily well conserved across all or most of the  <dig> species, in the spirit of generalizing the notion of ultraconserved elements of bejerano et al.
<cit> .
for concreteness in this introduction, let us say that you want to identify all regions of at least  <dig> consecutive alignment columns such that, for some subset s of at least  <dig> of the  <dig> species, at least 80% of the columns in this region are perfectly conserved  across all the species in s. because the 44-vertebrate whole-genome alignment occupies approximately  <dig> gigabytes of memory, algorithmic efficiency is a concern.
in the next section, we consider the generalization of this problem instance to arbitrary alignments, any number of columns, any minimum cardinality |s|, and any percentage of conserved columns.
we call such well conserved regions "extremely conserved elements".
we present a linear time algorithm for finding all such elements, provided the subset s is the entire set of aligned species.
for an arbitrary subset s, we demonstrate that the problem is np-complete  <cit>  and hence it is unlikely that there is an efficient algorithm for finding extremely conserved elements in this general case.
as an illustration of the linear time algorithm, we present results for the concrete instantiation of the problem given above.
in the current 44-vertebrate whole-genome alignment, there are  <dig> elements, each with at least  <dig> alignment columns and each perfectly conserved across the same  <dig> or more vertebrates in at least 80% of its columns.
the longest such element is  <dig> columns long and occurs  <dig> kbp from the nearest gene on human chromosome  <dig>  perfectly conserved in 80% of its columns across  <dig> of the species, missing only gorilla, shrew, and lamprey.
there is also a region  <dig> bp long,  <dig> kbp upstream of the foxb <dig> gene on human chromosome  <dig>  with 90% of its columns perfectly conserved across all  <dig> vertebrates.
RESULTS
problem statement and algorithms
we begin with a precise formulation of the extremely conserved element problem:
inputs: m × n alignment matrix m with entries from {a, c, g, t, -}, integer s ≤ m, integer t ≤ n, and real number  <dig> <c ≤  <dig>
problem: determine if m has a subset s of rows, a subset t of consecutive columns , and a subset u of t, with |s| ≥ s, |t| ≥ t, and |u| ≥ c|t| such that, in the matrix m restricted to s × u, every column is perfectly conserved .
note that neither s nor u need be consecutive.
for example, the illustrative problem in the introduction is the version of the extremely conserved element problem with m =  <dig>  n ≈  <dig>  ×  <dig>  s =  <dig>  t =  <dig>  and c =  <dig> .
the condition that every column in s × u be perfectly conserved is overly simplistic.
more realistically, the conservation measure should depend on the phylogeny relating the species, as does, for example, the measure used by phastcons  <cit> .
suppose that f is any conservation scoring function .
the algorithm of theorem  <dig> is easily generalized to the problem in which every column in s × u must have f exceeding some threshold τ.
theorem 1: if s = m, the extremely conserved element problem can be solved in time o. in fact, the maximum value of t can be determined in this time.
proof: assume without loss of generality that no column contains the gap character "-" in every row.
for  <dig> ≤ i ≤ n, let qi =  <dig> if column i is perfectly conserved, and qi =  <dig> otherwise.
the result then follows from theorem  <dig>    □
theorem 2: given q ∈ { <dig> }n and  <dig> <c ≤  <dig>  there is an o time algorithm that maximizes j - i subject to the condition that qi+ <dig> ... qj contains at least c 1's.
proof: a variety of linear time algorithms for this problem have appeared in the literature  <cit> , although this is the first time it has been applied to multiple sequence alignments on a gigabyte scale.
we give here a new and simpler algorithm due to eddie grove and benno schwikowski .
for  <dig> ≤ i ≤ n, let
let x be the number of 1's in qi+ <dig> ... qj.
then
thus, rj ≥ ri if and only if qi+ <dig> ... qj has at least c 1's, so the objective is to maximize j - i subject to rj ≥ ri.
for  <dig> ≤ i ≤ n, let xi = min and yi = max.
x and y are each nonincreasing sequences.
we claim that the objective above is equivalent to maximizing j - i subject to yj ≥ xi: if rj ≥ ri, then yj = max ≥ rj ≥ ri ≥ min = xi.
if yj ≥ xi and xi <xi- <dig> and yj >yj+ <dig>  then ri = xi and rj = yj, so rj ≥ ri.
in particular,  maximizes j - i subject to rj ≥ ri if and only if  maximizes j - i subject to yj ≥ xi.
since x and y are sorted, the latter can be found in linear time: merge x and y, breaking ties by taking elements from y first.
then identify the maximum j - i such that yj and xi are adjacent  in the sorted list.
□
in fact, in the proof of theorem  <dig>  any pair  such that yj and xi are adjacent  in the sorted list corresponds to a maximal interval qi+ <dig> ... qj that contains at least c 1's.
thus, all such maximal intervals can be found in linear time.
the dual of theorem  <dig>  maximizing c subject to a lower bound on j - i, also can be accomplished in linear time  <cit> .
this implies that, for s = m, the maximum value of c in the extremely conserved element problem can also be determined in time o.
for arbitrary s, the following theorem provides another special case in which the problem can be solved efficiently.
theorem 3: if c =  <dig>  the extremely conserved element problem can be solved in polynomial time.
in fact, the maximum value of s can be determined in this time.
proof: for every choice t of at least t consecutive columns, sort the rows of t lexicographically and look for s identical rows, with at least t nongap characters each, in this sorted list.
□
however, for the general case, the following theorem shows that it is unlikely that there is an efficient algorithm  <cit> .
theorem 4: the general extremely conserved element problem is np-complete, even if t = n and m's entries are all either a or t.
proof: the reduction used is very similar to the reduction from clique to balanced complete bipartite subgraph  <cit> .
let  be an instance of the clique problem, where g =  is an undirected graph and k is an integer.
assume without loss of generality that k < |v| -  <dig>  consider the bipartite graph b = , f), where x = v, y = e, and f = { | v ∉ e}.
let m be the |x| × |y| adjacency matrix of b, where mij= a if  ∈ f and mij = t otherwise.
let s = |v| - k, t = |e|, and c = /|e|.
we will show that g has a k-clique if and only if m has the appropriate extremely conserved element.
suppose that c ⊆ v is a k-clique of g. choose s = v - c and u = {{u, v} | u ∈ c and v ∈ c}.
|s| = |v| - k and |u| =  and, in b, every vertex in s is adjacent to every vertex in u. hence, the submatrix of m restricted to s × u contains only the character a.
conversely, suppose that m has a  ×  submatrix m' each of whose columns is perfectly conserved.
since each vertex v in y is not adjacent to exactly  <dig> vertices in x, it is impossible for v's column of m' to consist only of the character t when |v| - k >  <dig>  as is the case.
hence, m' contains only the character a. that is, there are subsets s of x and u of y that form a complete bipartite subgraph of b, with |s| = |v| - k and |u| = .
every vertex {u, v} ∈ u must satisfy u ∈ v - s and v ∈ v - s since, in b, {u, v} is adjacent to every vertex in s. but |v - s| = k, so the  vertices in u correspond to the edges of a k-clique v - s in g.   □
catalog of extremely conserved elements
as an illustration of theorem  <dig>  we present results for the concrete instantiation of the problem given in the introduction.
in the current 44-vertebrate whole-genome multiz alignment  available through the ucsc genome browser  <cit> , we identify all extremely conserved elements with at least  <dig> consecutive alignment columns such that, for some subset s of at least  <dig> species including human, at least 80% of the columns in this region are perfectly conserved across all the species in s.  we refer to such elements as ec elements.
despite the np-completeness demonstrated in theorem  <dig>  the algorithm of theorem  <dig> still allows a feasible solution to this particular instantiation of the general extremely conserved element problem.
the simple reason is that  =  <dig>  is not an impossibly large number of combinations on which to run the linear time algorithm.
had we asked for conservation across only  <dig> rather than  <dig> species, the computation would have been prohibitive, because  >  <dig> ×  <dig>  in addition, there are two novel filters described in methods that make the application to whole-genome alignments feasible.
in the current 44-vertebrate whole-genome alignment, our algorithm produces  <dig> ec elements.
a complete listing of these elements is given in additional files.
additional file  <dig> is a spreadsheet that shows each ec element's human genome coordinates, its length, percent identity, names of missing species, name of the human gene in which it resides , names of and distances to the two nearest neighboring genes, and overlap with previously identified conserved elements  <cit> .
additional file  <dig> shows the exact alignment for each ec element.
additional file  <dig> shows the single longest extremely conserved element that has at least 90% of its columns perfectly conserved across all  <dig> vertebrate species.
it is  <dig> bp long.
for the  <dig> human genes either containing an ec element, or immediately upstream or downstream from that element if it is between genes, we investigated enrichment for biological process go terms, using webgestalt  <cit> .
the results are shown in table  <dig>  these enrichments are in accord with previous human-rodent studies  <cit> , which reported significant functional enrichment for genes involved in regulation of transcription, dna binding, development, and nervous system development.
for the genes containing the  <dig> ec elements that overlap human coding exons, there is functional enrichment for rna processing .
this is consistent with the reported findings for genes containing ultraconserved elements that overlap coding exons, which show significant functional enrichment for rna binding and regulation of splicing  <cit> .
as was observed for ultraconserved elements  <cit> , it is quite common to see three to eight ec elements clustered within the same gene or within the same intergenic region .
as one extreme example, eight occur within the introns and another two upstream of the human gene zfpm <dig> on chromosome  <dig>  zfpm <dig> is a zinc finger transcription factor that modulates the activity of gata family proteins, which are important regulators of cardiogenesis.
none of these ten zfpm <dig> ec elements overlap ultraconserved elements of bejerano et al.
<cit> , and three of them do not even overlap the larger set of constrained human-rodent elements of visel et al.
<cit> , so are novel.
the longest ec element found is  <dig> columns long and is perfectly conserved in 80% of its columns across  <dig> of the species, missing only gorilla, shrew, and lamprey.
it occurs  <dig> kbp downstream of the nearest gene on human chromosome  <dig>  but interestingly it is  <dig> kbp upstream of its other neighboring gene znf <dig>  which has two other upstream and three intronic ec elements.
znf <dig> is a zinc finger protein, expressed in the developing central nervous system, that negatively regulates neuron differentiation  <cit> .
only two of these six ec elements overlap ultraconserved elements of bejerano et al.
<cit> .
note, though, that the distribution of the lengths of ec elements is not significant since, as pointed out in methods, our algorithm sacrifices length in preference for number of species in the element.
as one extreme example, there are abutting elements at human hg <dig> coordinates chrx:24826152- <dig> and chrx:24826333- <dig> of lengths  <dig> and  <dig>  respectively.
the first is missing alpaca, sloth, medaka, and lamprey, while the second is missing only alpaca, medaka, and lamprey.
had the algorithm not prioritized number of species over length, it would have produced a single ec element of length  <dig>  which would have been longer than the current longest element.
these two current elements are two out of three ec elements that occur in an intron of pola <dig>  which encodes the dna polymerase alpha catalytic subunit.
lamprey, the species most distant from the mammals and also a low-coverage genome assembly, is missing from  <dig> of the  <dig> ec elements.
the species with the next highest numbers are gorilla , cat , and zebrafish .
like lamprey, gorilla and cat are low-coverage genome assemblies.
on the other hand, fugu is missing from only  <dig> of the  <dig> ec elements, zebra finch is missing from only  <dig>  chicken is missing from only  <dig>  and lizard is missing from only  <dig>  these figures suggest that depth of sequencing is a greater determinant of inclusion in extremely conserved elements than is evolutionary distance, and also suggest that additional extremely conserved elements will emerge as the quality of genome sequences increases.
<dig>  of the  <dig> ec elements overlap an ultraconserved element of bejerano et al.
<cit> .
<dig>  overlap the larger set of constrained human-rodent elements of visel et al.
<cit> .
these overlaps confirm the fact that we have identified significant conserved elements that cannot be found by applying a more stringent conservation criterion to a smaller collection of species such as human and rodents.
all  <dig> ec elements overlap phastcons highly conserved elements  <cit>   with phastcons log-odds scores each exceeding  <dig>  details of all these overlaps are shown in additional file  <dig>  the phastcons highly conserved elements have the realistic advantage of taking the phylogeny and branch lengths into account, which our extremely conserved elements do not.
however, because their log-odds scores favor longer alignments, phastcons highly conserved elements tend to be much longer than ec elements, with less intense concentration of extremely conserved columns.
there are  <dig>  phastcons highly conserved elements with log-odds score at least  <dig>  of which only a certain  <dig> contain within them ec elements.
the average length of these  <dig>  elements is  <dig> bp, with many of them several kilobasepairs long, whereas the average ec element is less than  <dig> bp long.
there is no obvious way of querying phastcons highly conserved elements so as to identify those with such intense concentration of extremely conserved columns.
for instance, if you restrict attention to those highly conserved elements with log-odds score at least  <dig> and length at most  <dig> bp, this long list would contain only  <dig> of the  <dig> ec elements; the remaining  <dig>  though as extremely conserved, occur within longer highly conserved elements.
of the genes containing ec elements that do not contain nor are adjacent to either ultraconserved elements of bejerano et al.
<cit>  nor the larger set of constrained human-rodent elements of visel et al.
<cit> , three are particularly notable because their functions are closely related to the go term enrichments discussed near the beginning of this section.
nlgn <dig> on human chromosome  <dig> contains an intronic ec element and is involved in nervous system development.
in particular, this gene encodes a member of a family of neuronal cell surface proteins that may be involved in the formation and remodeling of central nervous system synapses.
whsc1l <dig> on human chromosome  <dig> contains a partially coding ec element and is involved both in regulation of transcription and in cell differentiation.
more specifically, this gene encodes a histone methyltransferase that preferentially methylates k <dig> and k <dig> of histone h <dig>  which are epigenetic tags for transcriptional regulation.
rbm <dig> on human chromosome  <dig> contains a partially coding ec element and, like many other genes with such coding elements, is involved in rna processing.
in particular, this gene encodes a component of the spliceosome a complex and regulates alternative splicing of a number of mrnas, including fas and casp2/caspase- <dig> in the apoptosis process.
in the case of fas, it promotes exclusion of exon  <dig>  producing a soluble form of fas that inhibits apoptosis.
in the case of casp2/caspase- <dig>  it promotes exclusion of exon  <dig>  producing a catalytically active form of casp2/caspase- <dig> that induces apoptosis.
these three genes, nlgn <dig>  whsc1l <dig>  and rbm <dig>  are just some of the genes containing extremely conserved elements that were not uncovered in previous studies of ultraconservation.
CONCLUSIONS
the notion of ultraconserved element was introduced by bejerano et al.
<cit>  to point out that there are certain long genomic sequences with extreme conservation between humans and rodents.
we generalized their definition in a natural way that allows one to look for such extreme conservation over a much larger collection of species.
we presented a linear time algorithm  to find all such maximal length extremely conserved elements, provided that one insists on conservation across all the aligned species.
in contrast, we showed that, for the general case of conservation across an arbitrary subset of the species, the question of whether there is an extremely conserved element is np-complete , so it is unlikely an efficient algorithm exists for this general case  <cit> .
this is true even in the special case of a gapless multiple sequence alignment.
finally, we illustrated the linear time algorithm by identifying all extremely conserved elements with s =  <dig>  t =  <dig>  and c =  <dig>  in the currently available 44-vertebrate whole-genome alignment.
the resulting  <dig> ec elements demonstrate many of the characteristics of the original ultraconserved elements  <cit> .

 in bejerano et al. made the startling discovery that there are hundreds of long genomic sequences extraordinarily conserved across human, mouse, and rat, most of them in noncoding regions and some of them very distant from the nearest human gene. they defined an "ultraconserved element" to be at least consecutive alignment columns, 100% of these columns perfectly conserved in human, mouse, and rat. they reported such elements across the human genome, exclusive of rrna genes. they also reported incidentally that some fraction of these ultraconserved elements are also well conserved in dog, in chicken, and in fugu, though with fewer than 100% of the columns perfectly conserved in these other species even in this fraction of elements. their introduction of ultraconserved elements stimulated a flurry of subsequent research. derti et al. compiled lists of similarly perfectly conserved elements in human-mouse-dog and in human-chicken, and observed a surprisingly small overlap in these three sets of ultraconserved elements. sakuraba et al. compiled a list of elements each more than bp long and each more than 95% identical between human and mouse, and observed that only 9-14% of these have conserved matches in fishes. visel et al. showed that the noncoding ultraconserved elements of bejerano et al. were only a subset of elements under similar constraint and with similar regulatory function. they generated this larger set of elements using gumby scores, and showed that this larger set of noncoding ultraconserved elements is highly enriched in mouse enhancer activity. rather than using percent of perfectly conserved columns, siepel et al. incorporated the phylogeny into the measure of conservation by using a phylogenetic hidden markov model, and defined highly conserved elements to be those with the highest log-odds scores, measuring how much more likely they are to be generated in the conserved than the nonconserved state of the model. most of these works defined their conserved elements in terms of conservation across just or species, siepel et al. being an exception. in this paper we extend the notion of ultraconserved elements in a very natural way to an arbitrarily large collection of species. suppose that you are given a whole-genome multiple sequence alignment, such as the current 44-vertebrate whole-genome alignment available through the ucsc genome browser. you are interested in finding long regions of this alignment that are extraordinarily well conserved across all or most of the species, in the spirit of generalizing the notion of ultraconserved elements of bejerano et al.. for concreteness in this introduction, let us say that you want to identify all regions of at least consecutive alignment columns such that, for some subset s of at least of the species, at least 80% of the columns in this region are perfectly conserved across all the species in s. because the 44-vertebrate whole-genome alignment occupies approximately gigabytes of memory, algorithmic efficiency is a concern. in the next section, we consider the generalization of this problem instance to arbitrary alignments, any number of columns, any minimum cardinality |s|, and any percentage of conserved columns. we call such well conserved regions "extremely conserved elements". we present a linear time algorithm for finding all such elements, provided the subset s is the entire set of aligned species. for an arbitrary subset s, we demonstrate that the problem is np-complete and hence it is unlikely that there is an efficient algorithm for finding extremely conserved elements in this general case. as an illustration of the linear time algorithm, we present results for the concrete instantiation of the problem given above. in the current 44-vertebrate whole-genome alignment, there are elements, each with at least alignment columns and each perfectly conserved across the same or more vertebrates in at least 80% of its columns. the longest such element is columns long and occurs kbp from the nearest gene on human chromosome perfectly conserved in 80% of its columns across of the species, missing only gorilla, shrew, and lamprey. there is also a region bp long, kbp upstream of the foxb gene on human chromosome with 90% of its columns perfectly conserved across all vertebrates.  problem statement and algorithms we begin with a precise formulation of the extremely conserved element problem: inputs: m × n alignment matrix m with entries from {a, c, g, t, -}, integer s ≤ m, integer t ≤ n, and real number <c ≤ problem: determine if m has a subset s of rows, a subset t of consecutive columns, and a subset u of t, with |s| ≥ s, |t| ≥ t, and |u| ≥ c|t| such that, in the matrix m restricted to s × u, every column is perfectly conserved. note that neither s nor u need be consecutive. for example, the illustrative problem in the introduction is the version of the extremely conserved element problem with m = n ≈ × s = t = and c =. the condition that every column in s × u be perfectly conserved is overly simplistic. more realistically, the conservation measure should depend on the phylogeny relating the species, as does, for example, the measure used by phastcons. suppose that f is any conservation scoring function. the algorithm of theorem is easily generalized to the problem in which every column in s × u must have f exceeding some threshold τ. theorem 1: if s = m, the extremely conserved element problem can be solved in time o. in fact, the maximum value of t can be determined in this time. proof: assume without loss of generality that no column contains the gap character "-" in every row. for ≤ i ≤ n, let qi = if column i is perfectly conserved, and qi = otherwise. the result then follows from theorem    □ theorem 2: given q ∈ { }n and <c ≤ there is an o time algorithm that maximizes j - i subject to the condition that qi+... qj contains at least c 1's. proof: a variety of linear time algorithms for this problem have appeared in the literature, although this is the first time it has been applied to multiple sequence alignments on a gigabyte scale. we give here a new and simpler algorithm due to eddie grove and benno schwikowski. for ≤ i ≤ n, let let x be the number of 1's in qi+... qj. then thus, rj ≥ ri if and only if qi+... qj has at least c 1's, so the objective is to maximize j - i subject to rj ≥ ri. for ≤ i ≤ n, let xi = min and yi = max. x and y are each nonincreasing sequences. we claim that the objective above is equivalent to maximizing j - i subject to yj ≥ xi: if rj ≥ ri, then yj = max ≥ rj ≥ ri ≥ min = xi. if yj ≥ xi and xi <xi- and yj >yj+ then ri = xi and rj = yj, so rj ≥ ri. in particular, maximizes j - i subject to rj ≥ ri if and only if maximizes j - i subject to yj ≥ xi. since x and y are sorted, the latter can be found in linear time: merge x and y, breaking ties by taking elements from y first. then identify the maximum j - i such that yj and xi are adjacent in the sorted list.   □ in fact, in the proof of theorem any pair such that yj and xi are adjacent in the sorted list corresponds to a maximal interval qi+... qj that contains at least c 1's. thus, all such maximal intervals can be found in linear time. the dual of theorem maximizing c subject to a lower bound on j - i, also can be accomplished in linear time. this implies that, for s = m, the maximum value of c in the extremely conserved element problem can also be determined in time o. for arbitrary s, the following theorem provides another special case in which the problem can be solved efficiently. theorem 3: if c = the extremely conserved element problem can be solved in polynomial time. in fact, the maximum value of s can be determined in this time. proof: for every choice t of at least t consecutive columns, sort the rows of t lexicographically and look for s identical rows, with at least t nongap characters each, in this sorted list.   □ however, for the general case, the following theorem shows that it is unlikely that there is an efficient algorithm. theorem 4: the general extremely conserved element problem is np-complete, even if t = n and m's entries are all either a or t. proof: the reduction used is very similar to the reduction from clique to balanced complete bipartite subgraph. let be an instance of the clique problem, where g = is an undirected graph and k is an integer. assume without loss of generality that k < |v| - consider the bipartite graph b =, f), where x = v, y = e, and f = { | v ∉ e}. let m be the |x| × |y| adjacency matrix of b, where mij= a if ∈ f and mij = t otherwise. let s = |v| - k, t = |e|, and c = /|e|. we will show that g has a k-clique if and only if m has the appropriate extremely conserved element. suppose that c ⊆ v is a k-clique of g. choose s = v - c and u = {{u, v} | u ∈ c and v ∈ c}. |s| = |v| - k and |u| = and, in b, every vertex in s is adjacent to every vertex in u. hence, the submatrix of m restricted to s × u contains only the character a. conversely, suppose that m has a × submatrix m' each of whose columns is perfectly conserved. since each vertex v in y is not adjacent to exactly vertices in x, it is impossible for v's column of m' to consist only of the character t when |v| - k > as is the case. hence, m' contains only the character a. that is, there are subsets s of x and u of y that form a complete bipartite subgraph of b, with |s| = |v| - k and |u| =. every vertex {u, v} ∈ u must satisfy u ∈ v - s and v ∈ v - s since, in b, {u, v} is adjacent to every vertex in s. but |v - s| = k, so the vertices in u correspond to the edges of a k-clique v - s in g.   □ catalog of extremely conserved elements as an illustration of theorem we present results for the concrete instantiation of the problem given in the introduction. in the current 44-vertebrate whole-genome multiz alignment available through the ucsc genome browser, we identify all extremely conserved elements with at least consecutive alignment columns such that, for some subset s of at least species including human, at least 80% of the columns in this region are perfectly conserved across all the species in s. we refer to such elements as ec elements. despite the np-completeness demonstrated in theorem the algorithm of theorem still allows a feasible solution to this particular instantiation of the general extremely conserved element problem. the simple reason is that = is not an impossibly large number of combinations on which to run the linear time algorithm. had we asked for conservation across only rather than species, the computation would have been prohibitive, because > × in addition, there are two novel filters described in methods that make the application to whole-genome alignments feasible. in the current 44-vertebrate whole-genome alignment, our algorithm produces ec elements. a complete listing of these elements is given in additional files. additional file is a spreadsheet that shows each ec element's human genome coordinates, its length, percent identity, names of missing species, name of the human gene in which it resides, names of and distances to the two nearest neighboring genes, and overlap with previously identified conserved elements. additional file shows the exact alignment for each ec element. additional file shows the single longest extremely conserved element that has at least 90% of its columns perfectly conserved across all vertebrate species. it is bp long. for the human genes either containing an ec element, or immediately upstream or downstream from that element if it is between genes, we investigated enrichment for biological process go terms, using webgestalt. the results are shown in table these enrichments are in accord with previous human-rodent studies, which reported significant functional enrichment for genes involved in regulation of transcription, dna binding, development, and nervous system development. for the genes containing the ec elements that overlap human coding exons, there is functional enrichment for rna processing. this is consistent with the reported findings for genes containing ultraconserved elements that overlap coding exons, which show significant functional enrichment for rna binding and regulation of splicing. as was observed for ultraconserved elements, it is quite common to see three to eight ec elements clustered within the same gene or within the same intergenic region. as one extreme example, eight occur within the introns and another two upstream of the human gene zfpm on chromosome zfpm is a zinc finger transcription factor that modulates the activity of gata family proteins, which are important regulators of cardiogenesis. none of these ten zfpm ec elements overlap ultraconserved elements of bejerano et al., and three of them do not even overlap the larger set of constrained human-rodent elements of visel et al., so are novel. the longest ec element found is columns long and is perfectly conserved in 80% of its columns across of the species, missing only gorilla, shrew, and lamprey. it occurs kbp downstream of the nearest gene on human chromosome but interestingly it is kbp upstream of its other neighboring gene znf which has two other upstream and three intronic ec elements. znf is a zinc finger protein, expressed in the developing central nervous system, that negatively regulates neuron differentiation. only two of these six ec elements overlap ultraconserved elements of bejerano et al.. note, though, that the distribution of the lengths of ec elements is not significant since, as pointed out in methods, our algorithm sacrifices length in preference for number of species in the element. as one extreme example, there are abutting elements at human hg coordinates chrx:24826152- and chrx:24826333- of lengths and respectively. the first is missing alpaca, sloth, medaka, and lamprey, while the second is missing only alpaca, medaka, and lamprey. had the algorithm not prioritized number of species over length, it would have produced a single ec element of length which would have been longer than the current longest element. these two current elements are two out of three ec elements that occur in an intron of pola which encodes the dna polymerase alpha catalytic subunit. lamprey, the species most distant from the mammals and also a low-coverage genome assembly, is missing from of the ec elements. the species with the next highest numbers are gorilla, cat, and zebrafish. like lamprey, gorilla and cat are low-coverage genome assemblies. on the other hand, fugu is missing from only of the ec elements, zebra finch is missing from only chicken is missing from only and lizard is missing from only these figures suggest that depth of sequencing is a greater determinant of inclusion in extremely conserved elements than is evolutionary distance, and also suggest that additional extremely conserved elements will emerge as the quality of genome sequences increases. of the ec elements overlap an ultraconserved element of bejerano et al.. overlap the larger set of constrained human-rodent elements of visel et al.. these overlaps confirm the fact that we have identified significant conserved elements that cannot be found by applying a more stringent conservation criterion to a smaller collection of species such as human and rodents. all ec elements overlap phastcons highly conserved elements with phastcons log-odds scores each exceeding details of all these overlaps are shown in additional file the phastcons highly conserved elements have the realistic advantage of taking the phylogeny and branch lengths into account, which our extremely conserved elements do not. however, because their log-odds scores favor longer alignments, phastcons highly conserved elements tend to be much longer than ec elements, with less intense concentration of extremely conserved columns. there are phastcons highly conserved elements with log-odds score at least of which only a certain contain within them ec elements. the average length of these elements is bp, with many of them several kilobasepairs long, whereas the average ec element is less than bp long. there is no obvious way of querying phastcons highly conserved elements so as to identify those with such intense concentration of extremely conserved columns. for instance, if you restrict attention to those highly conserved elements with log-odds score at least and length at most bp, this long list would contain only of the ec elements; the remaining though as extremely conserved, occur within longer highly conserved elements. of the genes containing ec elements that do not contain nor are adjacent to either ultraconserved elements of bejerano et al. nor the larger set of constrained human-rodent elements of visel et al., three are particularly notable because their functions are closely related to the go term enrichments discussed near the beginning of this section. nlgn on human chromosome contains an intronic ec element and is involved in nervous system development. in particular, this gene encodes a member of a family of neuronal cell surface proteins that may be involved in the formation and remodeling of central nervous system synapses. whsc1l on human chromosome contains a partially coding ec element and is involved both in regulation of transcription and in cell differentiation. more specifically, this gene encodes a histone methyltransferase that preferentially methylates k and k of histone h which are epigenetic tags for transcriptional regulation. rbm on human chromosome contains a partially coding ec element and, like many other genes with such coding elements, is involved in rna processing. in particular, this gene encodes a component of the spliceosome a complex and regulates alternative splicing of a number of mrnas, including fas and casp2/caspase- in the apoptosis process. in the case of fas, it promotes exclusion of exon producing a soluble form of fas that inhibits apoptosis. in the case of casp2/caspase- it promotes exclusion of exon producing a catalytically active form of casp2/caspase- that induces apoptosis. these three genes, nlgn whsc1l and rbm are just some of the genes containing extremely conserved elements that were not uncovered in previous studies of ultraconservation.  the notion of ultraconserved element was introduced by bejerano et al. to point out that there are certain long genomic sequences with extreme conservation between humans and rodents. we generalized their definition in a natural way that allows one to look for such extreme conservation over a much larger collection of species. we presented a linear time algorithm to find all such maximal length extremely conserved elements, provided that one insists on conservation across all the aligned species. in contrast, we showed that, for the general case of conservation across an arbitrary subset of the species, the question of whether there is an extremely conserved element is np-complete, so it is unlikely an efficient algorithm exists for this general case. this is true even in the special case of a gapless multiple sequence alignment. finally, we illustrated the linear time algorithm by identifying all extremely conserved elements with s = t = and c = in the currently available 44-vertebrate whole-genome alignment. the resulting ec elements demonstrate many of the characteristics of the original ultraconserved elements. 
their announcement stimulated a flurry of subsequent research. announced the startling discovery of hundreds of "ultraconserved elements", long genomic sequences perfectly conserved across human, mouse, and rat. for the general case of conservation across an arbitrary subset of the aligned species, we show that the question of whether there exists an extremely conserved element is np-complete. the np-completeness in the case of conservation across an arbitrary subset of the aligned species implies that it is unlikely an efficient algorithm exists for this general case. there is a linear time algorithm to find all such extremely conserved elements in any multiple sequence alignment, provided that the conservation is required to be across all the aligned species. we illustrate the linear time algorithm by cataloguing all extremely conserved elements in the currently available 44-vertebrate whole-genome alignment, and point out some of the characteristics of these elements. we generalize the notion of ultraconserved element in a natural way from extraordinary human-rodent conservation to extraordinary conservation over an arbitrary set of species.
 in bejerano et al. announced the startling discovery of hundreds of "ultraconserved elements", long genomic sequences perfectly conserved across human, mouse, and rat. their announcement stimulated a flurry of subsequent research.  we generalize the notion of ultraconserved element in a natural way from extraordinary human-rodent conservation to extraordinary conservation over an arbitrary set of species. we call these "extremely conserved elements". there is a linear time algorithm to find all such extremely conserved elements in any multiple sequence alignment, provided that the conservation is required to be across all the aligned species. for the general case of conservation across an arbitrary subset of the aligned species, we show that the question of whether there exists an extremely conserved element is np-complete. we illustrate the linear time algorithm by cataloguing all extremely conserved elements in the currently available 44-vertebrate whole-genome alignment, and point out some of the characteristics of these elements.  the np-completeness in the case of conservation across an arbitrary subset of the aligned species implies that it is unlikely an efficient algorithm exists for this general case. despite this fact, for the interesting case of conservation across all or most of the aligned species, our algorithm is efficient enough to be practical. the extremely conserved elements that we catalog demonstrate many of the characteristics of the original ultraconserved elements of bejerano et al. 