Genomic era, year zero

In 1995 a group of scientists led by Craig Venter, at The Institute for Genomic Research (TIGR) in Maryland, published a landmark paper in the journal Science. This paper reported the complete DNA sequence (the genome) of a free-living organism, the bacterium Haemophilus influenzae (or H. influenzae, for short). Up until that moment, only small viral genomes or small parts of other genomes had been sequenced. The first viral genome sequence (that of phage phiX174) was produced by Fred Sanger's group in 1978, followed a few years later by the sequence of human mitochondrial DNA by the same group. Sanger – working in Cambridge, UK – was awarded two Nobel prizes, the first one in 1958 for developing protein sequencing techniques and the second one in 1980 for developing DNA sequencing techniques. A bacterial sequence, however, is enormously larger than a viral one, making the H. influenzae paper a true milestone. Given the order of magnitude increase in genome size that was sequenced by the group at TIGR, the genomic era can be said to have started in 1995.

• Genomes and genomic sequences

• Probabilistic models of sequences

• Statistical properties of sequences

• Standard data formats and databases

A few months later the same group at TIGR published an analysis of the full genome of another bacterium, Mycoplasma genitalium – a microbe responsible for urethritis – and shortly thereafter the sequence of the first eukaryote, the fungus, Saccharomyces cerevisiae (or S. cerevisiae, baker's yeast) was published by other groups.

Chateau Hajji Feruz Tepe

In 1985 the world's most expensive bottle of wine was sold at auction for $160,000. This bottle of 1787 Chateau Lafite came from the cellar of Thomas Jefferson (third president of the United States) and was apparently purchased during his time as ambassador to France. While Jefferson's Bordeaux is undoubtedly an historic artifact (and probably undrinkable), the oldest bottle of wine dates to 5000 BC from the site of Hajji Feruz Tepe in Iran. This 9-liter clay pot did not contain any liquid when found, but still had dried residue from the wine it once held.

• Gene expression data

• Types of DNA microarrays

• Data clustering and visualization

• Expression during the cell Cycle

The recipe for making wine and other fermented beverages has not changed much in the past 7000 years. A solution rich in sugars (usually fruit juice) is turned into the alcoholic nectar we consume by exploiting a remarkable organism: the yeast, Saccharomyces cerevisiae. This unicellular fungus extracts energy from the environment by fermenting sugars, a process which produces alcohol as a by-product. Because S. cerevisiae is found naturally on grapevines, wine making is as easy as crushing grapes and putting them into a tightly sealed container for a few months. During this time yeast transforms the sugars contained in grape juice into alcohol, and this is why your wine is so much less sweet (and more alcoholic) than the grape juice it started from.

Mathematical algorithms, though usually invisible, are all around us. The microcomputer in your car controlling the fuel ignition uses a control algorithm embodying mathematical theories of dynamical systems; a Web search engine might use large-scale matrix computations; a “smart map” using a Global Positioning System to tell where you are and the best way to get home embodies numerous numerical and non-numerical algorithms; the design of modern aircraft involves simulating the aerodynamic and structural characteristics on powerful computers including supercomputers.

Behind these applications is software that does numerical computations. Often it is called scientific software, or engineering software; this software uses finite-precision floating-point (and occasionally fixed-point) numbers to represent continuous quantities.

If you are involved in writing software that does numerical computations, this book is for you. In it we try to provide tools for writing effective and efficient numerical software. If you are a numerical analyst, this book may open your eyes to software issues and techniques that are new to you. If you are a programmer, this book will explain pitfalls to avoid with floating-point arithmetic and how to get good performance without losing modern design techniques (or programming in Fortran 66). People in other areas with computing projects that involve significant numerical computation can find a bounty of useful information and techniques in this book.

But this is not a book of numerical recipes, or even a textbook for numerical analysis (numerical analysis being the study of mathematical algorithms and their behavior with finite precision floating-point arithmetic or other sources of computational errors). Nor is it a handbook on software development. It is about the development of a particular kind of software: numerical software.

In this section we remind our readers of a number of things that are important to understand when developing scientific software. The first is how a Central Processing Unit (CPU) works. This is particularly important for getting the maximum performance out of your computer. The second is how variables are stored in memory. This is important not only for the performance of your code, but also whether it runs correctly or not. The third is what compilers, linkers, loaders and interpreters do to the code you write when they turn it into a program that actually runs on your computer. This is particularly important for people who write libraries of routines; these days that includes most programmers.

In this section we will not deal with the most advanced aspects of programming for performance. That will come in the next chapter.

Under the hood: what a CPU does

A CPU is the hardware that does the actual processing. The other hardware that makes up a computer – memory, input and output devices (keyboard, mouse, network connector, display, disk drives), support hardware – are there mainly to support the operations of the CPU.

So what does a CPU actually do? At the bottom level it is an electrical circuit containing many transistors, which we can consider to be electrically controlled switches carrying out logical operations (“and”, “or”, and “not”). The circuits form sub-systems of the CPU, as illustrated in Figure 6.1. Inside the CPU are a number of fast registers to store temporary data which are going to be operated on. The part of the CPU that does the actual computation is called the Arithmetic-Logic Unit (ALU).

Numerical software is the software used to do computations with real numbers; that is, with numbers with decimal points in them like π = 3.141 5926. … These kinds computations are commonly of great scientific and engineering importance. Real numbers can be used to represent physical quantities (position, height, force, stress, viscosity, voltage, density, etc.). Computation with real numbers can be for simulating the nuclear processes in the centers of stars, finding the stresses in a large concrete and steel structure, or for determining how many spheres of unit radius can touch each other without penetrating. This kind of software is about quantitative problems. That is, the answers to our questions are not simple yes/no or red/green/blue answers. They involve continuously varying quantities. But computers can only store a finite number of values. So we have to use an approximation to real numbers called floating point numbers (described in Chapter 2).

Numerical software is often used for large-scale problems. That is, the number of quantities that need to be computed is often very large. This happens because we want to understand what is happening with a continuously varying quantity, such as stress in a structural column, or flow in a river. These are quantities that vary continuously with position, and perhaps with time as well. Since we cannot find or store the values at all infinitely many points in a column or a river, we must use some sort of discretization. Discretizations are approximations to the true system, which are usually more accurate when more refined. Refining a discretization means that we create more quantities to compute.

Software engineering

Software engineering is about the task of designing and implementing software. It is not about the specific algorithms or techniques to be programmed, but about how to organize both the software and the people who develop it. While many programmers have the attitude “Just do it!” and can cope with small programs just fine, large programs and, indeed, any programs that you expect other people to use, need careful attention and design.

There are many other books available to help programmers be more effective at their work. One of the first such books is The Mythical Man-Month [17], which is justifiably famous for its advice on avoiding software disasters. A book that many have found invaluable is Elements of Programming Style [65]. Recent books of this kind include books on trends such as Extreme Programming like [21], and The Pragmatic Programmer [58]. Many contain a great deal of wisdom, and have been written with considerable and deep experience. They usually generate a great deal of lively controversy. One of the especially good features of these books, as opposed to textbooks on software engineering such as [86], is their emphasis on practical aspects of programming and the words of experience with large systems and difficult situations.

Software life-cycle

Software is eternal. Once a program is written in a specific programming language, it is a valid program in that language and when compiled and executed will do essentially the same thing now and forever. Yet our software is ever-changing. Microsoft comes out with new versions of its operating system every few years, and sends out patches on a weekly basis.

Let's get this straight. Your priorities in writing scientific software should be, roughly speaking:

• correctness,

• numerical stability,

• accurate discretization (including estimating accuracy),

• flexibility,

• efficiency (speed and memory).

If your program is not correct, then nothing else matters. If the algorithm is not numerically stable, the results cannot be trusted (at least not unless you test them first). If the discretization or other approximations used are inaccurate we will still not be able to trust the results. Even better is to have a method that can estimate the errors in the discretization and approximations. The estimates don't have to be exact (if they were, we could compute the exact values), but good enough to give a reasonable idea of their size.

If the software is not flexible, then others probably won't use it, since they will have a hard time making it do something slightly different. Once we have a correct implementation of a numerically stable algorithm, then we can think about how to make it fast. Speed is still one of our priorities, but it comes last. Don't forget memory. If your algorithm needs more memory than your machine has, then it won't run. And sometimes this is more important than speed.

Correctness

Without correctness, we really can't expect any useful results. So we must first make sure that our programs bug-free. Since human beings make errors even for the simplest tasks (and programming involves a great deal of thought), the probability that someone can write a bug-free program of any significance without debugging is close to zero.

This section is about how you should design your software so it is easy to test and debug. Bugs are inevitable. But we should try to eliminate them as quickly and thoroughly as we can. To do this, we need to test the code thoroughly. The best way to do this is to automate the testing. When bugs are uncovered, the situation that revealed the bug should be added to the set of (automated) tests. When changes are made, re-do the tests. This is known as regression testing and is how many software companies ensure the quality of their software.

Memory allocation and the associated debugging issues are dealt with in Chapters 14 and 15.

Incremental testing

This is perhaps the most crucial single technique in designing for debugging. Test as you go. Make sure each piece is working correctly before you put them together. Don't try to construct a full-featured program from the beginning, but make sure that you can get a “bare bones” version going. For any feature you want to add, first devise a test for what this feature does. Then start building the feature, checking it against the test you devised. This way you can test each new addition while having confidence that the base system is behaving correctly.

The Extreme Programming approach [21] is even stronger: Before you start writing code, write the test code and data. Furthermore, you should automate the tests, and add new tests as you refine, debug, and test the code. Whenever you feel that you have things working, run the complete set of tests. This ensures that you haven't broken anything that you thought was fixed.