5

I developed new algorithm for phylogenetic tree comparison(phylogenetic tree is simply rooted binary tree). As an input we have two trees, we want to calculate their similarity percentage. one example of these type of algorithms is here.

But most of these algorithms(as I know all of them) did not offer a good way to check the accuracy of their algorithms. e.g if you look at the following figure, you can see there is more similarity between T1 and T3, versus T1 and T2.

examples of three phylogenetic trees

I need a method for checking its accuracy of similarity measure, To be sure that my algorithm is better than previous algorithms !!! (it is not difficult in most of the case by human eyes but I don't know how to extend it to my application)

your validity measure should be independent from algorithm.

SlowLoris
  • 995
  • 6
  • 28
  • 2
    you could ask http://biostar.stackexchange.com/ – Pierre Jan 23 '12 at 17:52
  • It would be helpful if you provided a little more detail. For example, are you interested in measuring how similar the shapes of the trees are? Are there similarities or distance measurements that should also be considered? – kc2001 Jan 24 '12 at 06:24
  • I don't want to find a similarity measurement for two trees, actually I have one I called it 'A'. I am interested to find a way to claim 'A' is better than previous similarity measurements . For example I can make a random tree(e.g. T1), by slowly reordering the leaves of T1 and making new trees like T2,T3,...(for example for T2 we can change the position of only two adjacent leaf but for T3 we can reorder the position of 4 leaf and...) we should be also observe decreasing similarity between T1 and T2, T1 and T3 and ... –  Jan 25 '12 at 07:43

1 Answers1

1

Take a look at "Graph similarity scoring and matching" and "A Method for Comparing Two Hierarchical Clusterings". Maybe they (or linked references) will be helpful.

kc2001
  • 5,008
  • 4
  • 51
  • 92