O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

13.7 Applications in Phylogenetics

Median graphs were introduced by Bandelt in 1994 as a tool for phylogenetic analysis, see [4]. Since then many new theoretical as well practical results have been obtained, that is, median graphs have also been successfully used in the analysis of population data in the form of human mitochondrial data, see [10, 12].

Median graph can be used to visualize phylogenetic relationships as follows. One way to build a median graph from a given alignment pattern of some taxa is to consider all sequences and for any position form splits in such a way as to combine in the same part all sequences that agree in this position. If this is possible, then sequences are said to be binary (every position has only two possible values). Once splits are determined for every position of the sequences, the construction from the previous section can be applied (the construction of the Buneman graph).

In practice, however, another approach is more appropriate. Suppose that a given taxon has a binary sequence and that its length is k. Then one can recode the alignment into binary data as follows: choose an arbitrary reference sequence L and code it by the sequence of the length k with all entries equal to 1. For any other sequence the ith position is 1 if the sequence agrees with L in the ith position and 0 otherwise. To reduce unnecessary data, remove all positions that agree on all sequences to get a set M, a set of sequences of length j. So far, sequences present vertices ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required