Question migrated from bioinformatics stackexchange due to lack of interest.

I'm new to bioinformatics and have been reading through a bioinformatics book, and it seems calculating a phylogenetic tree is quite a complicated process.

I'm wondering if generating the minimum spanning tree (MST) from a similarity matrix would provide a decent approximation to the actual phylogenetic tree, i.e. provide some information on the evolutionary ancestry of a collection of organisms? My thinking is that animals diverging from ancient ancestors will always be farther away than animals that diverged recently, so the MST will at least show me what animals are genetically related and which are genetically distant.

I realize this is not quite the same thing as a phylogenetic tree, but it seems to give me some of the same information provided by a phylogenetic tree, namely which animals are closely genetically related and which are distant relatives.

For reference, I'm measuring similarity based on the normalized compression distance (NCD) metric. The metric is defined in "Clustering by Compression" by Cilibrasi and Vitanyi.

Here is an example MST using the dataset from the referenced paper. Some parts make sense from my rudimentary knowledge of biology, like the clustering of primates. Other parts are new to me, and I'm not sure if the relationships are just an accidental feature of the metric, MST, or if real. For instance, cows are more related to whales instead of horses according to the MST, cats and dogs appear to have evolved from seals or visa versa, and pigs are related to a wide variety of animals: ranging from bats to rabbits to whales.

Note, the 'randgen' nodes are randomly generated DNA sequences that I added to the dataset as a sanity check. As expected, they are off on a branch by themselves instead of mixed into the population of real animal DNA sequences. The reason why they are clustered is because I repeat each DNA sequence 40 times to amplify the signal, and repeated short random subsequences become compressible. The random DNA sequences are probably clustered because they tend to share random subsequences, while the mammal DNA sequences are orderly and have fewer random subsequences.

Here is the repo to reproduce the tree. https://github.com/yters/ncd

enter image description here

  • 3
    $\begingroup$ Well, for a start, it shows nothing about ancestry. A phylogenetic tree shows where modern species exist relative to their most recent common ancestors. That concept is completely missing here. $\endgroup$ – Bryan Krause Aug 4 '19 at 19:09
  • 2
    $\begingroup$ Well yes, because rates of evolution frequently vary between lineages, and genetic (dis)similarity may not cleanly map to species relationships. So you might get some signal, but most of it is probably meaningless. For example, your figure above is telling me that fin whales are as closely related to blue whales as blue whales are to Hippopotami, but it's fairly uncontroversial that cetaceans are monophyletic. We already have fast algorithms to infer inaccurate trees. $\endgroup$ – NatWH Aug 4 '19 at 23:12
  • 2
    $\begingroup$ For another example from your actual example, it looks like a chimp is connected to a platypus through a rhino? What does that even mean? $\endgroup$ – Bryan Krause Aug 4 '19 at 23:13
  • 2
    $\begingroup$ Actually yes, it does - because you're confusing distances for relationships. Relationships are only ever discrete, defined in terms of degrees of common ancestry. The branch lengths do not matter in terms of statements of relatedness. So your graph explicitly does say that a blue whale is as closely related to a fin whale as it is to a cow, because they each are separated by one edge. If you wanted it to say otherwise, you would have to introduce a node representing the hypothetical ancestor to the tree, and @BryanKrause points out. $\endgroup$ – NatWH Aug 4 '19 at 23:48
  • 2
    $\begingroup$ Basically, any algorithm that places an extant taxon on a node, not a tip, is probably not inferring a phylogeny. $\endgroup$ – NatWH Aug 4 '19 at 23:54

Your graphic is omitting nodes of the tree, branching points, which are essential for trees and phylogeny.

When you read the data file, you should count the brackets ((( ))) because they signify where the tree has nodes, common ancestors.

You should generate simple phylogeny trees, prior to doing complex data mining for similarity. The names are in latin? there are genetic distance numbers? What format and data are you using? You have given the common animal names. you may have to use a database of common-and-latin-names to be ables to search "tiger"... that database will return "panthera tigris tigris"... And then you can start crawling up and down the tree branches to search for animals related to tigris tigris, by counting brackets and marking species close to that name.

To prevent the tree exploding to 5000 animals, you can 1/define a search depth. Depth 5, Five, will not go further than five brackets: (((((panthera_tigris_tigris)(lion)(cheetah))))) 2/represent a random fraction of the species (1/100 gives 50 animals from a 5000 tree) 3/use statistics measures to select certain animals based on data mining.

If you want to travel from whales to monkeys, you will have most of the mammalian family, and you will be able to count nodes and brackets by the dozens.

Not that parsing 5000 species has a big computational load that can take 1 hour to read through once, let alone 40 times!

Whichever statistics you are using to measure similarity, number of brackets / genetic distance numbers, you should have once represented trees as branches, nodes and leaves, because that is what tree data is meant to represent.

I'd recommend that you draw a tree using nodes and random animal selection, like 1% chance the animal is drawn in the final tree. When your tree has branches and is drawing OK, change the 1% selection line for the complex MST / MCD selection.

  • $\begingroup$ This is a great suggestion to run the MST on a known phylogenetic tree. Currently, I am just using a collection of DNA sequences. If you could provide a link to a database that has both the tree and the DNA sequences for comparison, I'll mark this as accepted. $\endgroup$ – yters Aug 5 '19 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.