Introduction to EMBOSS

The European Molecular Biology Open Software Suite (EMBOSS) is a high-quality, well-documented package of open source software tools for molecular biology. It includes over 200 applications for molecular sequence analysis and other common tasks in bioinformatics. It integrates the core applications with a range of popular third-party software packages under a consistent and powerful command line interface. The software has many useful features; for example, it automatically copes with data in a variety of formats and allows for transparent retrieval of sequence data from the web.

EMBOSS includes extensive C programming libraries with a clean and consistent API. There is much useful inbuilt functionality, for example the handling of the command line and common file formats, making it a powerful and convenient platform to develop and release bioinformatics programs. True to the spirit of open source, EMBOSS is free of charge to all and the code is licensed for use by everyone under the GNU General Public Licenses (GPL and LGPL). No one individual or institute ‘owns’ the code, or ever will. Under the terms of the licenses, it can be downloaded via the internet, copied, customised and passed on, so long as these same freedoms are preserved for others. Contributions are strongly encouraged!

Licence information

EMBOSS is licensed for use by everyone under the GNU Software licences. The AJAX and NUCLEUS libraries are released under the GNU Lesser General Public Licence (LGPL). The applications are released under the GNU General Public Licence (GPL). If you plan to develop proprietary software using the libraries you should read the full licensing conditions:

The licences were chosen to provides maximum flexibility and encourage development. They give you freedom in software development, so long as you preserve those freedoms for others.

General Public Licence (GPL)

The GPL allows you to freely modify, copy and distribute the application source code so long as the source code of the derived work is licensed under GPL and made available. This means you can freely extend and improve the EMBOSS applications.

Introduction to EMBOSS

The European Molecular Biology Open Software Suite (EMBOSS) is a high-quality, well-documented package of open source software tools for molecular biology. It includes over 200 applications for molecular sequence analysis and other common tasks in bioinformatics. It integrates the core applications with a range of popular third-party software packages under a consistent and powerful command line interface. The software has many useful features; for example, it automatically copes with data in a variety of formats and allows for transparent retrieval of sequence data from the web.

EMBOSS includes extensive C programming libraries with a clean and consistent API. There is much useful inbuilt functionality, for example the handling of the command line and common file formats, making it a powerful and convenient platform to develop and release bioinformatics programs. True to the spirit of open source, EMBOSS is free of charge to all and the code is licensed for use by everyone under the GNU General Public Licenses (GPL and LGPL). No one individual or institute ‘owns’ the code, or ever will. Under the terms of the licenses, it can be downloaded via the internet, copied, customised and passed on, so long as these same freedoms are preserved for others. Contributions are strongly encouraged!

Summary

This manual was written with newcomers to EMBOSS in mind. You will benefit from at least a basic appreciation of molecular biology and some familiarity with UNIX and the C programming language. You should know how to open, use, save and close files using a text editor. It will also help if you’ve used the EMBOSS programs and are familiar with the command line (see the EMBOSS User’s Guide).

All of the material in the EMBOSS Guides is available on the EMBOSS website:

1. http://emboss.open-bio.org

Introduction to Jemboss

Jemboss is a graphical user interface (GUI) for the EMBOSS package. It can be configured to be a client-server GUI or run as a standalone GUI on a workstation or home PC. It is written in Java.

Jemboss as a client-server

In this mode of operation, Jemboss and EMBOSS are installed on a server machine. All the EMBOSS applications will run on this server. The server must be a UNIX machine. Other computers on the network can request a copy of the GUI from the server. The GUI is self-contained: it comprises not only the user interface but also all the communication software for contacting the server and running EMBOSS applications. The client machines can be running any operating system for which there is Java support.

The server can be configured to allow anyone to run the EMBOSS applications (non-authenticating) or require that a GUI user must have an account on the server and that a username and password is typed at the start of the GUI session (authenticating).

The Jemboss server can also be configured to communicate with clients either via standard ASCII or to use automatic encryption (SSL) for security.

Introduction to EMBASSY

The EMBASSY packages include applications with the same look and feel as EMBOSS applications, but which are kept separate from EMBOSS. This is usually because the packages are for specialised sequence analysis, or for non-sequence-based analysis, or are licensed differently from EMBOSS (i.e. non-GPL), or done so at the author’s request.

The EMBASSY packages currently include:

• PHYLIPNEW (now phylip 3.68)

• HMMERNEW

• EMNU

• ESIM4

• MEMENEW

• TOPO

• MSE

• VIENNA

In Chapter 5, we introduced splits and split networks and presented the Buneman graph as the canonical split network associated with a given set of splits. Splits can be computed from many different types of data, as we discuss in some of the following chapters. The focus of this chapter is on the problem of computing a split network N for a given set of splits S on X. We present two different approaches. The first is the convex hull algorithm that computes the Buneman graph and can be applied to any set of splits, using an exponential number of nodes and edges in the worst case [11]. It is also used in Section 9.4 to compute median networks. The second is the circular network algorithm, which can be applied to any set of circular splits and produces an outer-labeled planar network with only a quadratic number of nodes and edges [62].

Both algorithms proceed in two steps. In the first step, all trivial splits in S = {S1, …, Sm} are processed to obtain a star network consisting of a central node and one leaf per taxon. Then, in the second step, the remaining splits are inserted one by one so as to obtain the final network.

To avoid some technical complexities, in the following we will assume that S contains all n trivial splits on X = {x1, …, xn}.

In this third part of the book we present a wide range of algorithms that have been developed for computing phylogenetic networks from biological data. For many of the methods, we briefly describe an application and provide references to papers that contain more details. The material is organized by type of input, which is either splits (Chapter 7), clusters (Chapter 8), sequences (Chapter 9), distances (Chapter 10), trees (Chapter 11), triples or quartets (Chapter 12). Additionally, we address the problem of drawing phylogenetic networks (Chapter 13) and give an overview of some of the existing software for computing them (Chapter 14).

The evolutionary history of a set of species is usually described by a rooted phylogenetic tree. The concept of a rooted tree is very simple and has proved to be extremely useful in many application domains. However, the truth is rarely pure and never simple.

By definition, phylogenetic trees are well suited to represent evolutionary histories in which the main events are speciations (at the internal nodes of the tree) and descent with modification (along the edges of the tree). But such trees are less suited to model mechanisms of reticulate evolution [219], such as horizontal gene transfer, hybridization, recombination or reassortment. Moreover, mechanisms such as incomplete lineage sorting, or complicated patterns of gene duplication and loss, can lead to incompatibilities that cannot be represented on a tree. Although the analysis of individual genes or short stretches of genomic sequence often gives strong support to a phylogenetic tree, different genes or sequence segments usually support different trees.

While it is generally undisputed that bifurcating speciation events and descent with modifications are major forces of evolution, there is also a growing belief that reticulate events play an important role in the shaping of evolutionary histories, too [55, 61, 111, 173].

Horizontal gene transfer (HGT), the direct transfer of genes from one organism to another, is known to occur very frequently in the prokaryotic world, the main mechanisms being transformation, conjugation and transduction [13, 28, 189, 231].

The concept of a split plays an important role in the mathematics of phylogeny. It is motivated by the simple, but crucial, observation that every edge e in an unrooted phylogenetic tree T defines a bipartition of the underlying taxon set X into two non-empty and disjoint subsets, A and B, known as a split. The splits of an unrooted phylogenetic tree uniquely define the topology of the tree and splits are used, for example, to compare different trees or to compute consensus trees. Any set of splits that is compatible corresponds to a phylogenetic tree and so one possible way to generalize from trees to networks is to consider sets of splits that are incompatible.

Splits provide the basis of unrooted phylogenetic trees and a large class of unrooted phylogenetic networks, namely split networks, just as clusters provide the basic building blocks for rooted phylogenetic trees and networks (see Chapter 6). The foundation for the theory of split networks was laid down in a seminal paper by Bandelt and Dress [9].

Overview

Figure 5.1 shows the relationships between some of the main concepts introduced in this chapter. The focus is on splits, and on split networks as an important type of unrooted phylogenetic networks. We compare splits to clusters, since the two concepts are closely related to each other. We describe the Buneman graph construction that provides a canonical split network for an arbitrary set of splits. We shall see that splits can be compatible, circular or weakly compatible.

In this chapter, we present some methods for computing phylogenetic networks from clusters. Clusters, as opposed to splits, are inherently rooted and this explains why all methods presented in this chapter produce rooted phylogenetic networks. We first briefly mention the cluster-popping algorithm for computing a cluster network, and then present a divide-and-conquer approach for computing rooted phylogenetic networks. Based on this, we discuss how to compute minimum galled trees, galled networks and level-k networks from clusters.

Cluster networks

In Chapter 6, we introduced the concept of a cluster network, which is a rooted phylogenetic network that represents a set of clusters in the hardwired sense. In such a network, every tree edge represents exactly one cluster, which is defined as the set of taxa that label nodes below that edge. Given a set of clusters C on X, the cluster network N that represents C can be efficiently computed using the cluster-popping algorithm presented in Section 6.4. This algorithm is implemented in the Dendroscope program and there it can be used to compute a cluster network from the set of clusters associated with a collection of rooted phylogenetic trees [121].

Application

A typical application of a cluster network is that one is given multiple rooted gene trees for a set of species and one would like to produce a network to illustrate the parts of the phylogeny upon which the trees agree and which parts are resolved in different ways.