The idea behind this book developed in late 2004–early 2005 while I was working on two unrelated projects in computational genomics. The first project involved the computational detection of small nucleolar RNAs (snoRNAs) in genome sequences. In the course of this work, I noticed – as others had, as well – that, in mammals, snoRNA genes are located within introns of protein-coding genes (so-called snoRNA host genes), which are often genes that code for ribosomal proteins. This observation led to speculation as to whether therewere additionalcommonfeatures of the introns and genes that contain snoRNAs. For example, are the host genes of homologous mammalian snoRNAs themselves homologous? Do those host genes have other shared functions beyond the fact that several of them code for ribosomal proteins? Are the introns that contain the snoRNAs consistently longer (or shorter) than the average introns found in these genes? Are the snoRNAs found at any characteristic distance from the nearest exon-intron junctions in their host gene? To answer these questions would require accessing sequence and annotation data for both the human and mouse genomes and performing some simple calculations and statistics on that data. Moreover, because therewere some200humansnoRNAs already known(and a similar number of mouse snoRNAs), performing this data acquisition and manipulation would require computer processing.

This book grew out of a number of conversations between Dr. Ian Korf and myself, in May of 2004, in which we jointly lamented the rather large number of small but important details which one is required to know when building a practical gene-finding system from scratch, and which were at that time not fully documented in the gene-finding literature. Page limits in traditional print journals invariably force authors of research reports to omit details, and although online journals have relaxed this constraint to some degree, the larger impact factors of the more venerable print journals still attract many researchers to those more constrained venues. Of course, even the online journals urge authors to be brief, so that implementation details are either relegated to supplementary online documents, or – more often than not – simply omitted entirely. Because practical gene-finding software typically consists of many thousands of lines of source code, including all the details necessary for replicating any of these programs is out of the question for any journal article. Placing one's gene finder into the public domain, or making it open source, can help to alleviate this problem, since the public is then free to peruse the source code. Of course, perusing a 30 000-line program can be tedious, to say the least, and ideally one would like a format more geared toward human consumption, in which the essential concepts have been distilled from the implementation and provided in a rigorous but accessible manner.

In this chapter we will briefly review the basic mathematical machinery and notational conventions that it will be necessary to know in order to most effectively absorb the rest of the material in this book. It will be of use primarily to those lacking a strong computational background. We assume only that the reader has knowledge of algebra and has at least some minimal facility with a structured programming language. In section 2.4 we will summarize the syntax and semantics of the pseudocode which we will be using when describing algorithms, and which should be largely intuitive to anyone familiar with a modern programming language such as C/C++, Java, Perl, or Pascal.

The sections that follow will be, we believe, appropriately brief; readers requiring further elaboration of any of the topics in this chapter are encouraged to pursue the cited references. Conversely, readers with a strong computational background may skim this chapter, noting only the typographical conventions that we have opted to employ.

Numbers and functions

A number of standard constants and functions will be utilized in the chapters ahead. The two infinities, ∞ and -∞, should be familiar enough; we will use them to denote the largest and smallest values, respectively, that can be represented in a particular computer system. As computer architectures advance, these respective values may grow, and so it is advisable when writing a gene finder to use an appropriate portable means of referring to these values in source code.

When Frederick Sanger sequenced the very first genome – the bacteriophage ϕ-X174 – in 1977, it was clear that DNA sequencing offered a dramatically faster way to find genes than earlier, traditional mapping methods. The small phage genome spans just 5386 bases, about 95% of which is used to encode 11 genes. For this and other viruses, gene finding is fast and easy: the proteins are encoded virtually end-to-end, sometimes even overlapping one another. The early days of DNA sequencing proceeded slowly but with great excitement, as the new technology was applied to small fragments of DNA from many different species. By the mid-1980s, scientists were attempting to automate the sequencing process, which soon led to larger sequencing projects, and in 1989 the Human Genome Project was launched, with the ambitious goal of sequencing the entire 3 billion base pairs of the 24 human chromosomes over the course of the next 15 years. In 1995 a team at The Institute for Genomic Research (TIGR) sequenced the first genome of a free-living organism, the bacterium Haemophilus influenzae, which at 1.8 million base pairs was considerably larger than any genome that had been sequenced before. The H. influenzae genome was the beginning of an enormous outpouring of DNA sequences, fueled by ever-lower sequencing costs and an ever-increasing thirst for new discoveries, that has now produced hundreds of genomes, both large and small.

Official book website

The official website for this book is located at:

http://www.geneprediction.org/book

Here you will find sample code, sample data, links to other online resources, information about other editions of the book, supplementary chapters, errata, and other information relevant to the book. In the near future we hope to add course materials such as slides and solutions to selected exercises from the book.

Open-source gene finders

As of the current printing of this book, the following gene finders are known to be available as open-source software. Note that all open-source programs are not governed by the same license; before modifying or redistributing any of this software, you should check the licensing agreement under which a specific program is distributed. Information about specific licensing agreements can be found at the web addresses given below, or by contacting the author(s) of the specific programs.

We conclude with a brief exposition of current research topics in computational gene prediction. As these all are areas of active research in which the optimal computational methods have yet to be identified, our treatment will necessarily be provisional. It may be hoped that future revisions of this text will be able to treat these topics in a more decisive manner due to the fruits of current research.

Alternative splicing and transcription

It may reasonably be argued that most current attempts at computational gene finding – at least those based on Markov models and Viterbi decoding – are fundamentally flawed. The paradigm of gene finding, as we have formulated it, consists of computing the single optimal parse of a genomic contig, and then predicting the set of nonoverlapping gene structures present in this “optimal” parse. As briefly mentioned in section 1.4, however, it is known that most human genes are subject to the phenomenon of alternative splicing, whereby a single locus in the genome may give rise to several different mature mRNAs, and therefore (in many cases) to distinct proteins with potentially divergent biological functions. Some estimates place the incidence of alternative splicing among human loci as high as 80% (e.g., Matlin et al., 2005). Thus, the problem of alternative splicing is one of vital importance to a biological understanding of the human genome.