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




More information about the Bioperl-l mailing list