The problem that we wish to address in this book is that of predicting computationally the one-dimensional structure of eukaryotic protein-coding genes. Our first order of business will be to define this problem more precisely, and to circumscribe the issue so as to reflect the set of assumptions and constraints which typically apply in the case of practical gene-finding systems. As we recognize that not all readers will be familiar with the relevant facts and theories from molecular biology, we begin with the so-called central dogma of molecular biology, in which the significance of genes and their genomic structure are defined in relation to current biological understanding and the goals of modern medicine.

The central dogma of molecular biology

Life on Earth began approximately 3.5 billion years ago, and since that time it has advanced through a number of stages of increasing complexity. Beginning with the first replicating molecules and unicellular organisms, our own evolutionary trajectory has taken us along an epic journey progressing from microscopic invertebrates to bony fishes, to the amphibians and reptiles who first established the vertebrate kingdom on dry land, to the basal mammals who hid from the dinosaurs among the primitive trees and bushes of the Mesozoic era, and then on to our closest living relatives, the great apes. Through all that time, one fact has remained constant: that our animal selves, both physically and cognitively (with the latter following, of course, the advent of that organ which we call the brain) have been extensively shaped by the action of our genes, through their influence both on our bodily development (our ontogeny) and also on our ongoing biological processes, both of which are overwhelmingly mediated through the action of proteins, the primarily biochemical products of gene expression.

In this chapter we will construct a “toy” exon finder for a trivial genome, using mostly ad hoc techniques. While the level of computational sophistication and rigor will contrast starkly with that of later chapters, the purpose here will be to develop some intuition for the more salient aspects of the statistical structure of genes. Source code and sequence files for the examples in this chapter can be obtained through the book's website (see Appendix). The genome that we will be using is that of the fictional organism Genomicus simplicans. We begin by describing some of the features of this toy genome.

The toy genome and its toy genes

The G. simplicans genome has several distinguishing characteristics which make it suitable for illustrating the basic gene-finding problem:

• The genome is very dense with genes, with typically no more than 20 bp between successive genes on a chromosome.

• The exons within each gene tend to be very small, on the order of 20 bp.

• The introns within multi-exon genes tend to be very short, on the order of 20 bp.

• The exons incorporate fairly strong codon biases as well as a significant {G,C} bias, and the splice sites and start and stop codons are flanked by positions with fairly strong base composition biases.

• The codon usage statistics and base composition biases near splice sites and start and stop codons have been well characterized through extensive experimental work.

• Genes occur only on one strand (which we will arbitrarily call the forward strand).

In this chapter we will develop a conceptual framework describing the gene prediction problem from a computational perspective. Our goal will be to expose the reader to the overall problem from a high level, but in a very concrete way, so that the necessities and compromises of the computational methods which we will introduce in the chapters ahead can be seen in light of the practical realities of the problem. A comparison of the material in this chapter with the description of the underlying biology given in Chapter 1 should highlight the gulf which yet needs to be crossed between the goals of genome annotation and the current state of the art in computational gene prediction.

Genes, exons, and coding segments

The common substrate for gene finding is the DNA sequence produced by the genome sequencing and assembly processes. As described in Chapter 1, the raw trace files produced by the sequencing machines are subjected to a base-caller program which infers the most likely nucleotide at each position in a fragment, given the levels of the fluorescent dyes measured by the sequencing machine. The nucleotide sequence fragments produced by the base-caller are then fed to an assembler, a program that combines fragments into longer DNA sequences called contigs. Contigs are generally stored in FASTA files. Figure 3.1 shows an example FASTA file.

Before we begin our exploration of the various gene-finding strategies, we need to establish a set of methods for assessing and comparing the predictive accuracy of gene finders. The two main issues that must be addressed are: (1) the experimental protocol for obtaining a set of predictions for evaluation, including the collection, filtering, and preprocessing of a suitable set of test genes, and (2) the actual evaluation metrics and their computation. The importance of obtaining an objective assessment of gene finder accuracy should not be underestimated; the publication of flawed evaluations and comparative studies can effect a significant disservice to the field by reducing interest in what might otherwise be fruitful areas of inquiry or by fostering the additional expenditure of resources on methods having no real merit. For this reason, we consider this topic to be as important as that of the actual prediction methods employed.

Testing protocols

Although computational gene predictions can be utilized in a number of different ways by manual and automatic genome annotation efforts, it is arguably the case that the application of greatest practical significance for ab initio gene finders is the detection of functional genes which have not yet been discovered through other means. An obvious implication of this is that the greatest value of a gene finder comes from its ability to recognize even those genes that were not presented as examples to the gene finder during training.

The most promising of current methods for computational gene prediction are those that utilize comparative information by incorporating evidence from the genomes of one or more additional organisms, or from expression data such as ESTs or proteins, or even by comparing and combining the predictions of other gene-finding systems (Guigó et al., 2006). In this chapter we review the various comparative methods which have been successfully employed to improve gene-finding accuracy, as well as several emerging techniques at the forefront of current gene-finding research.

In Figure 9.1 we summarize the major approaches to comparative gene finding that have been applied to date, and that we will be considering shortly. As it may be argued that all scientific and engineering endeavors tend to advance in an evolutionary manner – i.e., by modifying an existing theory or method so as to obtain an incremental improvement in descriptive, predictive, or manipulative power – we draw attention to the similarity of Figure 9.1 to a phylogeny or family tree (section 1.2), in which case we can view the paths through the figure as evolutionary lineages – whether lineages of software, or of ideas embedded in software. Furthermore, as it is certainly the case that comparative methods are at this point in time still evolving, the following exposition will necessarily be less dogmatic than our descriptions of ab initio methods given in the foregoing chapters, relying to a correspondingly greater degree on the presentation of case studies to illustrate the various methods that have been put forth.

Quite a few of the techniques described in the foregoing chapters could be said to qualify as machine-learning methods. In this chapter we consider a number of other popular machine-learning algorithms and models which either have seen limited use in gene finding, or would seem to offer possible avenues for future investigation in this arena. Most of the methods which we describe are relatively easy to implement in software, and nearly all are available in open-source implementations (see Appendix). While the current emphasis in the field of gene prediction seems to be on Markovian systems (in one form or another), an expanded role for other predictive techniques in the future is not inconceivable.

Overview of automatic classification

Perhaps the most typical setting for machine-learning applications is that of N-way classification (Figure 10.1). In this setting, a test case (i.e., a novel object) is presented to a classifier for assignment to one of a fixed number of discrete categories. The test case is typically encoded as a vector of real-valued or integer-valued attributes (i.e., random variables – section 2.6), though since we will generally treat all attributes as being real-valued; thus the attributes of a single test case are drawn from, for some integer m. The categories to which test cases are to be mapped are typically encoded as integer values in the range.

In this chapter we describe a number of heuristics which we have found useful during the implementation, training, and/or deployment of practical gene finding systems for real genome annotation tasks.

Boosting

A well-known trick from the field of machine learning is boosting. This technique has been applied to the training of gene finders in the following way, with modest accuracy improvements being observed in a number of cases.

Suppose that while training a signal sensor for a GHMM-based gene finder we notice that a number of positive examples are assigned relatively poor scores by the newly trained sensor. One approach to boosting involves duplicating these examples in the training set and then re-training the sensor from scratch. The duplicated, low-scoring examples will now have a greater impact on the parameter estimation process due to their being present multiple times in the training set, so that the re-trained sensor is more likely to assign a higher score to those examples. Assuming that the low-scoring examples are not mislabeled training features, improvements to the accuracy of the resulting gene finder might be expected when the gene finder is later deployed on sequences having genes with similar characteristics to the duplicated examples. Care must be taken to avoid overtraining, however. To the extent that a gene finder with optimal genome-wide accuracy is desired, it is important that boosting not be allowed to bias the gene finder in way that is significantly inconsistent with the actual frequency of these difficult signals in the genome.

The human genome sweepstakes

In May of 2003 it was announced that Lee Rowen of the Institute for Systems Biology in Seattle, Washington was the winner of GeneSweep, an informal betting pool on the number of genes contained in the human genome. Rowen's guess of 25,947 won her half of the $1200 pool and a signed copy of James Watson's book, The Double Helix. GeneSweep had been created in 2000 by Ewan Birney of the European Bioinformatics Institute just as large pieces of the genome were being completed; because of the increasing amount of sequence becoming available, the cost of bets rose from $1 in 2000, to $5 in 2001, to $20 in 2002. One of the most surprising things about Rowen's winning guess was that it was almost certainly 3,000 genes off the mark – above the true number of genes! Researchers had placed wagers on figures as high as 300,000 genes, with only three sub-30,000 guesses. This number of genes put humans below the two plants that have been sequenced and barely above the worm, C. elegans.

• Genes and proteins

• Gene finding and sequences

• Statistical hypothesis testing

Though the draft sequence of the human genome was published in 2001, nailing down exactly how many genes it contained turned out to be a tricky proposition.

Outbreak

On February 28, 2003 the Vietnam French Hospital of Hanoi, a private hospital with only 60 beds, called the World Health Organization (WHO) with a report of patients who had unusual influenza-like symptoms. Hospital officials had seen an avian influenza virus pass through the region a few years earlier and suspected a similar virus. The pathogen seemed highly contagious and highly virulent, so they asked that someone from the WHO be sent to investigate. Dr. Carlo Urbani, an Italian specialist in infectious diseases, responded.

• Phylogenetic trees

• The neighbor-joining algorithm

• The Newick format for representing trees

Dr. Urbani quickly determined that the Vietnamese hospital was facing a new and unusual pathogen. The infections he observed were characterized by a fever, dry cough, shortness of breath, and progressively worsening respiratory problems. Death from respiratory failure occurred in a significant fraction of the infected patients. For the next several days, Dr. Urbani worked at the hospital documenting findings, collecting samples, and organizing patient quarantine. He was the first person to identify and describe the new disease, called Severe Acute Respiratory Syndrome, or SARS. In a matter of weeks, Dr. Urbani and five other healthcare professionals from the hospital would be dead.

By March 15 the WHO had already issued a global alert, calling SARS a “worldwide health threat.” They warned that possible cases had been identified in Canada, Indonesia, Philippines, Singapore, Thailand, and Vietnam.

The physicist Richard Feynman is credited with jump-starting the field of nanotechnology. In a talk at Caltech in December 1959, Feynman issued a famous challenge: he would pay $1000 to anyone who could write the entire Encyclopedia Britannica on the head of a pin. Feynman calculated that the size of the area was approximately 1/16 of an inch across (about 1.6 × 10−3 meters), and that in order to fit all 42 million letters of the Encyclopedia one would have to make each letter 1.0 × 10−8 meters across. It took (only) 26 years before the prize was finally claimed by a graduate student at Stanford University.

• How cells work

• What is a genome

• The computational future of biology

• A roadmap to this book

Now, consider the problem of having to write out the entire set of instructions needed to build and operate a human, and consider having to do so in each of the trillions of cells in the body. The entire human genome is 3.5 billion “letters” long, and each cell is only 2 microns (2 × 10−7 meters) across. (Actually, two complete copies of the genome are present in each cell, so we have to fit a bit more than 7 billion letters.) However all the organisms on earth overcome these packaging problems to live and prosper in a wide range of environments.

In the same 1959 lecture Feynman also imagined being able to look inside a cell in order to read all of the instructions and history contained within a genome.

A mysterious disease

In the spring of 1979 the Centers for Disease Control in the United States received reports of an unknown disease that affected young men and produced a wide range of symptoms, including rare forms of cancer. In 1981 the disease was named Acquired Immune Deficiency Syndrome (AIDS). It was recognized that transmission of this disease was largely sexual, but it was not until 1983 that the infectious agent – Human Immunodeficiency Virus (HIV) – was “simultaneously” identified by labs in France and the US (the sordid story of this inter-continental competition has been the subject of multiple books). Since the first cases were identified, 20 million people have died from AIDS worldwide.

• The neutral theory of evolution

• Substitution rates

• KA/KS: quantifying the amount of selection on a sequence

At present there is no known cure for this disease and no effective vaccine against HIV infection. Large parts of the world are now facing an AIDS epidemic, with some African nations counting more than 60% of their population among the affected. Although methods exist to keep the virus in check, the high cost of these treatments means that most infected individuals in the developing world will die from AIDS. Indeed, this disease has now surpassed malaria as the number one killer in Africa.

Various aspects of the AIDS epidemic have caught scientists by surprise, including its sudden appearance, mysterious origin, and the difficulty in finding a cure or vaccine.

Uninvited guests

Every human being has multiple species of bacteria living within them. Most of these bacteria, such as E. coli, are not harmful to us and are considered beneficial symbionts. The bacteria help us to digest certain foods or supply us with vitamins that we cannot make on our own, and we provide them with the nutrients and environment they need to survive. The benefits of having bacterial symbionts extend beyond the production of necessary chemicals. These bacteria actually prevent infection by other pathogenic bacteria simply by virtue of having already established their presence in our gut. In fact, after taking a course of antibiotics it is often recommended that people eat foods like yogurt to re-populate their stomach and intestines with symbiotic bacteria.

• Genome rearrangements

• Orthology and paralogy

• Synteny blocks, inversions, and transpositions

Although there are many well-known examples of beneficial symbiotic relationships in nature, they tend to be interactions between free-living organisms such as bees and flowers or birds and rhinoceros (the appropriately named tick-bird eats ticks off the back of the rhino). As with our relationship with E. coli, however, there are many symbionts that are hidden from view because they live within their hosts. These symbionts often aid their hosts in digestion and benefit themselves by living in the stomach of a mobile organism. For instance, termites have specific protozoa (a type of single-celled eukaryote) living in their digestive tract to help with the digestion of wood.