Reconstructing phylogenetic tree from set of bipartitions

Question

[balanand.jha]

I read at a number of places that a phylogenetic tree can be uniquely represented by its set of bipartitions and that a phylogenetic tree can be reconstructed from its set of bipartitions. Can anyone please explain or provide a link to algorithm or steps following which I can reconstruct a tree from its set of bipartitions?

Thanks

[Joe]

I think I’m right in saying that this will only be true for a fully bifurcating tree. If there are polytomies present, and the tree isn’t rooted, there is no unique tree.

Do you have some example data? In order to be able to reconstruct a tree from purely a list of bipartitions, you would need at least some 'overlapping' partition information.

This documentation on DendroPy might get you started: https://www.dendropy.org/primer/bipartitions.html

[balanand.jha]

Actually I am trying to implement TreeZip algorithm in my project to compress trees. The treezip algorithm stores each unique bipartition in a set of trees and its support values (tree ids which contain that bipartition) in *.trz file. When unzipping the file, it creates a t x n matrix where t is the number of input trees and n is maximum possible number of bipartitions. Each row "i" of this matrix represents a collection of bipartitions contained in tree "i". In their paper, authors have skipped this method of reconstruction of trees from this matrix.

[Joe]

You may be best contacting the authors specifically if you haven't already done so, in that case.