Networks of polysemous and homophonous words

When I was very young, maybe even before I went to school, we often played a game with my parents and grandparents, during which we had to select two homophonous words (that is, one word form that expresses two rather different meanings), and the other people had to guess which word we had selected. This game is slightly different from its Anglo-Saxon counterpart, the homophone game.

In Germany, this game is called Teekesselchen: "little teapot". Therefore, people now also use the word Teekesselchen to denote cases of homophonoy or very advanced polysemy. In this sense, the word Teekesselchen itself becomes polysemous, since it denotes both a little teacup, and the phenomenon that word forms in a given language may often denote multiple meanings.

Homophony and polysemy

In linguistics, we learn very early that we should rigorously distinguish the phenomenon of homophony from the phenomenon of polysemy. The former refers to originally different word forms that have become similar (and even identical) due to the effects of sound change — compare French paix "peace" and pet "fart", which are now both pronounced as [pɛ]. The latter refers to cases where a word form has accumulated multiple meanings over time, which are shifted from the original meaning — compare head as in head of department vs. head as in headache.

Given the difference of the processes leading to homophony on the one hand and polysemy on the other, it may seem justified to opt for a strict usage of the terms, at least when discussing linguistic problems. However, the distinction between homophony and polysemy is not always that easy to make.

In German, for example, we have the same word Decke for "ceiling" and "blanket" (Geyken 2010). This may seem to reflect a homophony at first sight, given that the meanings are so different, so that it seems simpler to assume a coincidence. However, it is in fact a polysemy (cf. Pfeiffer 1993, s. v. «Decke»). This can be easily seen from the verb (be)decken "to cover", from which Decke was derived. While the ceiling covers the room, the blanket covers the body.

Given that we usually do not know much about the history of the words in our languages, we often have difficulties deciding whether we are dealing with homophonies or with polysemies when encountering ambiguous terms in the languges of the world. The problem of the two terms is that they are not descriptive, but explanative (or ontological): they do not only describe a phenomenon ("one word form is ambiguous, having multiple meanings"), but also the origin of this phenomenon (sound change or semantic change).

In this context, the recently coined term colexification (François 2008) has proven to be very helpful, as it is purely descriptive, referring to those cases where a given language has the same word form to express two or more different meanings. The advantage of descriptive terminology is that it allows us to identify a certain phenomenon but analyze it in a separate step — that is, we can already talk about the phenomenon before we have found out its specific explanation.

A new contribution

Having worked hard during recent years writing computer code for data curation and analysis (cf. List et al 2018a), my colleagues and I have finally managed to present the fascinating phenomena of colexifications (homophonies and polysemies) in the languages of the world in an interactive web application. This shows which colexifications occur frequently in which languages of the world.

In order to display how often the languages in the world express different concepts using the same word, we make use of a network model, in which the concepts (or meanings) are represented by the nodes in the networks, and links between concepts are drawn whenever we find that any of the languages in the sample colexifies the concepts. The following figure illustrates this idea.

Colexification network for concepts centering around "FOOD" and "MEAL".

This database and web application is called CLICS, which stands for the Database of Cross-Linguistic Colexifications (List et al. 2018b), and was published officially during the past week (http://clics.clld.org) — it can now be freely accessed by all who are interested. In addition, we describe the database in some more detail in a forthcoming article (List et al. 2018c), which is already available in form of a draft.

The data give us fascinating insights into the way in which the languages of the world describe the world. At times, it is surprising how similar the languages are, even if they do not share any recent ancestry. My favorite example is the network around the concept FUR, shown below. When inspecting this network, one can find direct links of FUR to HAIR, BODY HAIR, and WOOL on one hand, as well as LEATHER, SKIN, BARK, and PEEL on the other. In some sense, the many different languages of the world, whose data was used in this analysis, reflect a general principle of nature, namely that the bodies of living things are often covered by some protective substance.

Colexification network for concepts centering around "FUR".

Although we have been working with these networks for a long time, we are still far from understanding their true potential. Unfortunately, nobody in our team is a true specialist in complex networks. As a result, our approaches are always limited to what we may have read by chance about all of those fascinating ways in which complex networks can be analyzed.

For the future, we hope to convince more colleagues of the interesting character of the data. At the moment, our networks are simple tools for exploration, and it is hard to extract any evolutionary processes from them. With more refined methods, however, it may even be possible to use them to infer general tendencies of semantic change in language evolution.

References

Geyken A. (ed.) (2010) Digitales Wörterbuch der deutschen Sprache DWDS. Das Wortauskunftssystem zur deutschen Sprache in Geschichte und Gegenwart. Berlin-Brandenburgische Akademie der Wissenschaften: Berlin. http://dwds.de

François A. (2008) Semantic maps and the typology of colexification: intertwining polysemous networks across languages. In: Vanhove, M. (ed.) From Polysemy to Semantic Change, pp 163-215. Benjamins: Amsterdam.

List J.-M., M. Walworth, S. Greenhill, T. Tresoldi, R. Forkel (2018) Sequence comparison in computational historical linguistics. Journal of Language Evolution 3.2. http://dx.doi.org/10.1093/jole/lzy006

List J.-M., S. Greenhill, C. Anderson, T. Mayer, T. Tresoldi, R. Forkel (forthcoming) CLICS². An improved database of cross-linguistic colexifications: Assembling lexical data with help of cross-linguistic data formats. Linguistic Typology 22.2. https://doi.org/10.1515/lingty-2018-0010

List J.-M., S. Greenhill, C. Anderson, T. Mayer, T. Tresoldi, and R. Forkel (eds.) (2018) CLICS: Database of Cross-Linguistic Colexifications. Max Planck Institute for the Science of Human History: Jena. http://clics.clld.org

Pfeifer W. (1993) Etymologisches Wörterbuch des Deutschen. Akademie: Berlin.

Some new additions to the dataset database

Recently, I have added three new datasets to the database of "gold standards" that might be used to evaluate network algorithms. All three are different to what has previously been included, and so I will briefly discuss them here.

Pedigree data

I have included a known pedigree from a small group of thoroughbred stallions (Eclipse dataset) for which there are mitochondrial D-loop (control region) sequences. Pedigrees are networks, not trees, whenever there is inter-breeding among close relatives, and so their inclusion in the database is needed.

There are practical problems with including more pedigrees. Most of the known pedigrees do not have readily available sequence data associated with them, as the collected data have been mainly for features associated with diseases syndromes. Conversely, most of the available sequence data are not associated with known pedigrees, although for humans they are often taken from known social / linguistic / geographical groups (usually based on the place of birth of all four grandparents).

Language data

The database currently contains only a few examples from the social sciences, notably some experimental manipulations from stemmatology. However, there is so far nothing from linguistics, mainly because the phylogenetic history of languages is often poorly known. Nevertheless, languages form networks whenever there is borrowing of words (ie. loan words) between languages (usually as a result of geographical contact), and so their inclusion is desirable.

I have now included one dataset (the List dataset) taken from what appears to be the best-curated source of linguistic data, the Indo-European Lexical Cognacy Database. Known loan words are explicitly tagged in this source; and the phylogenetic relationships of many Indo-European languages are also tolerably well known (eg. see Ethnologue: Languages of the World).

Simulated data

I have not previously included simulated data, for two reasons. First, such data can easily be generated anew each time a set is required; and even if this is impractical then there are readily available datasets online (eg. see the compilation at utcs Phylogenetics). Second, and more importantly, simulations are based on a model (eg. using Brownian motion, Ornstein–Uhlenbeck, or Markov chains), and therefore they model only a subset of reality. Simulations are useful for situations involving a few well-defined variables, but they are much less useful for multivariate data such as occur in phylogenetics.

Nevertheless, I have included one well-known dataset, the Caminalcules (Camin dataset). These data were simulated manually back in the 1960s, and they include morphological features for both extant and fossil organisms. Over the years, the data have been used for many pedagogic purposes in the teaching of systematics, particularly in the U.S.A. (see Pasta have no phylogeny, so don't try to give them one). The data are strictly tree-like, and they do match real datasets in a number of ways (see Sokal 1983). However, there are also known ways in which they differ detectably from real data (see Holman 1986; Wirth 1993).

References

Holman EW (1986) A taxonomic difference between the Caminalcules and real organisms. Systematic Zoology 35: 259-261.

Sokal RR (1983) A phylogenetic analysis of the Caminalcules. I. The data base. Systematic Zoology 32: 159-184.

Wirth U (1993) Caminalcules and Didaktozoa: imaginary organisms as test-examples for systematics. In: Opitz O, Lausen B, Klar R (eds) Information and Classification: Concepts, Methods and Applications, pp. 421-433. Springer, Berlin.

Sharing supplementary data: a linguist's perspective

The Problem of Data Sharing

In 2013, Nature launched a discussion on how to increase the reproducability of research in the biomedical sciences. David addressed the problem of data sharing more concretely in two blog posts from 2013, one on the practice of releasing phylogenetic data, and one on its public availability. In my opinion, this topic does not only concern the sciences, but also, and even specifically, the humanities. In times where more and more data for anthropological research is being produced, and the formerly manually conducted analyses are being automated, we need to increase the awareness of scholars and publishers that publishing only the results is not enough to meet rigorous scientific standards.

When discussing these issues with colleagues, various reasons have been brought up as to why scholars would not release their data along with a publication. Apart from practical considerations (which mostly concern the publishers who do not provide the infrastructure to host supplementary material transparently), scholars often also bring up personal and legal concerns: they are afraid that their painstaking efforts in collecting a dataset will have been in vain, once they release the data to the public, since other researchers might take over and run analyses they would like to run themselves in the future. Furthermore, there are situations when data cannot simply be published completely, because the compilers of the datasets do not obtain the copyrights on the data itself.

In my opinion, all of these problems can be solved directly, and there is no reason to publish a study in which at least a part of the data is not provided in supplementary form.

Practical Solutions: GitHub and Zenodo

Regarding practical issues, one can use GitHub to host and curate data and computer source code. The advantage of using GitHub is that it allows for distributed revision control: all changes and modifications to the data can be tracked, and all of those who contributed to the compilation of a given dataset can receive the credit they deserve. Even for the case of anonymous data submission, there is a simple solution available along with GitHub Gist: by just uploading data to a Gist (a flat repository which does not allow for a folder structure) without being logged in with a GitHub account, one can anonymously host the data for review purposes.

If one doesn't completely trust the longeavity of GitHub in hosting the data forever (it might well happen that GitHub changes its payment policy at some point in the future, or limits the amount of open repositories), there is Zenodo, which offers full GitHub integration and allows storage of up to 2 GB per dataset. For more information regarding the possibilities that the GitHub integration offers, see this blog post by Robert Forkel. Zenodo was developed by CERN and, although they write on their website that their sustainability plan is still in development, it is quite unlikely that they will run out of funding within the next twenty years.

As a recommended way of hosting data, one would start with an anonymous Gist when submitting a paper. This would then be converted to a full GitHub repository once the paper has been accepted. By setting up an official release of this repository, the data would be automatically transferred to Zenodo, where it is permanently stored and provided with a DOI.

Sharing Data Prevents Data Theft

Regarding the personal concerns that one's data might be "stolen" by other scholars, I think it is important to make clear that at the core of all research we build on the work of our colleagues. Nobody should own a dataset, as well as nobody should own a theory. It is clear that in the stage of developing datasets (as well as theories), we may decide to be careful in sharing them with certain colleagues. But once they are finished and ready to use, we should allow our colleagues to run their own analyses on them.

What is important and missing here is an established practice, but also infrastructure support to give credits to the work of others. In linguistics, we lack journals, such as BMC Bioinformatics, that publish articles on source code or databases. There are, however, recent attempts to address these problems in linguistic research (see, for example, this blog post by Martin Haspelmath).

But even while this infrastructure is lacking, it should be made clear that scholars win more than they risk when submitting their data along with their publication. If the data turns out to be useful for additional research, then they will receive credit in the form of citations, and they will even prevent others from actually stealing their data — as with ideas, data can only be stolen by falsely associating it with another name. Once the data is out along with the publication, this is not likely to happen.

Giving Something is More than Giving Nothing

Even in those cases where there are real copyright restrictions, one can make a compromise and publish an illustrative snapshot of the data and the detailed results. Especially, computational analyses produce a large amount of data as part of their results, and this data may well turn out to be interesting for other scholars. Instead of publishing just a tree or a network, we may want to see the individual character evolution that was inferred along with the algorithm. And when illustrating a new algorithm for homolog detection in historical linguistics, it may be interesting for one scholar or another (but maybe also for the reviewer) to have a look at the detailed results apart from the aggregated evaluation scores.

Summary and Outlook

Current research practice in historical linguistics faces serious reproducability problems. Fortunately, solutions exist for most of the practical problems of the past. What we need now is to increase the awareness among scholars that all research based on data and source code is nothing without the data and the source code. Publishing both source code and data along with a paper is easy nowadays, especially thanks to GitHub and Zenodo. Guaranteeing that one gets the credit for ones efforts in the humanities is a bit more difficult, but not impossible, and colleagues are working on solutions.

What we need in addition to the publication of the raw data itself are explicit formats of data exchange. In historical linguistics, using only NEXUS-format files is not sufficient, since the nature of our data requires its own representation. Here again, scholars are already working on a solution by trying to define and establish specific formats for data sharing in historical linguistics and typology (see this discussion on GitHub).

In an ideal future scenario that was introduced to me by Michael Cysouw, all publications involving automatic analyses should provide not only the supplementary data, but also some kind of a MAKE file containing the code for the workflow that enables scholars to carry out the computational analyses immediately on their computer.

Is this a "gold standard" dataset?

I have just added another dataset to our database. This one is of considerable interest, because it is a complex one. As the authors note, it is likely to contain ancient hybrid speciation, recent introgression and deep coalescence. Thus, identifying recent hybrids will be problematic.

Michael L. Moody and Loren H. Rieseberg (2012) Sorting through the chaff, nDNA gene trees for phylogenetic inference and hybrid identification of annual sunflowers (Helianthus sect. Helianthus). Molecular Phylogenetics and Evolution 64: 145–155.

There are 29 accessions from 13 species, with data for 11 loci in 5 linkage groups (a total of 8,077 aligned nucleotides). The accessions have sequences for either 1 or 2 of the alleles, and sometimes 3 (the latter are likely to be the result of PCR artifacts). The authors have also tried to identify recombinant sequences. Three of the species are previously identified hybrid taxa.

Unfortunately, adding this dataset to the database has also been problematic, because there are internal inconsistencies. For complete consistency, Figure 1 of the paper should agree with its own Table 1, and the GenBank data should agree with both of them. Unfortunately, this three-way consistency exists for only 2 of the 11 loci. For the rest, in 7 instances the dataset is the odd one out, in 4 cases it is the table, and in four instances it is the figure. For the data discrepancies, in 2 cases a sequence is missing, in 1 case there is an extra sequence, and for the remaining 2 pairs it is likely that there is mis-labelling of the sequences.

It is therefore not immediately obvious to what extent this counts as a "gold standard" dataset. I have included it because of its intrinsic interest, but obviously with a caveat emptor warning. Sadly, this sort of situation has been all too common in my search for suitable datasets.

Request for datasets

During one of the discussion sessions at the recent Phylogenetic Network Workshop, in Singapore, the need was re-iterated for "gold standard" empirical datasets, in order to aid the development and validation of algorithms for phylogenetic networks.

The current collection of such datasets is located on this blog, at:

http://phylonetworks.blogspot.se/p/datasets.html

However, it is still quite a small database, as so far it has been based solely on my own ability to locate suitable datasets that are freely available (see the comments in Public availability of phylogenetic data).

I would therefore like to remind everyone that if you have, or know of, suitable empirical datasets then please contact me.

The database is currently hierarchically arranged as follows:

Datasets where the history is a tree
  Datasets where the history is known from experimentation
  Datasets where the history is known from retrospective observation
Datasets where the history is reticulated
  Datasets where the history is known from experimentation
    Hybridization
    Contamination
  Datasets where the reticulation is inferred
    Hybridization
    Recombination
    Lateral Gene Transfer

The basic requirement for a "gold standard" dataset that contains one or more reticulations (ie. there is gene flow) is that the evidence for the reticulation(s) is independent of the particular dataset. That is, there should be either experimental data, or at least another independent dataset, confirming the gene flow. This is quite a tough criterion, particularly for lateral gene transfer, but it is a necessary quality criterion.

Finally, the database requires the processed data (eg. a multiple sequence alignment), rather than the original raw data (see the comments in Releasing phylogenetic data).

The need for a new sequence alignment database

Multiple sequence alignment software have not yet met their primary aim for evolutionary biologists: maximizing homology of characters. The proliferation of alignment methods have diverse optimization functions, along with assorted heuristics to search for the optimum alignment; and these methods produce detectably different multiple sequence alignments in almost all realistic cases (see The need for a new sequence alignment program). This leaves the phylogeneticists wondering what to do. In response, the majority of phylogeneticists use manual alignment or re-alignment at some stage in their procedures.

If our goal is to develop an automated procedure for homology assessment (see Multiple sequence alignment), then we need some means of evaluating the relative success of different alignment methods.

There are four suggestions for benchmarking strategies for sequence alignment (Iantorno S, Gori K, Goldman N, Gil M, Dessimoz C 2014. Who watches the watchmen? An appraisal of benchmarks for multiple sequence alignment. Methods in Molecular Biology 1079: 59-73):

1. Benchmarks based on simulated evolution of biological sequences, to create examples with known homology.
2. Benchmarks based on consistency among several alignment techniques.
3. Benchmarks based on the three-dimensional structure of the products encoded by sequence data.
4. Benchmarks based on knowledge of, or assumption about, the phylogeny of the aligned biological sequences.

These authors list a number of pros and cons for each strategy. For our purposes here we nee to consider the cons, which I discuss here (not all of these are covered by the authors).

Cons

1.
Simulation-based approaches adopt a probabilistic model of sequence evolution to describe nucleotide substitution, deletion, and insertion rates, while keeping track of “true” relationships of homology between individual residue positions (see Do biologists over-interpret computer simulations?).
(a) The simulation and analysis methods are not independent. All observations drawn from simulated data depend on the assumptions and simplifications of the model used to generate the data. This means that the results are biased towards those analysis methods that most closely match the assumptions of the simulation model.
(b) Simulations cannot straightforwardly, if at all, account for all evolutionary forces. This means that the simulations are not realistic, and their relevance for the behaviour of real datasets is unknown. The biggest failing in this regard is that, at some stage in the simulation, insertions and deletions are assumed to occur at random along the sequence (IID), and nothing could be further from the truth. Sequence variation occurs as a result of tandem repeats, inverted repeats, substitutions, inversions, translocations, transpositions, deletions, and insertions; and there are strong spatial constraints on variation such as codons and stem-loops. Current simulation methods fall well short of modeling these patterns of sequence variation.

2.
The key idea behind consistency-based benchmarks is that different good aligners should tend to agree on a common alignment (namely, the correct one) whereas poor aligners might make different kinds of mistakes, thus resulting in inconsistent alignments.
(a) Two wrongs don't make a right. That is, consistent methods may be collectively biased. Moreover, consistency is not independent of the set of methods used (some may be consistent with each other and not with others).
(b) Consistency scores are a feature of several methods, which means that the benchmark is not independent.

3. Structural benchmarks most commonly employ the superposition of known protein/RNA structures as an independent means of alignment, to which alignments derived from sequence analysis can then be compared (see Edgar RC 2010. Quality measures for protein alignment benchmarks. Nucleic Acids Research 38: 2145-2153). The best known of these include: BAliBASE, OXBench, PREFAB, SABmark, IRMBase, and BRAliBase.
(a) Datasets are limited to structurally conserved regions, and may not be relevant for other alignment objectives.
(b) Deriving the structure-based alignments is problematic. For example, there is inconsistency amongst different stuctural superpositions.

4. Given a reference tree, the more accurate is the tree resulting from a given alignment, then the more accurate the underlying alignment is assumed to be (see Dessimoz C, Gil M 2010. Phylogenetic assessment of alignments reveals neglected tree signal in gaps. Genome Biology 11: R37).
(a) False inversion of a proposition: Accurate alignments yield accurate trees, therefore accurate trees must be based on accurate alignments.
(b) Alignment is often involved in constructing the reference tree. If not, the tree may be trivial in terms of taxon relationships.

Discussion

This evaluation leaves us in the invidious position of not yet having any benchmarking method that is relevant to homology assessment for multiple sequence alignments. This conclusion is at variance with other previous assessments (eg. Aniba MR, Poch O, Thompson JD 2010. Issues in bioinformatics benchmarking: the case study of multiple sequence alignment. Nucleic Acids Research 38: 7353-7363).

We need to consider what such a method might look like, and how we might go about constructing it. If biologists can't give the bioinformaticians a concrete goal for homology alignment then they can expect nothing in return.

It seems clear that we need to follow the idea behind option 3, but base the alignments on homology rather than structure. I once made a start with compiling some suitable datasets (see Morrison DA 2009. A framework for phylogenetic sequence alignment. Plant Systematics and Evolution 282: 127-149); but this was a very minor effort.

As I see it, we need alignments that are explicitly annotated with the reasons for considering the columns to be homologous. One suggestion would be to have relatively short alignments with annotations for "known" features, such as tandem repeats, inverted repeats, substitutions, inversions, translocations, transpositions, deletions, insertions, or stem-loops. These all create sequence variation, and they provide evidence of the homology relations among the sequences. Presumably the alignments would vary in length and number of sequences, and in the complexity of the patterns.

Perhaps the biggest practical problem will be how to deal with alignments where the homology criteria conflict with each other. That is, there are different types of criteria used to recognize homology — ie. similarity, structure, ontogeny, congruence (see Morrison DA 2015. Is multiple sequence alignment an art or a science? Systematic Botany 40: 14-26) — and they do not necessarily agree with each other.

This would allow us to come up with a set of requirements to specify various categories of the database, based on each of the above features. We would then try to accumulate as many example datasets for each category as we can. The database will presumably have protein-coding sequences in one section and RNA-coding, introns, etc in another. This dichotomy is simplistic, but I feel that it needs to be that way in order to be of practical use. Within each of those two sections we would have subsets of varying degrees of difficulty (eg. different degrees of average sequence similarity, or distinct taxon subsets in the same alignment, or orphan sequences).

This organisational approach is similar to that originally adopted for BAliBase, but it was dropped by most of the databases developed subsequently. I believe that it is the best approach for our purposes.

There are also experimentally created datasets where the alignment is known because all of the ancestors were sequenced as well. These would be useful; but their limitation is that the sequence variation was generated more or less at random, and so it does not match normal evolutionary processes. These alignments are more likely to match the IID assumption of the current automated alignment methods.

There is one further issue with this approach. Bioinformaticians often state that a few carefully prepared datasets is of little practical use to them (as opposed to being of use to phylogeneticists). What they need is a large number of datasets, the more the better. This is because they are interested in the percent success of their algorithms, and this cannot be assessed with small sample sizes. So, each alignment probably does not need to have too many taxa or too much sequence length — it is the number of alignments that is important, not their individual sizes. This could be achieved by sub-dividing larger datasets.

A BLAST search doesn't do what you think it does

BLAST is a computer program that searches a database for similarity matches to a given query sequence, either DNA or amino acid. It is most commonly used to search the GenBank database for matches to any new sequence that we might happen to have, in the hope that we will find one or more homologous sequences.

To most of us BLAST is a black box, in the sense that we have little idea about the details of how it does what it does. So, maybe we should at least look at what it does, just in case we ever need to know.

About 10 years ago I was working with some EST data. For those of you not old enough to know, ESTs consist of short DNA reads from arbitrary primers. In the hope of identifying the coding gene represented by each EST, BLASTX is used to search the GenBank protein database using each translated nucleotide query (in all six possible reading frames). BLASTX produces an E-value for each matching sequence, representing the strength of the match to the query. An E-value is not a probability (as they can vary from 0 to infinity), but at p=0.050 the expected E-value happens to be E=0.051. There is no consensus for what E-value should serve as indicating a "significant" match.

I decided to find out what happens if a DNA query sequence varies in either length or GC content. I used both random sequences (which were thus not in GenBank) as well as real sequences (which were in GenBank). The short answer is that the BLASTX results vary a lot. I never published these results because I figured the first thing a referee would do is ask me to explain BLASTX's behaviour, and I did not have an explanation (and still don't).

I present the results here for what they are still worth. Obviously, the results are not restricted to EST data, but apply any time that we use BLASTX.

Experimentation

The content of GenBank is quite different today to what it was back in late 2003, and so maybe the results will vary if the work was to be repeated. For reference, the first graph shows the GC content of the GenBank protein-coding sequences at the time of my work. Also, it is possible that BLASTX is different as well — I used v. 2.2.6 with default parameters (BLOSUM62, edge correction, length correction, SEG filtering, universal genetic code, gap penalty 11+k). Maybe some intrepid soul will be inspired to find out what happens nowadays.

Random sequences

I generated sets of 1,000 replicate "ESTs" using the perl script Randseq by M. Raymer (5/27/2003). These sets varied in DNA length (100–1,000 nt) and in GC content (0–94%), but were otherwise random sequences of nucleotides. These sequences are not expected to be homologous to anything already in GenBank, and should thus form BLASTX matches only by random chance.

The results for varying the sequence length are shown in the next graph, with each point representing the mean E-value observed. The lines represent four somewhat different GC contents; and the anticipated E-value for random data (0.051) is also shown. Clearly, very few points are near the expected value. The lines all show the same shape, with a minimum E-value near 450 nt, and rising slowly with longer lengths and rising rapidly with shorter lengths.

A more detailed assessment of the results for varying the GC content is shown in the third graph. The lines represent two somewhat different sequence lengths; and the anticipated E-value for random data (0.051) is also shown. It is clear that the E-value is capable of varying by up to seven orders of magnitude in response to variation in the GC content of the sequence.

Real sequences

I used the sequences contained in the Poxvirux Orthologous Clusters database (POCs), which used to be available at: http://athena.bioc.uvic.ca/pbr/POCs/pocs.html. This has since been replaced by the Viral Orthologous Clusters database (VOCs). These virus protein sequences are expected to already be in GenBank, and they should thus form good BLASTX matches.

The POCs database could be queried by both sequence length and GC content, and it was the only such database that I could find at the time. For each combination of length (in 50-nt bands) and GC-value (in 10% bands) I gathered a minimum of 20 sequences. There were few sequences for the shortest lengths, so I chopped up the longest sequences (longer then needed) to increase the sample size. There were also few sequences at the greatest GC values, so I used sequence AE004437.1 from GenBank (a Halobacterium sp.) to increase the sample size.

The results are shown in the final graph, with each point representing the mean E-value observed. The E-values are all small, since they represent actual database matches. Clearly, variation in sequence length can lead to orders of magnitude variation in E-value, while variation in GC content has an effect only at longer sequence lengths.

Conclusions

For a program that is supposed to produce comparable results, no matter what the sequence, these BLASTX results are disquieting. After all, BLAST is one of the most cited programs ever (see Massive citations of bioinformatics in biology papers), and yet I suspect that most people do not realize that it behaves like this.

The random sequences assess the effect of false positives. That they vary so much in E-value is amazing. Clearly, BLASTX E-values are not comparable between sequences. It is interesting that GC content seems to have a bigger effect than sequence length — for any given GC content the effect of length is relatively small for sequences longer than c. 600 nt. However, variation in GC content can produce orders of magnitude of effect at any given sequence length.

The real sequences assess the effect of true positives. That they vary in E-value is also not good — the E-values all represent true database matches (and presumably exact ones). Nevertheless, the effect of variation in sequence length and GC content is repeated for these real sequences. However, variation in GC content only has a large effect for the longer sequences, and instead it is the sequence length that produces the orders of magnitude variation in E-value.

You can make of this what you will.

Archiving of phylogenetics data

The draft Minimum Information about a Phylogenetic Analysis standard (Leebens-Mack et al. 2006) suggests that all relevant information about each and every published phylogenetics analysis should be archived, so that it can be scrutinized by later researchers, either for validation or for re-use. The issues here are both preservation of the information (data and analysis protocols) and open access to it.

In this blog we have already pointed out that there has been criticism of the bioinformatics part of this archiving, where there have been repeated claims that many computer programs are poorly maintained (Poor bioinformatics?) as well as poorly archived (Archiving of bioinformatics software).

Anyone who has ever tried to get data out of a biologist will know that the data-related part of the standard is no better. My own success rate, at requesting data from all areas of biology not just phylogenetics, is less than 20% over the past 25 years. The responses have been, in order: (i) no response (>50%), (ii) "a student / postdoc / colleague has the data not me", and (iii) "I have moved recently and don't know where the data are". My most recent attempt, to get the data from Collard et al. (2006), was ultimately unsuccessful even after several attempts.

For phylogenetics, this situation has recently been quantified and analyzed by Magee et al. (2014). They tried to collect phylogenetic data (comprising nucleotide sequence alignment and tree files) from 217 published studies. Of these, 54 (25%) had at least some part of the data (alignment or tree) archived in an online repository, and 91 (42%) were obtained by direct solicitation, but in 72 (33%) of cases nothing could be obtained even after three requests. Overall, complete datasets (both tree and alignment) were available for only 40% of the studies.

The authors note that the data were more likely to be deposited in online archives and/ or shared upon request when the publishing journal has a strong data-sharing policy. Furthermore, there has been a positive impact of recent policy initiatives and infrastructural changes involving data repositories. The TreeBASE phylogenetic-data repository has existed for more than 20 years, but its use has been sporadic. However, the recent establishment of the Joint Data Archiving Policy by a consortium of journals, which requires the submission of data to online archives as a condition of publication, and the concomitant establishment of the Dryad repository for evolutionary and ecological data, has seen a surge in the archiving of data.

So, all in all, things have been no better on the bio side than the informatics side of bioinformatics.

Stoltzfus et al. (2012) have identified a number of possible barriers to successful data archiving, including lack of awareness of options and policies, perception that benefits do not justify burden, and an active desire to restrict data access. Importantly, there are also a number of practical issues even for those people who do wish to archive their data:

• inconvenience of gathering complete data and metadata
• inconvenience of format conversions needed for archiving
• frustration when some data don't fit the archive's data model
• poor and undocumented archive submission interfaces.

For the readers of this blog, issue three is possibly the most important one — all current repositories are based on a tree model for phylogenetics, and therefore network phylogenies are frustrating to deal with.

In order to improve the overall situation, there are explicit suggestions from Cranston et al. (2014) for best practices when archiving. They have ten simple guidelines that, if followed, will result in you providing open access to your data and analyses, even if the publishing journal does not force you to do it.

Footnote: I have been reminded that archiving data in PDF format is inappropriate. Trying to extract text (such as a dataset) from a PDF file can be difficult, because there is no standard format for storing the text. Consequently, different PDF readers will extract the text in different ways, and it is possible that in all cases the output will need extensive manual re-formatting, in order to recover the original text formatting that went into the PDF file. In my experience, Google Chrome may do the least-worst job.

References

Collard M, Shennan SJ, Tehrani JJ (2006) Branching, blending, and the evolution of cultural similarities and differences among human populations. Evolution and Human Behavior 27: 169-184.

Cranston K, Harmon LJ, O'Leary MA, Lisle C (2014) Best practices for data sharing in phylogenetic research. PLoS Currents Jun 19;6.

Leebens-Mack J, Vision T, Brenner E, Bowers JE, Cannon S, Clement MJ, Cunningham CW, dePamphilis C, deSalle R, Doyle JJ, Eisen JA, Gu X, Harshman J, Jansen RK, Kellogg EA, Koonin EV, Mishler BD, Philippe H, Pires JC, Qiu YL, Rhee SY, Sjölander K, Soltis DE, Soltis PS, Stevenson DW, Wall K, Warnow T, Zmasek C (2006) Taking the first steps towards a standard for reporting on phylogenies: Minimum Information About a Phylogenetic Analysis (MIAPA). OMICS 10: 231-237.

Magee AF, May MR, Moore BR (2014) The dawn of open access to phylogenetic data. PLoS One 9: e110268.

Stoltzfus A, O'Meara B, Whitacre J, Mounce R, Gillespie EL, Kumar S, Rosauer DF, Vos RA (2012) Sharing and re-use of phylogenetic trees (and associated data) to facilitate synthesis. BMC Research Notes 5: 574.

Network publications

Some of you may have noticed that the Who is Who in Phylogenetic Networks database is currently down while it is being moved to a new server. It will soon be back, but in the meantime here is a graph showing the number of publications in the database in its most recent iteration. The data are grouped according to their authors, with the top 20 most prolific authors separated on the left. The next 9 authors are included solely to get myself onto the graph.

There are no real surprises here; and there are plenty of other authors in the database with fewer publications to their name. The database data will be updated when the web site returns, in which case I might update this graph.

More datasets for validating network algorithms

Four more datasets have been added to the Datasets blog page. These are:

• 1 stemmatology study where the manuscript history is known from experimentation
• 2 stemmatology studies where the manuscript history is known from experimentation, and where there is reticulation caused by contamination
• 1 plant study where recombination is known.

These are the first three studies to be added from the social sciences, all of them from experimental manipulation of text copying.

Unfortunately, it is unlikely that suitable datasets will be found from other parts of the social sciences, such as linguistics; but please tell us if you know of any relevant studies, where the phylogenetic history is known or inferred independently of the dataset itself.

Archiving of bioinformatics software

Some months ago I wrote a blog post about what is perceived to be the rather poor quality of many computer programs in bioinformatics (Poor bioinformatics?), noting that many bioinformaticians aren't taking seriously the need to properly engineer software, with full documentation and standard programming development and versioning.

An obvious follow-up to that post is to consider the archiving of bioinformatics software. If programs are written well, then they should be permanently archived for future reference. A number of bloggers have commented on what is perceived to be the poor current state of affairs here, as well, and I thought that I might draw your attention to a few of the posts.

In many ways, this issue is the computational equivalent of storing biological data, about which I have also written recently (Releasing phylogenetic data). My comments about this were:

• There is a difference between storing / releasing the original data (eg. raw DNA sequences) and the data as analyzed (eg. aligned sequences)
• There are sustainable and accessible archiving facilities for raw data that are almost universally used (eg. GenBank)
• Many people do not release the processed data as analyzed (some of them will if directly asked to do so)
• Many of the people who do release their analyzed data do so on the homepage of one of the authors, which is better than nothing but is rarely sustainable
• There are sustainable and accessible archiving facilities for processed data, such as TreeBASE and Dryad.

Analogous comments can be made about the archiving of bioinformatics software.

The first question to ask is this: what proportion of the bioinformatics software referred to in publications is actually stored in sustainable and accessible archives? A corollary to this question is: what archive facilities are being used? Casey Bergman, at the I Wish You'd Made Me Angry Earlier blog, has attempted to answer both of these questions (Where Do Bioinformaticians Host Their Code?).

In answer to the first question, Casey notes:

of the many thousands of articles published in the field of bioinformatics, as of Dec 31 2012 just under 700 papers (n=676) have easily discoverable code linked to a major repository in their abstract.

While many papers may have the code URL in the Methods or Results sections but not the Abstract, this does suggest that repository archiving is not the mode actually employed by bioinformaticians. Instead, they are archiving (if at all) on personal or institutional homepages.

Sadly, the reported rate of decay of URLs ("Error 404: Page not found") indicates that this is rarely a sustainable approach to archiving (eg. see the Google+ comment by Dave Lunt). The relevance of the similar situation with the TreeBase / Dryad type of repository has not gone unnoticed, for example by Hilmar Lapp. These repositories require and enforce standards of data and software archiving, as well as providing persistence.

The answer to the second question, about which repositories, seems to be (see also the data provided by MRR in the comments to Casey's blog post):

• SourceForge has been vastly predominant
• Google Code has a large number of projects, but many of them have never made it to publication
• GitHub has had a rapid recent growth rate, and therefore appears to be becoming the preferred repository.

Other repositories, such as BitBucket, seem to be much less used. Users on other forums (eg. Biostar: Where would you host your open source code repository today?) seem to concur with the choice of GitHub, mainly because of the tools available (it is user-oriented rather than project-oriented).

This leads to the issue of how permanent the archiving is at the major repositories. It turns out that there is a major difference in policies, as noted by Casey Bergman:

SourceForge has a very draconian policy when it come to deleting projects, which prevents accidental or willful deletion of a repository. In my opinion, Google Code and (especially) GitHub are too permissive in terms of allowing projects to be deleted.

In a follow-up post (On the Preservation of Published Bioinformatics Code on GitHub), Casey expands on this theme:

A clear trend emerging in the bioinformatics community is to use GitHub as the primary repository of bioinformatics code in published papers. While I am a big fan of Github and I support its widespread adoption, I have concerns about the ease with which an individual can delete a published repository. In contrast to SourceForge, where it is extremely difficult to delete a repository once files have been released, and this can only be done by SourceForge itself, deleting a repository on GitHub takes only a few seconds and can be done (accidentally or intentionally) by the user who created the repository.

This is an important issue, as exemplified by Christopher Hogue in the comments section of that blog post:

In my case SourceForge preserved the SLRI toolkit my group made in Toronto. As the intellectual property underlying the code was sold to Thompson-Reuters in 2007, my host institution and the dealmakers pressured me to delete the repository. SourceForge policy kept it on the site ... [However,] the aftermath of all this is that, of everything my group did under the guise of open source, only about 30% is preserved and online, and the rest is buried in an intellectual property shoebox at Thompson-Reuters. Host institutions have a lot of power of ownership over your intellectual property. If you win the right to post work into open-source, the GitHub delete policy means that your host institution can over-ride this, and require you to take your code out of circulation. GitHub is great, but for the sake of preservation, SourceForge has the right policy, protecting your decision to go open source from later manipulations by your host institution when it becomes "valuable".

Casey Bergman's response to this issue has been to create the Bioinformatics Archive on GitHub. This is based on the idea used by the journal Computers & Geosciences, in which the journal editor forks the GitHub code into a journal "organization" for all accepted papers — this creates a permanent repository, which is necessary because deleting a private GitHub repository will delete all forks of the repository but deleting a public repository will not do so. So, Casey has been personally forking the code for all publications that come to hand (currently 147 repositories) into the Bioinformatics Archive, thus creating a public repository for all of the relevant GitHub code.

However, this is clearly a stopgap measure. Dave Lunt, at the EvoPhylo blog, has listed three desiderata for a more permanent solution to the issue (How can we ensure the persistence of analysis software?):

• A publisher driven version of the Bioinformatics Archive; journals should have a policy for the hosting of published code in a sustainable and accessible archive in a standardized manner
• Redundancy to ensure persistence in the worst case scenario; archive persistence is the key requirement, and this can only happen in public repositories, with the published URL and/or DOI pointing to a public copy of the code
• The community to initiate actual action; authors need to pressure the publishers to adopt a Dryad-like strategy, in which a large group of ecology and evolutionary biology journals agreed to require the use of a public database for storing the biological data associated with their publications.

At a minimum, a persistent public repository is a snapshot of the code at the time of publication, just as a sequence alignment is a snapshot of the processed data at the time of its publication. This does not preclude further work on the code, and further publications based on the newly modified code, just as new sequence alignments can be created by adding newly acquired sequences. Open-source code can still be newly forked, and there can be user-contributed updates and public issue tracking. Multiple snapshots of code related to different publications through time is not necessarily an issue, but it will need to be handled in some sensible manner.

The main reason for requiring the public archiving of code is to deal with the all-too-common situation when code is no longer being maintained (the scholarship ran out, the grant ended, the author retired, etc). For example, Jamie Cuticchia & Gregg Silk (2004, Bioinformatics needs a software archive, Nature 429: 241) mention the loss of part of the code when the multi-million dollar Genome Database lost funding in 1998. These two authors seem to be the first to have proposed a Bioinformatics Software Archive, "in which an archival copy of bioinformatics software would be maintained in a secure central repository supported by public funding." Personal and institutional homepages are too ephemeral (suffering what is known as URL decay) and too prone to politics to be considered acceptable for the storage of data and software in high-quality science.

More datasets for validating network algorithms

Ten more datasets have been added to the Datasets blog page. These are:

• 2 plant studies where hybrids are known from experimentation
• 3 more plant studies where natural hybrids are known
• 5 studies (fungi, plants, protozoa, viruses, animals) where recombination is known.

A comment

It is worth noting something that has become obvious to me while compiling these datasets — the mathematical model often applied to hybridization networks cannot easily be applied to many of the datasets collected by biologists. The usual mathematical model involves incompatibility between two or more trees for the same set of taxa, for example from different genes or genomes. The incompatibilities are resolved by postulating one or more reticulations in the network.

However, the data produced by biologists often involve only a single nuclear gene, most frequently the Internal Transcribed Spacer region, so that the biologists do not have multiple trees. Instead, hybrids are detected by additive polymorphisms at alignment positions within the study gene. These polymorphisms arise either from (i) the polyploid nature of the hybrids (there are multiple copies of each chromosome, each of which may have a gene copy from either parental species), or (ii) from multiple paralogous copies of the genes (the rRNA region, which contains the ITS, usually has many tandemly repeated copies of the genes, which are homogenized by concerted evolution, but in a hybrid any of them may have a gene copy from either parental species).

This means that it is difficult to use any current evolutionary network for the phylogenetic analysis of many of the datasets used for detecting hybridization. In turn, this suggests that we may need a different model, one based on additive polymorphisms rather than incongruent trees.

The usual mathematical model for lateral-transfer networks is actually the same as for hybridization networks, since the only real difference between HGT and hybridization is that HGT does not occur via sexual reproduction while hybridization does. (Also, hybridization often involves whole genomes while HGT usually involves partial genomes.) Importantly, the mathematical model does seem to apply to the sort of datasets collected by biologists when they are studying HGT. That is, HGT is detected by incompatibility between two or more trees for the same set of taxa. Indeed, this model is usually the only evidence for HGT, unlike hybridization and recombination where there is often evidence that is independent of the network model.

Datasets for validating algorithms for evolutionary networks

Steven Kelk has previously raised the issue about Validating methods for constructing evolutionary phylogenetic networks: there are currently not many options for validating the biological relevance of methods for constructing evolutionary phylogenetic networks. These are phylogenetic networks intended to represent evolutionary history, such as HGT networks. hybridization networks, and recombination networks.

Thus, we need 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 could then be used as a framework for validating the output of algorithms for constructing evolutionary phylogenetic networks.

This issue was discussed at some length at the Workshop: The Future of Phylogenetic Networks. It was suggested by Leo van Iersel that a practical starting point would be to use this blog as a link to suitable datasets. As people become aware of such datasets, a blog post would be published with the details, and the dataset would be linked from one of the blog Pages.

This page now exists (Datasets), and can be accessed at the top right of each blog page. Everyone is encouraged to contribute to this "database", which you can do by sending details about potential dataset  to me by email.

In another post, What should a database of datasets look like?, I have noted that there have been four suggested approaches to acquiring datasets for evaluating algorithms (in order of increasing reality):

1. simulate datasets 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 reticulation events have been independently confirmed
4. experimentally create taxa with a known evolutionary history.

It seems unnecessary to store datasets of type (1), since they can be created to order by computer programs. Datasets of type (2) are rare, but would be suitable for the database.

Datasets of type (4) currently exist for tree-like evolutionary histories but not yet, as far as I know, for reticulated histories. I have added the known (and available) ones to the database.

Datasets of type (3) are likely to form the bulk of the database, and I have started this part of the database with some example datasets involving hybridization.

For the latter datasets, it is important to note the potential problem of the degree to which the postulated reticulation events have been independently confirmed. I suspect that only weak evidence has been applied to far too many datasets. This is particularly true for those involving horizontal gene transfer (HGT), where mere incongruence between genes is presented as the sole "evidence". More than this is required (see Than C, Ruths D, Innan H, Nakhleh L. 2007. Confounding factors in HGT detection: statistical error, coalescent effects, and multiple solutions. Journal of Computational Biology 14: 517-535.).

GPWG Poaceae dataset

In a previous post, Steven mentioned that one of the datasets from the Grass Phylogeny Working Group has played an unexpectedly prominent role in evaluation of hybridization network algorithms.

These algorithms work by trying to construct a network from a set of rooted trees with overlapping sets of taxa; and the GPWG dataset provides six such trees, one from each of six different molecular loci. This dataset seems to have been introduced into the network literature by Bordewich et al. (2007), although it had previously been used for evaluations of supertree methods (Salamin et al. 2002; Schmidt 2003).

The data used consist of DNA sequences of three nuclear loci and three chloroplast genes. The original publication also has data provided for morphology and restriction sites, but these have not been used for the network analyses. One reason for interest in this dataset is the possibility of reticulation signals between the nuclear and chloroplast data sources. There are 66 taxa, although nearly half of them are composites formed from data for several different species in the same genus, and only a few of the taxa have data for all six datasets (the number of taxa varies from 19-65 per dataset). The data available are summarized in Table 7.1 from Schmidt (2003).

An important point about these data is that in the original GPWG publication the six gene trees were strict consensus trees from maximum-parsimony analyses, and so they have quite a number of polychotomies. These polychotomies were intended by the authors [personal communication] to express uncertainty about the topologies of the trees.

However, this uncertainty is not shown in the trees that have been used for network evaluation. According to Bordewich et al., the trees that they (and everyone else) used were reconstructed using the fastDNAmL program (ie. maximum-likelihood), and were supplied by Heiko Schmidt (see Schmidt 2003, p.74). As expected, there are no polychotomies in these ML trees and no indication of uncertain topology; and, of course, the tree topologies are somewhat different from the parsimony trees.

An important consequence is that there is more incompatibility among the dichotomous maximum-likelihood trees than there is among the polychromous maximum-parsimony trees. That is, many of the ML incompatibilities are related to uncertainties in the MP trees. Unfortunately, most of the network algorithms that have been evaluated using these data require strictly dichotomous trees.

Also, the root seems to create problems for these data. The GPWG trees are all rooted with this topology:
  (Flagellaria,((Elegia,Baloskion),(Joinvillea,((Streptochaeta,Anomochloa),(Pharus,(ingroup))))))
However, the position of this 7-taxon outgroup relative to the rest of the taxa varies among the gene trees. That is, the connection between the outgroup and the ingroup differs between the gene trees. So, some of the incompatibility among the trees is created by an uncertain root, rather than by conflicting signals due to reticulation processes.

Some of the ML datasets available have trees with the same set of ingroup / outgroup relationships as the GPWG trees, for example those datasets available with the CASS algorithm. However, some of the ML trees presented in the literature seem to be rooted in quite a different place, and this place differs between the gene trees. For example, the data as presented with the HybridInterleave program, which is presented as 15 pairs of subtrees rather than as six complete trees, not only are the the gene trees apparently rooted in different places but the different subsets presented of the same gene tree are also sometimes rooted in different places.

It seems to me that there are two consequences arising from these points: (i) it is unnecessarily hard to construct a network from the ML data (because not all of the data signals relate to reticulation), and (ii) the resulting networks (as published) look rather unrealistic to a biologist (there are far too many reticulation nodes). Perhaps this isn't the most realistic dataset to be using for the evaluation of network algorithms.

Another commonly used dataset is the Ranunculus data from Lockhart et al. (2001). In this dataset much of the incompatibility signal also seems to be associated with an uncertain position for the root (see Morrison 2011, Fig. 4.7). In this case there are two gene trees (one nuclear and one chloroplast) that have similar unrooted topologies but have different outgroup-derived root locations. Dealing with root uncertainty may thus be one of the biggest confounding problems when trying to identify reticulation events.

The original GPWG data are available at:
http://www.eeob.iastate.edu/faculty/profiles/ClarkL/GPWG-2001-Appendices.pdf

The nexus data matrix is available at:
http://www.umsl.edu/services/kellogg/gpwg/matrix.html
[In this dataset, 0=A, 1=C, 2=G, 3=T]

A nexus treefile with the original six GPWG (consensus parsimony) trees is available at:
http://acacia.atspace.eu/data/GPWG.tre

A dendroscope treefile with the six ML trees is available at:
http://sites.google.com/site/cassalgorithm/data-sets

References

Bordewich M., Linz S., St. John K., Charles Semple C. (2007) A reduction algorithm for computing the hybridization number of two trees. Evolutionary Bioinformatics 3: 86-98.

Grass Phylogeny Working Group (2001) Phylogeny and subfamilial classification of the grasses (Poaceae). Annals of the Missouri Botanical Garden 88: 373-457.

Lockhart P., McLechnanan P.A., Havell D., Glenny D., Huson D., Jensen U. (2001) Phylogeny, radiation, and transoceanic dispersal of New Zealand alpine buttercups: molecular evidence under split decomposition. Annals of the Missouri Botanical Garden 88: 458-477.

Morrison D.A. (2011) Introduction to Phylogenetic Networks. RJR Productions, Uppsala.

Salamin N., Hodkinson T.R., Savolainen V. (2002) Building supertrees: an empirical assessment using the grass family (Poaceae). Systematic Biology 51: 136-150.

Schmidt H.A. (2003) Phylogenetic Trees From Large Datasets. PhD thesis, Heinrich Heine University, Düsseldorf.

Wu Y. (2010) Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees. Bioinformatics 26: i140-i148.

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