Algebraic trees

[dschrempf]

Hi,

I am a molecular phylogeneticist, and as such I work a lot with tree-like objects (mostly binary trees). I was following the development of alga for some time now and I am keen on using it in my projects. However, I have some conceptional questions. Maybe one of you can answer them.

Basically, I am interested in the following two data types:

1. A rooted tree with labeled branches.

Degree one vertices are leaves; degree two vertices are nodes that divide a branch into two sub-branches; other vertices with degree greater than two are, for example, speciations. The root vertex is special in that no branch is pointing towards it.

At the moment, I use the Tree data type from Data.Tree, and since I can associate each node with the attached branch pointing towards it, I can add the edge label data type to the node label data type. This works quite well. A direct solution with branch labels would be advantageous though.

Can I use Alga for this purpose (without the need to first produce a Data.Tree.Tree and then use using the function tree).

Also, is there a possibility to extend the rooted, tree-like object to a phylogenetic network (a directed, acyclic graph)?

2. An unrooted tree with labeled branches.

In contrast to rooted trees, unrooted trees do not have a root vertex. They have undirected edges with labels. They are very important for reversible phylogenetic methods that are insensitive to the direction of time, so to speak. At the moment, I do not know any way of representing such as object in an algebraic way. I tried to define a Graph-like data type of such an object but failed. Do you know if and how I could use alga to work with unrooted trees?

Finally, I wrote a short blog entry about your library. I want to expand it and explain how to use your library with (phylogenetic) trees. If you want, you can have a short look and tell me if there are any errors.

Thank you,
Dominik

[snowleopard]

Hi Dominik, thanks for reaching out and for writing a nice blog post about Alga! (I found only one little typo: you first say "string decomposition" and then "strong decomposition".)

Of course, I would be pleased if you choose to use the library for your work. However, it is a bit strange to use a graph library when working with trees. Trees are very simple objects algorithmically and when you forget about the tree structure, e.g. by calling the function tree :: Tree a -> Graph a, you lose many efficient algorithms that only work on trees (here is an example).

If you'd like to use graphs to represent trees, and you need edges with labels, then you should look into the module Algebra.Graph.Labelled. It is based on a different algebraic structure which supports edge labels. I haven't yet managed to write a paper or a blog post about it, but I definitely should!

[dschrempf]

Thanks for spotting the type, I have corrected it!

I understand. In this case, I will continue using the Tree data type of the container package for rooted trees. For unrooted trees however, I still think that using Alga or another graph library would make a lot of sense since there is no distinguished (root) node.

[snowleopard]

OK, let's keep this issue open. Perhaps, it's possible to somehow express and manipulate undirected trees algebraically.