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

Thomas Sharpton thomas.sharpton at gmail.com
Tue Oct 4 18:05:27 UTC 2011

```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.

```