Candy Crush network

King Digital, the creators of the popular smartphone game Candy Crush Saga were listed on the New York Stock Exchange two days after this game was shown to be NP-hard [1]. Could these two events be somehow related? Anyway, although the King Digital shares are not doing well, the NP-hardness proof still stands. A different NP-hardness proof for Candy Crush actually appeared on the arXiv a few weeks earlier [2], but was based on rules that are slightly different from the usual rules of Candy Crush.

So what is Candy Crush? It is a smartphone / tablet game having a rectangular board filled with different types of candies. A player can score points by swapping two adjacent candies in order to match three or more candies of the same type. This seems to be even more addictive than eating candies, which made the game the most popular game of Facebook, and led to a 568 million dollar profit for King Digital in 2013.

Interestingly, Candy Crush Saga is one of a large family of games that are all based on matching objects. These games all seem to be closely related. Moreover, their genealogy is not tree-like at all, as shown below. Many modern games have been derived by combining ideas from different older games. In other words, the genealogy of such games can best be described by a phylogenetic network.

A phylogenetic network for Bejeweled-type games, taken from [1], which was in turn taken (after modification) from [3].

This network is clearly a rooted, genealogical phylogenetic network (although it does not have a unique root).

So what does the NP-hardness of Candy Crush tell us? Nothing, of course, except that the 97 million people daily playing Candy Crush are pouring all their energy into solving a frivolous, but nevertheless intrinsically hard, problem. This is a pity because, since Candy Crush is NP-hard, one can (at least in theory) encode any NP-complete problem as a Candy Crush episode. This could be used to let all these 97 million people solve more useful NP-complete problems every day. For example, we could encode massive phylogenetic network reconstruction problems as Candy Crush episodes, and use this to construct the Web of Life in a few days!

References

[1] Luciano Gualà, Stefano Leucci, Emanuele Natale. Bejeweled, Candy Crush and other match-three games are (NP-)hard, http://arxiv.org/abs/1403.5830 (24 March 2014)

[2] Toby Walsh. Candy Crush is NP-hard, http://arxiv.org/abs/1403.1911 (8 March 2014)

[3] Jesper Juul. A casual revolution: reinventing video games and their players. The MIT Press, 2012.


Later note:
It turns out that the figure shown above is not actually taken from [3], in spite of the claim made in [1]. The figure in [3] is re-drawn from [4], and the genealogy as shown in [1] is edited directly from [4], not [3]. The editing consists of deleting all of the many other descendants of Tetris. The original complete figure is available here.

[4] Jesper Juul. Swap adjacent gems to make sets of three: a history of matching tile games. Artifact 1: 205-216, 2007.

Tutankhamun and extreme consanguinity

Consanguineous relationships involve people who are first cousins or more closely related. Apparently, about 15 percent of all marriages worldwide involve consanguineous partners, although this number has been higher in the past (Bittles 2012).

Our interest for this blog is that such relationships emphasize that so-called family trees (pedigrees) are hybridization networks not trees (see Pedigrees and phylogenies are networks not trees). Everyone can trace their maternal and paternal ancestors back into the past to a point where the lineages fuse again, and consanguineous marriages mean that this happens in the recent past rather than the distant past. To this end, we have had posts about Charles Darwin (Charles Darwin's family pedigree network), Henri Toulouse-Lautrec (Toulouse-Lautrec: family trees and networks) and Albert Einstein (Albert Einstein's consanguineous marriage). Not unexpectedly, it is royalty that provide the best-known examples (see Family trees, pedigrees and hybridization networks).

However, many cultures have taken consanguinity even further, as noted by Dobbs (2010):

While virtually every culture in recorded history has held sibling or parent-child couplings taboo, royalty have been exempted in many societies, including ancient Egypt, Inca Peru, and, at times, Central Africa, Mexico, and Thailand [and also Hawaii].

The reference to ancient Egypt includes both Cleopatra and Tutankhamun, each of whom was part of a dynasty that apparently adopted the practice of incest. As noted by Wikipedia:

In ancient Egypt, royal women carried the bloodlines and so it was advantageous for a pharaoh to marry his sister or half-sister; in such cases a special combination between endogamy and polygamy is found. Normally the old ruler's eldest son and daughter (who could be either siblings or half-siblings) became the new rulers.

Tutankhamun

Tutankhamun briefly ruled as Pharaoh from 1333-1323 BCE, at the end of the Amarna period, the 18th Dynasty. His failure to leave an heir ended the direct line of succession, and ultimately resulted in the transition to the 19th Dynasty, started by Rameses I. Tutankhamun seems to have been a rather minor king, becoming ruler at age 9 and dying at 19. He was surrounded by the power struggle that resulted from his father's attempt to found the first monotheistic religion, and being a minor he probably had little influence on the events of the time (Antanovskii 2013).

He became famous in 1922, when his near-intact tomb was discovered. He had been buried in a tomb not intended for royalty, and its location and even existence was quickly forgotten at the time — due to the political turmoil, his successors had deleted nearly all traces of the Amarna kings. In a classic case of irony, this situation made Tutankhamun's tomb safe from the robbers who removed much of the contents of other tombs in the Valley of Kings. Thus, more than 5,000 artifacts were found in his tomb, along with the well-preserved mummies (see the death mask pictured above). This has made Tutankhamun a better-known name ("King Tut") than that of anyone else from his period.

A note on names: Tutankhamun's father was Amenḥotep IV, who tried to replace the polytheistic worship associated with Amun (or Amen) and the other gods of the national pantheon with the monotheistic worship of Aten ("the disk of the sun"). He thus changed his name from Amenhotep ("Amun is satisfied") to Akhenaten ("beneficial to Aten"). His son was named Tutankhaten ("the living spirit of Aten"), but this was changed to Tutankhamun ("the living spirit of Amun") when the state religion was restored during his reign.

The history of the period surrounding Akhenaten and Tutankhamun is particularly confused, as Tutankhamun did not become pharaoh until 2 years after his father's death (Hawass 2010; Gabolde 2011). Nevertheless, the preservation of Tutankhamun's tomb has allowed us to reconstruct a possible genealogy for this period, as shown next.

Hawass et al. (2010) compared the DNA of the mummy of Tutankhamun with that of 10 royal mummies from the same period, ranging from 1,410 to 1,324 BCE. The mummy of the genetically identified father, found in grave No. 55 of the Valley of Kings, is considered to be Akhenaten. The identified mother, found in grave No. 35, was also identified to be the sister of Akhenaten. This is surprising, because only two wives of Akhenaten, Nefertiti and Kiya, are known to have had the title of Great Royal Wife, which the mother of the royal heir should bear.

Hawass et al. (2010) also looked for evidence of possible genetic effects of the consanguineous relationship (eg. homozygous genetic disorders):

An accumulation of malformations in Tutankhamun's family was evident. Several pathologies including Köhler disease II were diagnosed in Tutankhamun; none alone would have caused death. Genetic testing for genes specific for Plasmodium falciparum revealed indications of malaria tropica in four mummies, including Tutankhamun's. These results suggest avascular bone necrosis in conjunction with the malarial infection as the most likely cause of death in Tutankhamun. Walking impairment and malarial disease sustained by Tutankhamun is supported by the discovery of canes and an afterlife pharmacy in his tomb.

Incestuous marriages were nothing new to the pharaohs of Dynasty 18 (see Ian Mladjov's detailed genealogy). Part of the genealogy of its founding is shown in the next figure. Aahotep I and Sequenenra III were sister and brother, as were Aahmes-Nefertari and Aahmes (or Ahmose II). Aames (or Ahmose III) and Thotmes I were either sister and brother or half-siblings (the records are unclear).

Circles refer to females and squares to males.

Finally, it is worth noting that Marc Gabolde has an alternative explanation for the apparent genetic closeness of King Tutankhamun's parents (see Powell 2013). He suggests that Tutankhamun's mother was not his father's sister, but rather his father's first cousin, Nefertiti. The apparent genetic closeness is then not the result of a single brother-sister mating but due to three successive instances of marriage between first cousins. Nefertiti is recorded to have had six daughters with Akhenaten, but no son.

References

Antanovskii R (2013) Unmasking Tutankhamun : the figure behind the fame. Heritage Daily – Archaeology.

Bittles AH (2012) Consanguinity in Context. Cambridge University Press.

Dobbs D (2010) The risks and rewards of royal incest. National Geographic Magazine.

Gabolde M (2011) The end of the Amarna Period. BBC History – Ancient History in Depth.

Hawass Z (2010) King Tut's family secrets. National Geographic Magazine.

Hawass Z, et al. (2010) Ancestry and pathology in King Tutankhamun's family. Journal of the American Medical Association 303: 638-647.

Ian Mladjov's Genealogical Tables — The pharaohs of the New Kingdom in Egypt c. 1540-1070 BC.

Powell A (2013) A different take on Tut. Harvard Gazette.

Trees, treemaps and networks

Hierarchically arranged information has traditionally been represented as a tree. However, this is not the only way that this information can be pictured. As noted by Manuel Lima (Visualization Metaphors: Old & New):

As one of the most hailed methods of modern information visualization, the treemap has truly become an epitome of the recent growth of the field and one of the most widespread methods for visualizing hierarchies.

Isabel Meirelles (Design for Information: An Introduction to the Histories, Theories, and Best Practices Behind Effective Information Visualizations. Rockport Publishers, 2013) provides this illustration as an example of the different ways to represent hierarchies:

So, treemaps display the tree information as a set of nested rectangles — each branch of the tree is given a rectangle, which is then tiled with smaller rectangles representing sub-branches. The main advantage of using a map as a representation is that the size and colour of the rectangles can be used to represent other information about each tree leaf. (Note: This treemap concept should not be confused with Mike Charleston's program TreeMap, which maps the relationships between two phylogenetic trees, nor with MLTreemap, which maps an unidentified DNA sequence onto a phylogenetic tree.)

Modern treemaps were developed in 1991 by Ben Shneiderman, who has conveniently provided a description of the history and initial development of the idea (Treemaps for space-constrained visualization of hierarchies). Not unexpectedly, this idea has been adopted in biology. For example, taxonomic hierarchies are sometimes represented using a treemap, such as in BioNames (which displays the taxonomic groups recognised by the Index to Organism Names database), and the Natural Science Museum of Barcelona (which allows interactive access to the database records via a taxonomic hierarchy). It has also been used to display the gene ontology associated with gene expression data from microarray studies (Visualization and analysis of microarray and gene ontology data with treemaps).

In addition, it has been suggested that treemaps could be used to represent phylogenetic trees (Using treemaps to visualize phylogenetic trees. 6th International Symposium on Biological and Medical Data Analysis, 2005. Lecture Notes in Computer Science 3745: 283-293); and there is an associated computer program. An example is shown below, in which the rectangles are coloured by their taxonomy — the circles highlight two sequences that are misplaced in the tree (ie. their tree location does not match their taxonomy).

This approach to displaying phylogenies has not really caught on (ie. phylogeneticists have stuck to the "node-link" layout). The treemap approach works best with a fixed-level hierarchy, such as the taxonomic hierarchy or the gene ontology hierarchy. In phylogenetics, on the other hand, branch lengths are variable, so that there is no fixed-level hierarchy. Treemaps work well for displaying information about groups that might be recognized in the tree, but not for the tree itself.

Nevertheless, similar methods were suggested long before the invention of computers (two early examples are noted by Manuel Lima, in the blog post linked above). Indeed, we end up with a treemap if we simply cut slices out of the tree, as shown by the next picture (taken from Isabel Meirelles' book), which shows Maximilian Fürbringer's tree of bird relationships from 1888 (published in Untersuchungen zur Morphologie und Systematik der Vögel). On the left is the side view of the tree, and on the right are three slices through the tree branches (as viewed from above). This produces a circular treemap rather than a rectangular one, which is admittedly a less efficient use of the visualization space.

Finally, we can consider the relationship of these ideas to phylogenetic networks. A network is not a nested hierarchy, but instead involves a collection of over-lapping sets. This can be represented as a venn diagram, for example, but not as a treemap. This form of visualization has also been a long-standing suggestion in phylogenetics. The final picture shows Georg August Goldfuss' "system of animals" from 1817 (published in Ueber de Entwicklungstufen). It is a set of nested egg-shaped sets, expressing his ideas about affinity relationships, with one set over-lapping several of the others, representing a non-nested series of relationships. There is nothing new under the sun!

Pedigrees and phylogenies are networks not trees

There is nothing in the etymology of the words 'genealogy' and 'phylogeny' that necessarily implies that they must be tree-like. Indeed, all genealogies are networks. For example, a human family "tree" is a tree only if it includes one sex alone. Otherwise, it must be a network when traced backwards from any single individual through both parents, because the lineages must eventually coalesce in a pair of shared common ancestors. This must happen if there is a single origin for Homo sapiens (ie. the species is monophyletic). The coalescence may not occur for thousands of years in the past, or it may be quite recent.

So, all pedigrees of sexually reproducing species involve conjoined lineages at both "ends", one in the common ancestor and one in the contemporary offspring.

Given the extent of inbreeding among royal families, this ancestral coalescence is quite likely to be recent among monarchs. For example, the most recent common ancestors of all of the currently reigning monarchs of Europe are John William Friso, Prince of Orange (1687-1711), and his wife, Marie Louise of Hesse-Kassel, Princess consort of Orange (1688-1765). This situation has existed since the abolition of the Albanian monarchy in 1939 (this particular monarchy was not related to the house of Orange).

Marie Louise (left) and her two children.

There used to be a Wikipedia page listing the contemporary descendants of this royal Dutch couple, but it has been deleted. It is, however, still available in the Internet Archive WayBack Machine (Royal descendants of John William Friso, Prince of Orange). This page shows that the lineages of all of the current monarchs coalesce in this couple in 7-11 generations. This is true of all 10 current monarchs (in Belgium, Denmark, Liechtenstein, Luxembourg, Monaco, the Netherlands, Norway, Spain, Sweden, the United Kingdom), many former monarchies (13 or so), many so-called pretenders or claimants (at least 21), plus two royal consorts. Interestingly, the progenitor couple achieved this set of family relationships even though they had only one daughter (Princess Amalia of Nassau-Dietz) and one son (William IV, Prince of Orange), who was born six weeks after his father's death by drowning.

Family trees were originally devised as a way for nobles to assert their nobility, by tracing their direct male ancestry from some "important" progenitor (see the picture below). The female lineages were usually ignored in such ancestries, with each woman appearing alone, solely as an isolated wife and mother. This was, of course, modelled on the genealogies listed in the christian Bible, in both Genesis 5 and 11, in which females are mentioned but only males appear to be named. However, the ancestral relationships of the current European monarchs do involve females as part of the direct lines of descent, in all cases (ie. none of the direct lines of descent can be traced solely through males).

On the left is part of a genealogy of Christ (from c. 1130-1205);
on the right is a genealogy of the House of Habsburg (c. 1540).
Reproduced from the Visual Complexity blog.

Thus, in the modern world, we should be constructing family networks not family trees, with all of the male and female lineages sharing equal prominence. This will make it clear that genealogies are networks not trees. This assumes, of course, that enough historical information can be collected to locate the actual points of coalescence. This is unlikely to be so for the likes of you and me, but the nobility seem to be able to do it quite regularly.

Family networks that reticulate within a few generations are not necessarily good things, of course. Sex-linked recessive traits such as heamophilia B are widespread among the royalty of Europe (Stevens 1999, Rogaev et al. 2009), as are autosomal dominant traits such as variegate porphyria (Cox et al. 2005). These diseases are much rarer amongst commoners.

A similar situation applies to phylogenies showing species relationships. If there is a single origin to life, then tracing phylogenies backwards in time must lead to the eventual coalescence of all lineages. Any species whose ancestry involves hybridization, introgression or horizontal gene transfer must form a network. Parts of this network might be tree-like if isolated from the rest, but the whole phylogeny cannot be anything other than a network.

Consider the following points:

Definitions:
A network is a series of overlapping groups
A tree is a set of nested groups

Observation:
Each evolutionary event defines a group (all of the descendants of the ancestor in which the event occurred)

Conclusions:
Dichotomous speciation leads to a tree, by definition
Other processes will lead to a network, by definition

We know that in biology there are both vertical (speciation) and horizontal (reticulation) evolutionary processes. Therefore, no biological data fit a tree perfectly (unless the data are carefully selected to do so). A network analysis will allow you to evaluate the relative contribution of the horizontal and vertical processes that have occurred.

References

Cox TM, Jack N, Lofthouse S, Watling J, Haines J, Warren MJ (2005) King George III and porphyria: an elemental hypothesis and investigation. Lancet 366: 332-335.

Rogaev EI, Grigorenko AP, Faskhutdinova G, Kittler ELW, Moliaka YK (2009) Genotype analysis identifies the cause of the "Royal Disease". Science 326: 817.

Stevens R. (1999) The history of hemophilia in the royal families of Europe.  British Journal of Haematology 105: 25-32.

The Netherlands is more than just tulips and sea-dykes

When I look out the window of my workroom at home, several minutes can easily pass without a person being in view. This is quite typical of Swedish countryside. During the times I have been in the Netherlands, however, I have never experienced even one whole minute without a person walking, or more likely cycling, into view. The Netherlands is the most densely populated country in Europe (excluding all of the really tiny countries), with about 500 people per square kilometre of actual land area.

In spite of this, the Netherlands, according to the Statistics Division of the United Nations, managed to be the largest worldwide exporter and re-exporter of fruit and vegetables (including citrus) between 2009 and 2012. The data show that the Netherlands handled 14.6% of the world's total, followed by Spain (12.1%), China (10.9%), Mexico (9.7%), the United States (8.3%), Canada (5%), France (4.4%), Belgium (3.7%), Italy (2.8%) and Germany (1.9%).

Given this unexpected fact, it seems worthwhile to list some of the other facts about the Netherlands that I bet you never knew. Many of the data come from the Eurostat database and the Statistics Netherlands database, but also from miscellaneous other sources on the web.

Bulb season at the Keukenhof Gardens, in the Netherlands.

In this period the Netherlands exported 4,600 million kilograms of vegetables with a market value of 4,200 million Euros. It is worth noting that a considerable amount of the export is actually re-export, particularly of products imported from south-east Asia. Nevertheless, about 24,000 hectares of the Netherlands is devoted to vegetables in total, plus about 19,000 ha dedicated to fruit.

Hardly anyone realizes that the Netherlands is the world’s biggest producer of onions, with 1,353,000 tonnes in 2012. For comparison, Spain produced only 1,169,700 tonnes. The Netherlands is also the leading exporter of button mushrooms (40% of the export market) followed by China, France, Spain, Hong Kong, Taiwan, Indonesia and South Korea. The U.S.A. is the largest consumer, accounting for one third of World production.

The Dutch are the biggest exporters of seed in the world, exporting some 1,500 million Euros worth every year. About 15,000 hectares of land is given over to nurseries and perennial plants, and about 3,000 ha to floricultural crops. Much of the horticultural production is under glass (c. 10% of the area). For example, within the European Union, Spain has about 65,000 hectares of commercial glasshouses, and Italy has c. 35,000 ha; but the Netherlands is third, with c. 10,000 ha.

However, it is bulbs for which the Netherlands is most famous, both as cut flowers and as whole plants. The Netherlands has 86% of the world area for tulip production, with about 10,800 hectares. It also has about 75% of the lily production area (4,280 ha), out of a Dutch total of 23,500 hectares devoted to bulbs. Sales total 1,320 million tulip bulbs per year (1,300 million as cut flowers) out of a world total of 4,320 million (2,300 million as cut flowers).

Tulip season in South Holland. Note the line of tourist camper vans.

The introduction of the tulip to Europe is usually attributed to Ogier de Busbecq, who sent the first tulip bulbs and seeds to Vienna in 1554 from Turkey in the Ottoman Empire. The Turks still tell the story of the first recipients trying to fry and eat the bulbs, rather than growing them! Tulip popularity and cultivation in the Netherlands probably dates from 1593, when the Flemish botanist Carolus Clusius planted his collection of tulip bulbs at the Hortus Botanicus in Leiden. To this day, the area immediately north of Leiden is the heart of the Dutch bulb industry (see the picture above).

However, in spite of all of this plant production, most of the farmland in the Netherlands is actually given over to animals, not plants. Only about 30% of the farmland is dedicated to plants, while 56% is reserved for grazing livestock, as shown in the next graph.

Annual area of Dutch farmland this century. Note the log scale.

Given all of this primary production, it is not unexpected that the Netherlands has the best balance of trade for raw materials within the European Union, with a surplus of 4,500 million Euros per year (see the first network below). This is followed by Sweden (3,000 million). The only other EU countries with a positive balance are Denmark, Latvia, Romania, Ireland and Estonia. Last are Italy and Germany, each with a deficit of -12,000 million Euros per year.

NeighborNet (based on manhattan distance) of the 2001-2012 data for international trade of raw materials
for the member countries of the European Union. Countries near each other in the network have a similar
balance of trade, while countries further apart are progressively more different from each other.

Furthermore, the Netherlands has the second best overall balance of trade (i.e. including manufacturing) in the European Union, with a surplus of 37,000 million Euros per year (see the next network). This is way behind Germany (153,000 million), but just ahead of Ireland (35,500 million). The only other countries to have consistently had a positive balance of trade this century are Sweden, Belgium and Denmark. The United Kingdom has fared much the worst, with a deficit of -116,000 million Euros per year.

NeighborNet (based on the manhattan distance) of the 2001-2012 data for total international trade
for the member countries of the European Union.  Countries near each other in the network have a similar
balance of trade, while countries further apart are progressively more different from each other.

The Netherlands is also famous for having 50% of its alleged land area less than 1 metre above sea level (see the map below); and indeed 20% of the land is actually below sea level. Throughout the latter region, the water flows uphill into the rivers and canals, a feat that is not usually achieved anywhere else on the planet. This has traditionally been accomplished with windmills, of course.

This situation has occurred because during the first millenium AD much of the land was washed out into the North Sea, and during the second millenium the Dutch tried to get it back again. In particular, Lake Flevo became the South Sea, and was then reclaimed as Lake IJssel. These days, rather massive sea-dykes are used to keep the water at bay.

The Netherlands with respect to the Amsterdam Ordinance Level (NAP).

So, where are the Dutch managing to do all of this agricultural production? I suspect that the creators of Dr Who invented the Tardis after a visit to the Netherlands, since clearly the Netherlands is larger on the inside than it appears to be on the outside.

The Phylocode and reticulation

Biologists have this idea that when any of us uses a formal name then we should all be talking about the same thing. To this end, various cods of nomenclature have been proposed and agreed to over the centuries, notably those based on hierarchical ranking (eg. International Code of Nomenclature for Algae, Fungi, and Plants; International Code of Zoological Nomenclature; International Code of Nomenclature of Bacteria; International Code of Nomenclature for Cultivated Plants). Others have not been universally agreed to, and are not yet being used (eg. BioCode; PhyloCode).

Of the latter group, the Phylocode is not dead, but it is certainly hibernating. As explained by Mike Keesey (The PhyloCode Has a Deadline ):

The PhyloCode (more verbosely, the International Code of Phylogenetic Nomenclature) is a proposed nomenclatural code, intended as an alternative to the rank-based codes. It was first drafted in April 2000, and at that time the starting date was given as "1 January 200n". On this date the code would be enacted and published along with a companion volume, which would provide the first definitions under the code, establishing best practices and defining the most commonly used clade names across all fields of biology.

Well, the '00s came and went without the code being enacted. The hold-up was not the code itself, which has been at least close to its final form since 2007. (The last revision, in January 2010, was minor.) And it hasn't been the software for the registration database, which has been completed. The hold-up was the companion volume, which turned out to be a much more daunting project than expected.

There is a new progress report for Phylonyms, the companion volume to the PhyloCode. There will be at most 268 entries. Currently 186 of those (over two thirds) have already been accepted. The rest are at various stages of review. The contract with University of California Press calls for the manuscript to be submitted by September 1, 2014.

Reticulation

Of interest to us here at this blog is how the Phylocode treats reticulate evolution. In the rank-based nomenclatural codes (eg. ICN, ICZN), reticulate evolution is ignored. Each named group at any given rank is mutually exclusive, so that each taxon can be part of only one of the named groups. This naming scheme can be used to represent hierarchical relationships but not reticulate ones.

With regard to the Phylocode, Philip Cantino explicitly addressed this issue at the Botany 2008 conference (The taxonomic treatment of hybrid derivatives under the ICBN and the PhyloCode):

By convention, ranked taxa must be either nested or mutually exclusive, but clades that include species of hybrid origin may be partially overlapping. Consequently, reticulate evolution presents a challenge for phylogenetic systematists using traditional rank-based taxonomy and nomenclature, where a species can belong to only one taxon at a given rank. Assignment of a species derived from an intersectional (or intersubgeneric or intergeneric) hybrid to only one of its parental sections (or subgenera or genera) renders the other parental taxon at the same rank paraphyletic. When classifying such hybrids using a ranked hierarchy, one must reject either the convention that an organism can only belong to one taxon at a given rank or the convention that paraphyletic groups should not be formally recognized. Phylogenetic nomenclature accurately reflects the complex patterns of descent that result from hybridization, in that a species of hybrid origin belongs to all of the named clades that contain each of its parents. Thus, the expectation that named supraspecific taxa be monophyletic is maintained in spite of hybridization.

Putting aside the obvious suggestion that we could allow named groups to be paraphyletic (which they can be under the rank-based codes but not the Phylocode), the suggestion that organisms can belong to more than one named group (which they can under the Phylocode but not the other codes) is an interesting departure from tradition. It explicitly recognizes the existence of fuzzy groups, which can overlap.

Phylocode

The Phylocode has little to say explicitly about reticulation, but what it does say is clear:

Note 2.1.3. Clades are often either nested or mutually exclusive; however, phenomena such as speciation via hybridization, species fusion, and symbiogenesis can result in clades that are partially overlapping.

Note 2.2.1. Here and elsewhere in this code, "phylogenetic tree" is used loosely to include any directed graph, specifically those with additional connections representing phenomena such as hybridization (see Note 2.1.3).

Note 9.3.2. The application of a phylogenetic definition, and thus also of a phylogenetically defined clade name, requires a hypothesized phylogeny. To accommodate phenomena such as speciation via hybridization, species fusion, and symbiogenesis (see Note 2.1.3), the hypothesized phylogeny that serves as the context for the application of a phylogenetically defined name need not be strictly diverging.

Chapter VI. Provisions for Hybrids
Article 16.
16.1. Hybrid origin of a clade may be indicated by placing the multiplication sign (×) in front of the name. The names of clades of hybrid origin otherwise follow the same rules as for other clades.
16.2. An organism that is a hybrid between named clades may be indicated by placing the multiplication sign between the names of the clades; the whole expression is then called a hybrid formula.
Recommendation 16.2A. In cases in which it is not clear whether a set of hybrid organisms represents a clade (as opposed to independently produced hybrid individuals that do not form a clade), authors should consider whether a name is really needed, bearing in mind that formulae, though more cumbersome, are more informative.

In many ways, the sentiments expressed here about phylogenetics are the same as those engendered in the recent announcement of the NSF Genealogy of Life program (GoLife) (see NSF and reticulating phylogenies) — a genealogy does not have to be tree-like.

Comments

In one sense, we should applaud the creators of the Phylocode for explicitly addressing an issue that has traditionally been ignored by the creators of the other codes (who have ignored phylogeny), as well as by tree-based phylogeneticists (who seem to think that phylogenies consist only of nested monophyletic groups).

Previous suggestions for dealing with hybrids look a bit like an attempt to sweep all of the problems together into separate piles, and then simply labeling them "problem piles" (see How should we treat hybrids in a taxonomic scheme?). This is very much what is done, for example, under the International Code of Nomenclature for Algae, Fungi, and Plants. Here, hybrids are treated as separate taxa, and are named as such using a "hybrid formula" that applies to distinct "nothotaxa".

Furthermore, species separately derived from the same ancestral gene pool are considered to be distinct species, and are named appropriately. However, hybrids derived independently from crosses of the same two species appear to be treated in botany as being the same taxon, and thus share the same name. For example, the ICN states: "Elymus ×laxus is the correct name applicable to all hybrids between E. farctus and E. repens" and "the correct nothospecific designation for all hybrids between Euphorbia amygdaloides and E. characias is E. ×martini". Multiple origins are not considered.

Unfortunately, while the Phylocode does better than this, the potential consequences of the Phylocode rules may be somewhat messy. For example, introgression is an extensive phenomenon in zoology and especially botany, and if we were to take the Phylocode literally then a huge number of populations would have multiple species names. Moreover, horizontal gene transfer creates relationships between distant taxa, so that species would have names in two unrelated groups (eg. an animal name and a viral name). Finally, symbiogenesis means that all of the eukaryotes would have both a eukaryote name and a proteobacterium name (since that is where their mitochondrion probably originated), and all of the plants would also have a cyanobacterium name (since that is where their chloroplast probably originated).

On one hand, fuzzy groups are a reality in phylogenetics, as a result of reticulate evolutionary histories. On the other hand, there is a good practical reason why the traditional codes of nomenclature are based on mutually exclusive groups. The only complete and accurate representation of group relationships is the phylogeny itself, and trying to name groups that represent only parts of the phylogeny is a poor substitute for that diagram. This is the dilemma faced by the Phylocode, that in practice it is trying to substitute names for relationships.

Which cars are good, really?

My wife and I recently bought a new old car (it is new for us, but it was 1 year old when we bought it). Being a scientist, part of the choosing procedure involved me trying to find out which cars in my price range might be recommended by their owners. There are several organizations who annually try to find out the same thing, and so I naturally had a look at some of their data. I thought that I might share some of the results with you.

I live in Europe, and so the two data sources that were of most interest are the Vi Bilägare AutoIndex survey, in Sweden, and the Auto Express Driver Power Survey, in the United Kingdom. Every year, these surveys ask car owners how they have fared recently with their near-new cars (up to 5 years old). For the data analyzed here, we are concerned solely with the data aggregated by manufacturer (rather than for individual car models).

For the analysis, I have chosen the data for the years 2011-2013 inclusive, because they were available from both organizations, and I rescaled the numbers to the common range 0-100. Several car manufacturers could not be included because of missing data from some years: Alfa Romeo, Chevrolet, Jaguar, Land Rover, Porsche, and Smart. That still leaves 25 manufacturers in the dataset.

As usual, I used the manhattan distance and a neighbor-net network to produce the graph. Car manufacturers near each other in the network have similar scores across the two countries and three years, while manufacturers that are further apart are progressively more different from each other.

The average scores vary from 77-88, going from Fiat (at the bottom of the graph) to Lexus (at the top). There is general agreement between the two surveys and the three years, with some notable exceptions.

For example, Skoda stands out in the network because it scores much better in the U.K. than in Sweden. On the other hand, Mini scores much better in Sweden than in the U.K., which explains its involvement in the only major network reticulation.

Nissan, Hyundai and Seat also score somewhat better in the U.K. than in Sweden, while BMW and Suzuki score better in Sweden; however, these patterns are not obvious in the network.

The gradient in scores from the top of the network to the bottom shows some interesting patterns. For example, the three French manufacturers are at the bottom of the graph (Citroën, Peugeot and Renault), along with the two American-owned companies (Ford and Opel / Vauxhall). The two Korean-owned manufacturers are together in the middle (Hyundai and Kia), while the Japanese-owned companies are scattered from top to bottom, along with the remaining European-owned companies.

Not unexpectedly, you pay for what you get. The makers of the most expensive cars are all gathered at the top of the graph (from Volvo and Audi upwards). However, the position of Saab and Volkswagen may surprise some people. Sadly, both manufacturers have a current reputation for designing excellent cars but building rather poor ones.

Finally, our motor mechanic recommended that we buy a Ford rather than a Kia. Clearly, the car owners do not agree with his assessment. Sadly, the car we were replacing was a Peugeot, and we completely agree that it deserves its location in the graph.

Recognizing groups in splits graphs

Splits graphs are produced by distance-based network methods such as NeighborNet and Split Decomposition, by character-based methods such as Median Networks and Parsimony Splits, and by tree-based methods such as Consensus Networks and SuperNetworks. They represent sets of node clusters that may overlap. If the clusters are nested then the graph will be tree-like, but if they overlap then the graph will show complex reticulation patterns. In the latter case, there is no simple way to summarize the patterns as a set of "groups" of nodes, although there is clearly a strong tendency in the literature for practitioners to try to do so.

I have written before about How to interpret splits graphs, in which the edges in the graph represent separation between two clusters of nodes in the network (ie. they split the graph in two). Recognizing groups of nodes should therefore be based on the splits. Ideally, each group of nodes should represent a split in the network, preferably a well-supported split.

However, if the split pattern is complex then recognizing groups of nodes will also be complex. This can be seen in the following splits graph, which is taken from the paper by Robert M. Ross, Simon J. Greenhill and Quentin D. Atkinson (2013. Population structure and cultural geography of a folktale in Europe. Proceedings of the Royal Society B 280: 20123065). The network shows the relationships among 32 ethnolinguistic cultures based on the characteristics of one of their folktales.

This network is not very tree-like, and yet the authors recognize five main ethnolinguistic groups (shown in different colors). Inspection of these groups reveals:

• The light-orange group represents a well-supported split in the graph, and is thus uncontroversial; but none of the other groups are represented by a single split.
• The pink group represents two splits, one clustering English, Irish, Scottish and Danish, and one clustering Danish, Latvian and German. These splits are incompatible with only one other minor split, and so the group is relatively uncontroversial.
• The green group also represents two splits, one clustering Armenian and Turkish and one clustering Turkish and Greek. These are well-supported splits, with only minor incompatibility with other splits, and so perhaps this group is also uncontroversial.
• The purple group is supported by a single split only if Greek is included in the group. Clearly, this conflicts with the green grouping. However, without Greek there is not much in the way of splits that support the purple grouping.
• There is a very poorly supported split that unites the dark-orange group only if Bulgarian and Czech are included in the group. There are three well-supported splits that combine to support the group provided that Bulgarian is included. In both cases this conflicts with the purple grouping.

So, at least two of the recognized groups can be considered doubtful, as groups, based on the network alone. The authors' motivation for their groupings is at least partially based on geographical considerations:

The NeighbourNet in figure 2 represents graphically the pattern of regional clustering in folktale variation. The five clusters we identify provide insights into possible cultural spheres of influence in Europe since the folktale’s inception.

Nevertheless, it seems unwise to recognize all of the five colored regions of the network as "groups" or "clusters" of nodes, since it is not obvious that the network actually supports them all as groups. Perhaps we should call them "neighborhoods" or some other similar term, so as not to be misleading. We could define a neighborhood as a collection of nodes in close proximity in the splits graph but not necessarily representing any unique combination of well-supported splits.

Has phylogenetics reached its apogee?

Few people had heard of phylogenetics before 1970. It was during that decade that explicit methods for constructing phylogenetic trees came to prominence, although such methods had first appeared in the late 1950s. These methods appeared first in systematics, based on parsimony (1970s), and then in genetics, based on likelihood (1980s). These days, phylogenetics is seen as ubiquitous in biology, but it is interesting to consider whether this idea can be quantified.

Joseph Hughes (2011.TreeRipper web application: towards a fully automated optical tree recognition software. BMC Bioinformatics 12:178) had a go at this by trying to extract information from the PubMed bibliographic database. Here, I have expanded on this approach.

I searched PubMed for the string phylogen*, thus including words like "phylogeny" and "phylogenetics", as well as unusual variations on these words. I searched both the full bibliographic record (including the abstract) as well as restricting the search to the Title field. I did this for every calendar year from 1970–2012 inclusive (the 2013 data are currently still incomplete in the database).

The results are shown in the first graph, and the second graph shows the details of the title search alone. The data are expressed as a percentage of the total number of PubMed records for each year.

So, less than 2% of the current papers in biology mention phylogenetics in their title or abstracts. This does not, of course, mean that the paper doesn't mention the topic at all, as it could do so under some other name (eg. "evolutionary tree", "genealogy", etc), or do so in a way that does not make it into the abstract. Still, it seems to me that this is a rather low number.

The erratic nature of the data before 1975 is probably a by-product of the quality of the PubMed data for that time. However, the clear upper asymptote in the data this century is not artifactual, but real. The average maximum value for the "All" data is ~1.54%, reached in 2009, while the average for "Title only" is ~0.17%, reached in 2004. This seems to imply that phylogenetics has now saturated the market, and is as ubiquitous as it will be, unless something new comes along to change it.

The initial rise in usage of the phylogenetic methods coincided with the release of computer programs that implemented them. Wagner78 was released for mainframe computers in 1978, followed by Phylip in 1980. Phylip was the first to be ported to microcomputers; but it was the release of the PC version of PAUP (v. 2.4) in December 1985 that came to dominate the next 10 years. Hennig86, the successor to Wagner78, was released in 1988.

However, the rapid growth in usage coincided with the growth of molecular genetics. The patent applications for PCR were filed in 1985, and the first paper based on it was also published that year. The technology started to be used for human diagnostics during 1986, and PCR became a basic research tool in molecular biology from c.1989. (Science selected PCR as the major scientific development of 1989.) The journal Molecular Biology and Evolution was founded in 1983, and Molecular Phylogenetics and Evolution in 1992.

The inflection point in the graph is c.1999, which indicates where the slow-down in growth occurred. Coincidentally, it was in 1999 that the Journal of Molecular Evolution announced that it would henceforth exclude molecular phylogenetics (and research on the origin of life), except in cases that have "a special significance and impact." Phylogenetics was now seen as a tool of evolutionary analysis rather than an end in itself.

By this stage, bayesian methods were being proposed, and MrBayes was released in 2001, rapidly becoming the predominant program. However, this was simply a transformation of the existing methodology, rather than being a major new component of data analysis in the way the very first programs were. Furthermore, the rise in usage of genome data seems also to be a transformation, rather than a major addition to data collection the way sequence data were.

Thus, it took 30 years (c. 1978–2008) for the phylogenetics revolution to be complete. Mind you, it had already taken 150 years from 1859 for quantitative methods to first be proposed.