This chapter explores the topic of coevolution: the genetic change in one species in response to the change in another. For example, in some cases, a parasite species might evolve to specialize with its host species. In other cases, the relationship between two species may be mutually beneficial and coevolution may serve to strengthen the benefits of that relationship.

One important way to study the coevolution of species is through a computational technique called cophylogeny reconstruction. In this technique, we first obtain the evolutionary (phylogenetic) trees for the two species and then try to map one tree onto the other in the “simplest” (most parsimonious) possible way. We can then use these mappings to determine how likely it is that the two species coevolved.

This chapter begins with descriptions of several pairs of species that are believed to have coevolved: figs and the wasps that polinate them; gophers and the lice that infest them; and a bird species that “tricks” another species to tend to its young. Next, we describe the cophylogeny reconstruction problem, its computational complexity, and a technique for finding good solutions for this problem. Finally, the reader is invited to use this computational method – through a freely accessible software package called Jane – to investigate the relationships between the pairs of species described at the beginning of the chapter.

Phylogenetics seeks to deduce the pattern of relatedness between organisms by using a phylogeny or evolutionary tree. For a given set of organisms or taxa, there may be many evolutionary trees depicting how these organisms evolved from a common ancestor. As a result, consensus trees are a popular approach for summarizing the shared evolutionary relationships in a group of trees. We examine these consensus techniques by studying how the pantherine lineage of cats (clouded leopard, jaguar, leopard, lion, snow leopard, and tiger) evolved, which is hotly debated. While there are many phylogenetic resources that describe consensus trees, there is very little information regarding the underlying computational techniques (such as sorting numbers, hashing functions, and traversing trees) for building them written for biologists. The pantherine cats provide us with a small, relevant example for exploring these techniques. Our hope is that life scientists enjoy peeking under the computational hood of consensus tree construction and share their positive experiences with others in their community.

It is all in the DNA. Our genetic code, or genotype, influences much about us. Not only are physical attributes (appearance, height, weight, eye color, hair color, etc.) all fair game for genetics, but also possibly more important things such as our susceptibility to diseases, response to a certain drug, and so on. We refer to these “observable physico-chemical traits” as phenotypes. Note that “to influence” is not the same as “to determine” – other factors such as the environment one grows up in can play a role. The exact contribution of the genotype in determining a specific phenotype is a subject of much research. The best we can do today is to measure correlations between the two. Even this simpler problem has many challenges. But we are jumping ahead of ourselves. Let us review some biology.

This introduction is a brief primer on some basic computational concepts that are used throughout the book. The goal is to provide some initial intuition rather than formal definitions. The reader is referred to excellent basic books on algorithms which cover these notions in much greater rigor and depth.

In addition to point mutations, larger-scale structural changes (including rearrangements, duplications, insertions, and deletions) are also prevalent between different mammalian genomes. Capturing these large-scale changes is critical to unraveling the history of mammalian evolution in order to better understand the human genome. It also has profound biomedical significance, because many human diseases are associated with structural genomic aberrations. The increasing number of mammalian genomes being sequenced as well as recent advancement in DNA sequencing technologies are allowing us to identify these structural genomic changes with vastly greater accuracy. However, there are a considerable number of computational challenges related to these problems. In this chapter, we introduce the ancestral genome reconstruction problem, which enables us to explain the large-scale genomic changes between species in an evolutionary context. The application of these methods to within-species structural variation and disease genome analysis is also discussed. The target audience of this chapter is advanced undergraduate students in biology.

Identifying the complicated patterns of regulatory interactions that control when different genes are active in a cell is a challenging problem, but one essential to understanding how organisms function at a systems level. In this chapter, we will examine the role of computational methods in making such inferences by studying one particularly important version of this problem: the inference of genetic regulatory networks from gene expression data. We will first briefly cover some necessary background on the biology of genetic regulation and technology for measuring the activities of distinct genes in a sample. We will then work through the process of how one can abstract the biological problem of finding interactions among genes into a precise mathematical formulation suitable for computational analysis, starting from very simple variants and gradually working up to models suitable for analysis of large-scale networks. We will also briefly cover key algorithmic issues in working with such models. Finally, we will see how one can transition from simplified pedagogical models to the more detailed, realistic models used in actual research practice. In the process, we will learn about some key concepts in computer science and machine learning, consider how computational scientists think about solving a problem, and see why such thinking has come to play an essential role in the emerging field of systems biology.

Phylogenetic trees, also known as evolutionary trees, are fundamental to many problems in biological and biomedical research, including protein structure and function estimation, drug design, estimating the origins of mankind, etc. However, the estimation of a phylogeny is enormously challenging from a computational standpoint, often involving months or more of computer time in order to produce estimates of evolutionary histories. Even these month-long analyses are not guaranteed to produce accurate estimates of evolution, for a variety of reasons. In addition to the errors in phylogeny estimation produced by limited amounts of data, there is the added – and critically important – fact that all the best phylogeny estimation methods are based upon heuristics for optimization problems that are difficult to solve. Consequently, large data sets are often “solved” only approximately. In this chapter, we discuss the issues involved in phylogeny estimation, as well as the technical term from computer science, “NP-hard.”

Networks have been used to model many real-world phenomena, including biological systems. The recent explosion in biological network data has spurred research in analysis and modeling of these data sets. The expectation is that network data will be as useful as the sequence data in uncovering new biology. The definition of a network (also called a graph) is very simple: it is a set of objects, called nodes, along with pairwise relationships that link the nodes, called links or edges. Biological networks come in many different flavors, depending on the type of biological phenomenon that they model. They can model protein structure: in these networks, called protein structure networks, or residue interaction graphs (RIGs), nodes represent amino acid residues and edges exist between residues that are close in the protein crystal structure, usually within 5 Å (Figure 15.1). Also, they can model protein–protein interactions (PPls): in these networks, proteins are modeled as nodes and edges exist between pairs of nodes corresponding to proteins that can physically bind to each other (Figure 15.2a). Hence, PPI and RIG networks are naturally undirected, meaning that edge AB is the same as edge BA. When all proteins in a cell are considered, these networks are quite large, containing thousands of proteins and tens of thousands of interactions, even for model organisms. An illustration of the PPI network of baker's yeast, Saccharomyces cerevisiae, is presented in Figure 15.2b. Networks can model many other biological phenomena, including transcriptional regulation, functional associations between genes (e.g. synthetic lethality), metabolism, and neuronal synaptic connections.

From the evolutionary standpoint, DNA replication and transcription are two fundamental processes enabling reliable passage of fitness advantages through generations (in DNA form) and manifestation of these advantages (in RNA form), respectively. Paradoxically, both of these basic mechanisms not only preserve genetic information but also apparently cause systematic genomic changes directly. Here, I show how genome-scale sequence analysis can help identify such effects, estimate their relative contributions, and find practical application (e.g. for predicting replication origins). Visualization of bioinformatics results is often the best way of connecting them to the underlying biological question and I describe the process of choosing the visual representation that would help compare different organisms, genomes, and chromosomes.

The purpose of this chapter is to introduce the physical principles underlying models of the electrical activity of neurons. Starting with the neuronal cell membrane, we explore how its permeability to different ions and the maintenance by ionic pumps of concentration gradients across the membrane underpin the resting membrane potential. We show how the electrical activity of a small neuron can be represented by equivalent electrical circuits, and discuss the insights this approach gives into the time–dependent aspects of the membrane potential, as well as its limitations. It is shown that spatially extended neurons can be modelled approximately by joining together multiple compartments, each of which contains an equivalent electrical circuit. To model neurons with uniform properties, the cable equation is introduced. This gives insights into how the membrane potential varies over the spatial extent of a neuron.

So far we have been discussing how to model accurately the electrical and chemical properties of nerve cells and how these cells interact within the networks of cells forming the nervous system. The existence of the correct structure is essential for the proper functioning of the nervous system, and in this chapter we discuss modelling work that addresses the development of the structure of the nervous system. Existing models of developmental processes are usually designed to test a particular theory for neural development and so are not of such wide application as, for example, the HH model of nerve impulse propagation. We discuss several examples of specific models of neural development, at the levels of individual nerve cells and ensembles of nerve cells.