COMPUTATIONAL TOOLS 91
that although “all 518 [kinase] genes are covered by some EST [Expressed Sequence Tag] sequence, and
~90% are present in gene predictions from the Celera and public genome databases,... those predic-
tions are often fragmentary or inaccurate and are frequently misannotated.”^99
There are several reasons for these limitations. First, only a fraction of newly discovered sequences have
identifiable homologous genes in the current databases.^100 The proportion of vertebrate genes with no detect-
able similarity in other phyla is estimated to be about 50 percent,^101 and this is supported by a recent analysis
of human chromosome 22, where only 50 percent of the proteins are found to be similar to previously known
proteins.^102 Also, the most prominent vertebrate organisms in GenBank have only a fraction of their genomes
present in finished (versus draft, error-prone) sequences. Hence, it is obvious that sequence similarity search
within vertebrates is currently limited. Second, sequence similarity searches are computationally expensive
when query sequences have to be matched against a large number of sequences in the databases.
To resolve this problem, a dictionary-based method, such as Identifier of Coding Exons (ICE), is often
employed. In this method, gene sequences in the reference database are fragmented into subsequences of
length k, and these subsequences make up the dictionary against which a query sequence is matched. If the
subsequences corresponding to a gene have at least m consecutive matches with a query sequence, the gene is
selected for closer examination. Full-length alignment techniques are then applied to the selected gene se-
quences. The dictionary-based approach significantly reduces the processing time (down to seconds per gene).
In compositional and signal search, a model (typically a hidden Markov model) is constructed that
integrates coding statistics (measures indicative of protein coding functions) with signal detection into
one framework. An example of a simple hidden Markov model for a compositional and signal search
for a gene in a sequence sampled from a bacterial genome is shown in Figure 4.3. The model is first
“trained” on sequences from the reference database and generates the probable frequencies of different
nucleotides at any given position on the query sequence to estimate the likelihood that a sequence is in
a different “state” (such as a coding region). The query sequence is predicted to be a gene if the product
of the combined probabilities across the sequence exceeds a threshold determined by probabilities
generated from sequences in the reference database.
The discussion above has presumed that biological understanding does not play a role in gene
recognition. This is often untrue—gene-recognition algorithms make errors of omission and commis-
sion when run against genomic sequences in the absence of experimental biological data. That is, they
fail to recognize genes that are present, or misidentify starts or stops of genes, or mistakenly insert or
delete segments of DNA into the putative genes. Improvements in algorithm design will help to reduce
these difficulties, but all the evidence to date shows that knowledge of some of the underlying science
helps even more to identify genes properly.^103
(^99) G. Manning, D.B. Whyte, R. Martinez, T. Hunter, and S. Sudarsanam, “The Protein Kinase Complement of the Human
Genome,” Science 298(5600):1912-1934, 2002.
(^100) I. Dunham, N. Shimizu, B.A. Roe, S. Chissoe, A.R. Hunt, J.E. Collins, R. Bruskiewich, et al. “The DNA Sequence of Human
Chromosome 22,” Nature 402(6761):489-495, 1999.
(^101) J.M. Claverie, “Computational Methods for the Identification of Genes in Vertebrate Genomic Sequences,” Human Molecular
Genetics 6(10):1735-1744, 1999.
(^102) I. Dunham, N. Shimizu, B.A. Roe, S. Chissoe, A.R. Hunt, J.E. Collins, R. Bruskiewich, et al., “The DNA Sequence of Human
Chromosome 22,” Nature 402(6761):489-495, 1999.
(^103) This discussion is further complicated by the fact that there is no scientific consensus on the definition of a gene. Robert
Robbins (Vice President for Information Technology at the Fred Hutchinson Cancer Research Center in Seattle, Washington, per-
sonal communication, December 2003) relates the following story: “Several times, I’ve experienced a situation where something like
the following happens. First, you get biologists to agree on the definition of a gene so that a computer could analyze perfect data
and tell you how many genes are present in a region. Then you apply the definition to a fairly complex region of DNA to determine
the number of genes (let’s say the result is 11). Then, you show the results to the biologists who provided the rules and you say,
‘According to your definition of a gene there are eleven genes present in this region.’ The biologists respond, ‘No, there are just
three. But they are related in a very complicated way.’ When you then ask for a revised version of the rules that would provide a
result of three in the present example, they respond, ‘No, the rules I gave you are fine.’” In short, Robbins argues with considerable
persuasion that if biologists armed with perfect knowledge and with their own definition of a gene cannot produce rules that will
always identify how many genes are present in a region of DNA, computers have no chance of doing so.