Unrooted softwired distance

[lutteropp]

@celinescornavacca I've read the part in your book about hardwired/softwired clusters in rooted phylogenetic networks. Now I understand what these are:

• A cluster induced by an edge is the set of taxa descending from the target node of the edge.
• For hardwired clusters, we keep all reticulation edges activated at once, and each edge induces a single cluster this way.
• For softwired clusters, we go through the displayed trees one-by-one, switching reticulation edges on and off during the process. Here, each edge induces a set of clusters (up to one per displayed tree).

You mentioned that for softwired network distance, we can modify its definition by treating the displayed trees as unrooted ones. My question is here: How is a cluster defined in an unrooted tree, where the edges have no direction? Which side of the bipartition induced by the edge is the cluster then?

[celinescornavacca]

We need to change things a bit if we want to use unrooted trees. You need to use bipartitions (and not clusters) in the unrooted setting for softwired distances (as I wrote in the slack): For a given network N, T(N) are the displayed trees of N and B(N) are the set of all bipartitions of the trees in T(N). Then, the softwired unrotoed distance between two networks N1 and N2 would be (|B(N1)\B(N2)| + |B(N2)\B(N1)|)/(|B(N2)+B(N1)|)

[lutteropp]

Oh cool, so it really is just the bipartitions then. Nice, that's simple to implement! :) (I've already worked with bipartitions in trees for transfer bootstrap scores, likely can reuse much of the code from there)

Thanks for the lightspeed answer. :-)

[lutteropp]

@celinescornavacca I have implemented this:

Is this (especially the denominator) how you meant it?

[lutteropp]

Now that I think about it... Isn't our "unrooted softwired distance" the same as the normal rooted softwired distance definition, only that we are scaling the distance to be in the range [0.0, 1.0]?

Because when computing a bipartition induced by an edge, I simply collect the set of taxa which are descendants of the edge's target node. All these taxa are on the left side of the bipartition. The remaining taxa are on the right side.

And when I compare two bipartitions, I say bipartitions A and B are equal, if (A.left == B.left) and (A.right == B.right), or (A.left == B.right) and (A.right == B.left)

... To me it looks like we can easily scale all reported topological network distances to be in range [0.0,1.0]...

[lutteropp]

Do we need to ignore the trivial bipartitions (with only a single taxon on one side)? Or are they counted as well?

[lutteropp]

Now that I think about it... Isn't our "unrooted softwired distance" the same as the normal rooted softwired distance definition, only that we are scaling the distance to be in the range [0.0, 1.0]?

Ok nevermind regarding this, I now understand the difference between rooted and unrooted softwired distance. Let S be the set of all taxa. Let the cluster A be a subset of S.

• In rooted interpretation, we treat S and S\A as being different.
• In unrooted interpretation, we treat S and S\A as being equal.

[lutteropp]

Is this (especially the denominator) how you meant it?

Nevermind, I just noticed my mistake: The denominator has to be the cardinality of the set union, not the sum of the set cardinalities...

[stamatak]

we shouldn't count them as they do not provide any information about the tree/network structure

On 16.02.21 01:13, Sarah Lutteropp wrote:

Do we need to ignore the trivial bipartitions (with only a single taxon on one side)? Or are they counted as well?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/lutteropp/NetRAX/issues/45#issuecomment-779487984, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAGXB6VLNXFUMTO72NLNDETS7GTCNANCNFSM4XUZONAQ.

-- Alexandros (Alexis) Stamatakis

Research Group Leader, Heidelberg Institute for Theoretical Studies Full Professor, Dept. of Informatics, Karlsruhe Institute of Technology

www.exelixis-lab.org

[celinescornavacca]

Hi

I cannot access github from my phone so i cannot see what I wrote on the denominator, (maybe I wrote this too fast, in this case, sorry for the mess) but the denominator is there to ensure that the distance.max = 1 if no bipartition is in common between the trees.

On February 16, 2021 7:10:27 AM GMT+01:00, Alexis Stamatakis notifications@github.com wrote:

we shouldn't count them as they do not provide any information about the > tree/network structure>

On 16.02.21 01:13, Sarah Lutteropp wrote:> Do we need to ignore the trivial bipartitions (with only a single taxon > on one side)? Or are they counted as well?>

—> You are receiving this because you are subscribed to this thread.> Reply to this email directly, view it on GitHub >

https://github.com/lutteropp/NetRAX/issues/45#issuecomment-779487984,

or unsubscribe >

https://github.com/notifications/unsubscribe-auth/AAGXB6VLNXFUMTO72NLNDETS7GTCNANCNFSM4XUZONAQ.>

-- > Alexandros (Alexis) Stamatakis>

Research Group Leader, Heidelberg Institute for Theoretical Studies> Full Professor, Dept. of Informatics, Karlsruhe Institute of Technology>

www.exelixis-lab.org>

-- > You are receiving this because you were mentioned.> Reply to this email directly or view it on GitHub:> https://github.com/lutteropp/NetRAX/issues/45#issuecomment-779607689

-- Sent from my Android device with K-9 Mail. Please excuse my brevity.