# [Bioperl-l] Find distances between LCA's and the other nodes from a tree

Rutger Vos R.A.Vos at reading.ac.uk
Tue Oct 4 23:59:52 UTC 2011

```> I shall infer the state based on descendant's states. In my example, Nodes H
> and I belong to "Wing", then their ancestor M is also assigned "Wing". After
> assigning these states to all the nodes of the tree, I shall calculate the
> distances between these nodes.

What is your approach for when internal states are equivocal?

> From: Thomas Sharpton [mailto:thomas.sharpton at gmail.com]
> Sent: 2011年10月5日 2:05
> To: Ross KK Leung
> Cc: bioperl-l
> Subject: Re: [Bioperl-l] Find distances between LCA's and the other nodes
> from a tree
>
>
>
> Hi Ross,
>
>
>
> I understand that you want to infer ancestral states on your tree, but I'm
> unclear about how you want to do so. Can you clarify how you infer the state
> for node K on your example tree? In particular, is your method of inference
> dependent on the branch lengths? The answers to these questions will
> (hopefully) help guide you to methods that can assist you.
>
>
>
> Unfortunately, Perl is not the most efficient language for tree/graph
> traversal. It can certainly be done, but for very, very large trees, I tend
> to roll over to C (but only if I have to as I am not proficient in C).
>
>
>
> Best,
>
> Tom
>
>
>
> On Oct 3, 2011, at 6:53 PM, Ross KK Leung wrote:
>
>
>
>
>
> Hi, Tom. Let me formally define my problem because this would be more
> effective for communication. My objective is to assign a state for
> intermediate nodes. For the following example, nodes M and J can be assigned
> with (Wing). After assignment (forget the unassigned first), the pairwise
> distances of these intermediate nodes and any other nodes may be compared
> (e.g. Nodes M and L; Nodes J and E).
>
>
>
>
>
>        +---I (Wing)
>
>        |
>
>    +---M
>
>    |   |
>
>    |   +---H (Wing)
>
>    |
>
> +---O
>
> |   |
>
> |   |
>
> |   |
>
> |   +---L (No-Wing)
>
> |
>
> |
>
> Z
>
> |       +---E (Wing)
>
> |       |
>
> |   +---K
>
> |   |   |
>
> |   |   +---D (No-Wing)
>
> |   |
>
> +---N
>
>    |
>
>    |   +---C (Wing)
>
>    |   |
>
>    +---J
>
>        |
>
>        +---B (Wing)
>
>
>
> Technically, I can either use TreeFunctionsI's method add_trait to the
> leaves first. Then I back trace the ancestral nodes. While nodes K and J are
> pictorially displayed to be nicely at the same level, in fact besides
> exhaustively testing NodeI's methods ancestor or get_all_Descendants etc, I
> cannot come up with a better idea. As you have mentioned before, when the
> tree is big, this curse is amplified, not to say "Wing" is just one of
> several hundred properties to test.
>
>
>
> That's why I'm posting this question to see whether any convenient data
> structures already exist to tackle this kind of "graph-traversing" process.
>
>
>
>
>
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l at lists.open-bio.org
> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>

--
Dr. Rutger A. Vos
School of Biological Sciences
Philip Lyle Building, Level 4