What should a database of datasets look like?

In the previous post, Steven made the very good point that we need a "database" of datasets that can be used to evaluate algorithms for phylogenetic networks. In biological terms, we currently lack a "gold standard" with which to compare the results of our data analyses. This is an important point, to which it is worth adding a few biological notes.

Validation (or evaluation) is a common analytical problem, not just in biology, and it has been addressed in many different circumstances. For example, another area within which I work is multiple DNA sequence alignment. Between 1999 and 2005 several different databases of empirical alignments were developed: BAliBase, OXBench, PREFAB, SABmark, and BRAliBase. These were created independently of each other, and were ostensibly designed for somewhat different purposes. Evaluations of computer algorithms since that time tend to have used several of these databases as their gold standard; and it is quite obvious that success using one of the databases does not imply success with any of the others.

This background has lead me to the conclusion that a database needs a structured set of data, with the structure addressing all of the different biological issues that are likely to be important. For example, phylogenetic networks are used to analyze datasets that contain "reticulation" events such as hybridization & introgression, lateral gene transfer, recombination, and genome fusion, but such events can be confounded by other events such as deep coalescence and hidden paralogy. So, a truly valuable database would have datasets that encompass not only all of these possibilities but their combinations as well. Chris Whidden's comment on Steven's post discusses the same important issue, but from the point of view of the mathematical requirements for finding the optimal network.

Such a database is a very ambitious goal. More to the point, I doubt that such a database could be created without widespread collaboration, as both Steven and Chris have emphasized.

BAliBase (referred to above) attempted to have a structured set of multiple alignments, but it is interesting to note that this structure was mostly ignored by subsequent users of the database. The users simply pooled all the different groups of alignments together and came up with an "average" success for the alignment algorithms, rather than discovering (as they would have done; see Morrison 2006) that different algorithms have different degrees of success depending on the particular characteristics of the dataset being analyzed. We should not make the same mistake when evaluating network algorithms.

I think that there have been four suggested approaches to acquiring datasets for evaluating tree/network algorithms (in order of increasing reality):

1. simulation under one or more data-generation models
2. create mixed datasets from "pure" datasets, or create artificial mosaic taxa from real datasets
3. use datasets where the postulated events have been independently confirmed
4. experimentally create taxa with a known evolutionary history.

Option (1) has been used by many workers to evaluate tree-building algorithms, and the models have been readily adapted for phylogenetic networks (eg. Bandelt et al. 2000; Morin 2007; Woolley et al. 2008). Indeed, this has been the most common strategy for evaluating network algorithms, although there seems to be little consensus so far on what data-generation model(s) to use. The basic limitation here is that simulations (a) only show the success of the algorithms relative to how well they fit the model used to simulate the data, and (b) the relationship between the simulation model and the "real world" is unknown.

Option (2) has rarely been used for networks (eg. Vriesendorp 2007). The basic idea is to create "known" reticulations by combining parts of pre-existing datasets that lack reticulation signals. One can either combine whole datasets that contain mutually incompatible signals, or one can create individual taxa that have parts of their data taken from different reticulation-free datasets. This is a promising approach to "experimental" phylogenetics, although lack of prior experience means that we do not yet know how to use this strategy most effectively.

Option (3) is an obvious approach to collating data (McDade 1990), and has been used for evaluating tree-building algorithms (eg. McDade 1992; Leitner et al. 1996, Lemey et al. 2005). This has been used, for example, for fast-evolving organisms such as viruses, where the transmission history can sometimes be independently checked. Also, hybrids can often be experimentally verified; and Vriesendorp (2007) lists several such datasets for plants. The problem here is the degree to which the postulated reticulation events have been independently confirmed. A network reticulation may look like good evidence in favor of a "suspected" hybrid, for example, but it is not really independent evidence of anything in particular. I suspect that this weak sort of reasoning has been applied to far too many datasets used for the evaluation of network algorithms, where unsuitable datasets have been employed.

Option (4) has occasionally been used for evaluating tree-building algorithms (eg. Hillis et al. 1992; Cunningham et al. 1998; Sanson et al. 2002) but not, as far as I know, network algorithms. The idea is to experimentally manipulate some biological organisms in the laboratory to create a known evolutionary history, against which subsequent data analyses can be compared. Realistically, this restricts the datasets to viruses and phages, as these can be manipulated within a reasonable timeframe.

We need to think about which of these options we wish to adopt. Perhaps all of them?

Note: The suggested database now exists: Datasets for validating algorithms for evolutionary networks

References

Bandelt H.-J., Macauley V., Richards M. (2000) Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA. Molecular Phylogenetics & Evolution 16: 8–28.

Cunningham C.W., Zhu H., Hillis D.M. (1998) Best-fit maximum-likelihood models for phylogenetic inference: empirical tests with known phylogenies. Evolution 52: 978-987.

Hillis D.M., Bull J.J., White M.E., Badgett M.R., Molineux I.J. (1992) Experimental phylogenetics: generation of a known phylogeny. Science 255: 589-592.

Leitner T., Escanilla D., Franzén C., Uhlén M., Albert J. (1996) Accurate reconstruction of a known HIV-1 transmission history by phylogenetic tree analysis. Proceedings of the National Academy of Sciences of the USA 93: 10864-10869.

Lemey P., Derdelinckx I., Rambaut A., Van Laethem K., Dumont S., Vermeulen S., Van Wijngaerden E., Vandamme A.-M. (2005) Molecular footprint of drug-selective pressure in a Human Immunodeficiency Virus transmission chain. Journal of Virology 79: 11981–11989.

McDade L.A. (1990) Hybrids and phylogenetic systematics I. Patterns of character expression in hybrids and their implications for cladistic analysis. Evolution 44: 1685–1700.

McDade L.A. (1992) Hybrids and phylogenetic systematics II. The impact of hybrids on cladistic analysis. Evolution 46: 1329–1346.

Morin M.M. (2007) Phylogenetic Networks: Simulation, Characterization, and Reconstruction. PhD Thesis, University of New Mexico.

Morrison D.A. (2006) Multiple sequence alignment for phylogenetic purposes. Australian Systematic Botany 19: 479-539.

Sanson G.F.O., Kawashita S.Y., Brunstein A., Briones M.R.S. (2002) Experimental phylogeny of neutrally evolving DNA sequences generated by a bifurcate series of nested polymerase chain reactions. Molecular Biology & Evolution 19: 170–178.

Vriesendorp B. (2007) Phylogenetworks: Exploring Reticulate Evolution and its Consequences for Phylogenetic Reconstruction. PhD Thesis, Wageningen University.

Woolley S.M., Posada D., Crandall K.A. (2008) A comparison of phylogenetic network methods using computer simulation. PLoS One 3: e1913.

Validating methods for constructing evolutionary phylogenetic networks

Many researchers working on constructing evolutionary (i.e. explicit, as opposed to implicit/data-display) phylogenetic networks encounter the problem that, at present, there are not many options for validating the biological relevance of their methods. In other words, how does a researcher verify whether the network produced by his/her latest algorithm is a biologically plausible approximation of reality? This is of critical importance because, unlike implicit/data-display networks, evolutionary phylogenetic networks seek to produce an explicit hypothesis of what actually happened.

Ideally there should be a repository of biological datasets where there is some level of consensus amongst biologists as to the character, extent and location of reticulate evolutionary events. This can then be used as a framework for validating the output of algorithms for constructing evolutionary phylogenetic networks. Unfortunately, as far as I am aware there are very few such “reference” datasets in circulation – if any.  There seem to be multiple reasons for this. Within biology reticulate evolution is still a comparatively new topic which actually encompasses an entire range of evolutionary time-scales and phenomena. I can fully appreciate that trying to get a grip on even a tiny part of this world is an immensely complex task for biologists! This is probably why biological validation of algorithmic methods, if it happens at all, still requires collaborating biologists to perform a labour-intensive and highly case-specific analysis. It will be a massive challenge to move beyond such ad-hoc models of validation.

On the algorithmic side there are also plenty of issues. Input-side and output-side limitations to existing software are well-known. Expressed deliberately sharply: it is not often that one encounters a biologist who has two fully-refined, unambiguously rooted gene trees on the same set of taxa who wants to develop a reticulation-minimal solution and who does not mind if ancestors can hybridize with descendants. Faced with such limitations computer scientists inevitably resort to simulations or try and analyse the same dataset that the last group of computer scientists used, which is (sigh…) probably the Grass Phylogeny Working Group's Poaceae dataset. Simulations tend to use a variety of plausible-sounding techniques (e.g. random rSPR moves to simulate HGT, or – at the population-genomic level – techniques for simulating recombination) but in how far do these simulations really approximate reality?

My concern is that, at the moment, biologists and computer-scientists are locked in an unhealthy embrace, both expecting the other group to come up with “real” networks. This could be dangerous. I’ve seen biologists adjust their hypotheses based on the output of evolutionary phylogenetic network software. But those computer programs often lack any form of biological validation: not because algorithm designers are bad people aiming to mislead but because the apparently intractable character of the associated optimization problems forces computer scientists to make all kinds of restrictions and assumptions which are not necessarily compatible with the concerns of biologists. In any case: it’s clearly not helpful if hypotheses derived this way find their way back into the literature with an “approved by biologists” seal of approval.

How, then, to transform this embrace into something more virtuous? One possibility could be a structured collaboration between groups in the phylogenetic network community to produce and disseminate at least a small number of rigorously validated reference datasets which can serve as benchmarks. Is this realistic?

Very curious to hear what you think!

Note: The suggested database now exists: Datasets for validating algorithms for evolutionary networks