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

[Ross KK Leung]

Hi Tom,

 

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.

 

Switching to C is only the last option because that involves another 2
months, not to include the time if C does not have any libraries to deal
with Newick Tree.

 

Best,

Ross

 

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.