Non-model distances in phylogenetics

Bioinformatics is sometimes divorced from biology. This happens when the ideas involved are solely computational ones, and are not biologically motivated. For example, Otu et al. (2003), when proposing "a new sequence distance measure for phylogenetic tree construction" point out that "it is worth noting that our distance measures do not use any evolutionary model". They seem to see this a a Good Thing whereas biologists might not.

Pairwise distances are actually a good case in point, because there are many ways to measure the similarity / distance between any two objects, and most of them have nothing whatever to do with biology. One method that was popular about 10 years ago was using computerized compression.

This is based on the notion of complexity — all objects are complex to one degree or another, but the information they contain can often be reduced (or compressed) to a smaller amount without losing anything essential. That is, the original information can be exactly reproduced from the compressed version. This notion is applied to computer files, for example, in the idea of zipping a file — depending on the file's content it may be possible to zip the file to much a smaller size for storage or transmission.

This idea is straightforward to apply to similarity (Cilibrasi & Vitányi 2005). One simply has to compress the two objects separately as well as compress the combination of the two objects (ie. their union or concatenation). If the two objects are identical then the compression of their union will be the same size as the compression of each object individually (= a distance of 0), because all of the information in one of the objects is redundant. If they have nothing in common then the compression of their union will be the sum of the sizes of the compression of each object individually (= a distance of 1).

This idea has been applied in a number of areas where similarity / distance is used to group objects together (ie. clustering or classification), including computer viruses (Wehner 2008), music (Cilibrasi et al. 2004), languages (Benedetto et al. 2002a), and genomics (Chen et al. 2000, Li et al. 2001, Otu et al. 2003).

This approach has not always been received with equanimity. For example, the paper by Benedetto et al. (2002a) has received considerable commentary (Khmelev & Teahan 2003a; Benedetto et al. 2003; Khmelev & Teahan 2003b), (Goodman 2002; Benedetto et al. 2002b), (Wang 2009).

In biology, this idea has been mostly ignored. Chen et al. (2000) and Li et al. (2001) based their idea of information on Kolmogorov complexity, which is "the shortest program on a universal computer that outputs one of the objects when the input is the other object". This complexity cannot be measured directly, and so it is approximated by using a file compression program (eg. gzip). Clearly, the approximation can only be as good as the compression program and its algorithms.

Otu et al. (2003) based their idea of information on Lempel & Ziv complexity, which is "related to the number of steps required by a production process that builds either of the two objects". They claim an exact solution to the measurement of this complexity for gene sequences, and propose several slightly different distances based on this. Furthermore, the claim to:

show that the proposed distance measures, which are based on the relative complexity between sequences imply the evolutionary distance between organisms ... As the proposed approach does not depend on multiple alignments we test the validity of the approach in two ways: we use simulated data to show that the proposed distance measures can reasonably be represented by a tree. We also show the superiority of the proposed method on existing techniques using this simulated data. Secondly, we look at how well the results generated by the proposed method agree with existing phylogenies.

The use of generic compression similarity simply demonstrates that phylogeny does produce similarity to some extent. However, phylogeny is based on what we might call a form of "special similarity", which is similarity solely due to the possession of shared derived character states. Other components of similarity, such as the similarity produced by parallelisms, convergences and reversals, do not contribute to an estimate of a phylogeny. Indeed, they will often be positively misleading. A general concept of similarity is inadequate for reconstructing a phylogeny except under the simplest circumstances. This was empirically demonstrated, for example, in liguistics by the results of the Computer-Assisted Stemmatology Challenge, in which the compression method CompLearn came dead last in the primary ranking of the different phylogenetic methods (but did okay in the secondary ranking).

In short, only some aspects of complexity are relevant for phylogenetics, and only some of the information contained in a genome is relevant for measuring phylogenetic similarity. The focus on information as a whole ignores the "bio" in bioinformatics.

References

Benedetto D, Caglioti E, Loreto V (2002a) Language trees and zipping. Physical Review Letters 88: 048702. [arXiv:cond-mat/0108530, 2001]

Benedetto D, Caglioti E, Loreto V (2002b) On J. Goodman’s comment to "Language trees and zipping". arXiv:cond-mat/0203275

Benedetto D, Caglioti E, Loreto V (2003) A reply to the comment by Khmelev and Teahan. Physical Review Letters 90: 089804.

Chen X, Kwong S, Li M (2000) A compression algorithm for DNA sequences and its applications in genome comparison. Proceedings of the Fourth Annual International Conference on Computational Molecular Biology (RECOMB), pp. 107-117. ACM Press, Tokyo.

Cilibrasi R, Vitányi PMB (2005) Clustering by compression. IEEE Transactions on Information Theory 51: 1523-1545.

Cilibrasi R, Vitányi P, de Wolf R (2004) Algorithmic clustering of music based on string compression. Computer Music Journal 28(4): 49-67.

Goodman J (2002) Extended comment on "Language trees and zipping". arXiv:cond-mat/0202383

Khmelev DV, Teahan WJ (2003a) Comment on "Language trees and zipping". Physical Review Letters 90: 089803.

Khmelev DV, Teahan WJ (2003b) Comment on the reply of Benedetto et al. arXiv:cond-mat/0303261

Li M, Badger JH, Chen X, Kwong S, Kearney P, Zhang H (2001) An information-based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics 17: 149-154.

Otu HH, Sayood K (2003) A new sequence distance measure for phylogenetic tree construction. Bioinformatics 19: 2122-2130.

Wang X-L (2009) Comment on "Language trees and zipping". arXiv:0903.3669

Wehner S (2008) Analyzing worms and network traffic using compression. Journal of Computer Security 15: 303-320. (arXiv:cs/0504045v1, 2007)

Using constraints to get a handle on the space of phylogenetic networks?

The following two problems will be familiar to researchers working on evolutionary phylogenetic networks.

1) The severe computational intractability associated with globally optimizing most objective functions over the space of phylogenetic networks.

2) The fact that within the space of potential solutions, there are typically very many that an end-user biologist will want to exclude from consideration, for context-specific biological reasons that the software does not know about. This hidden information often only becomes available at the end of the analysis. It is not unusual to receive comments such as: "Thanks for the networks but they can't be good, because experimentalists strongly believe that taxon X is a hybrid of taxa Y and Z, and we also think that taxon group C should be monophyletic ... this is not visible in your networks."

In a recent opinion piece added to the Arxiv ("Fighting network space: it is time for an SQL-type language to filter phylogenetic networks") myself, David and Simone Linz pose the question of whether it might be possible to address both these questions at the same time, using constraint-based modelling. The core of the idea is that, via some kind of comparatively easy-to-use modelling language (e.g. something with an SQL flavour), the end-user biologist should be able to specify characteristics that all candidate solutions must (or must not) have.

The win-win scenario would be that this (a) tempers the intractability of the search problem, by cutting out large swathes of irrelevant networks in the vast search space and (b) invites biologists to incorporate their context-specific knowledge "upstream", reducing the risk that the networks generated by the software are mis-interpreted. In the context of phylogenetic trees, the idea is not new: in 1986 Constantinescu and Sankoff showed that the use of a constrained tree indeed reduces the search space remarkably.

It seems a natural idea to do this for networks, but the question of course is how feasible all this is. Constraint-based pruning of intractable search spaces is seductive but technically challenging for all kinds of reasons. Depending on the constraints used it might help a lot or a little, it is certainly no silver bullet. We might nevertheless hope that in many cases end-user biologists have so much implicit knowledge that the search space is massively shrunk. The question of the modelling language is also tricky because we need to decide upon a set of network constraints that biologists want and need: the dominant topological feature of trees, the clade, is no longer sufficient to describe (or constrain) the topologically richer space of phylogenetic networks. Furthermore, the constraints themselves should not become a new source of intractability.

In the opinion piece we make a few basic suggestions for atomic network constraints and how they might be combined via an SQL-style language. This, of course, is only the starting point for what we hope will be a wider discussion.

We're very keen to hear your thoughts about this!

An open question about computational complexity

This is a guest blog post by:

Jesper Jansson

Laboratory of Mathematical Bioinformatics, Kyoto University, Japan

Here is an open problem for people interested in computational complexity issues related to phylogenetic networks.

In a recent paper we introduced a parameter called the "minimum spread" that measures a kind of structural complexity of phylogenetic networks:
T. Asano, J. Jansson, K. Sadakane, R. Uehara, G. Valiente (2012) Faster computation of the Robinson-Foulds distance between phylogenetic networks. Information Sciences 197: 77-90.

The definition is as follows:

• The "minimum spread" of a rooted phylogenetic network N is the smallest integer x such that the leaves of N can be relabeled by distinct positive integers in a way that at every node u in N, the set of all leaf descendants of u forms at most x consecutive intervals.

For example, any phylogenetic tree has minimum spread 1 because if we do a depth-first traversal of the tree and number the leaves in the order that they are discovered, then at each node, the set of leaf descendants corresponds to a single consecutive interval. This property was used in, for example, Day's algorithm from 1985 for comparing phylogenetic trees and constructing a strict consensus tree.

Similarly, any level-k phylogenetic network has minimum spread at most k+1 (see our paper for the proof). Moreover, any "leaf-outerplanar network" has minimum spread 1, where a "leaf-outerplanar network" is a network that admits a non-crossing layout in the plane with the root (if any) and all leaves lying on the outer face. Today's existing software typically outputs such networks. So, for certain classes of phylogenetic networks, we automatically get a nice upper bound on the minimum spread.

Having a small minimum spread means that the phylogenetic network is "tree-like" in the sense that its cluster collection has a space-efficient representation. But are compact representations of the clusters in a network useful?

Well, they can be employed to compare phylogenetic networks quickly, for example when using the Robinson-Foulds distance to measure the dissimilarity between two phylogenetic networks. There may be other applications, too. On the other hand, if a phylogenetic network is "chaotic" and non-tree-like then the minimum spread will not be a helpful parameter when looking for a compact encoding of its branching information.

At this point in time, not much is known about how to compute the minimum spread efficiently. As an example, consider the class of level-k networks for any fixed k > 1. According to Lemma 6 in our paper, we can always find a leaf relabeling function that yields spread at most k+1 in linear time, but that might not be the minimum possible for some particular level-k network.

As observed by Sylvain Guillemot and Philippe Gambette (independently of each other), a related result for the k-Consecutive Ones Problem implies that computing the minimum spread of an arbitrary phylogenetic network is NP-hard in the general case, although we can expect it to be easier when restricted to special cases:
P. W. Goldberg, M. C. Golumbic, H. Kaplan, R. Shamir (1995) Four strikes against physical mapping of DNA. Journal of Computational Biology 2: 139-152.

In summary, the following is still open:

• What is the computational complexity of computing the minimum spread when restricted to particular classes of phylogenetic networks?