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 *i*th position is 1 if the sequence agrees with *L* in the *i*th 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 ...

Start Free Trial

No credit card required