[Bioperl-l] Bio::Species, Bio::Taxonomy::Node overhaul

[Hilmar Lapp]

On Aug 7, 2006, at 9:57 AM, Sendu Bala wrote:

>
> Let T be a rooted tree. A node x ∈ T is an ancestor of a
> node y ∈ T if the path from the root of T to y goes through
> x. A node v ∈ T is a common ancestor of x and y if it is
> an ancestor of both x and y. The nearest common ancestor,
> nca, of two nodes x, y is the common ancestor of x and y
> whose distance to x (and to y) is smaller than the distance
> to x of any other common ancestor of x and y.
>
> According to that, v cannot be x or y.

Why not? The path from the root node to node x certainly goes through  
x, so x is an ancestor of x. Also, there is no other ancestor of x  
whose distance to x is smaller than the distance of x to x (namely  
zero).

Hence, x is the nearest common ancestor of nodes x and x. More  
generally, node x is the nearest common ancestor of node x and any  
node z for which node x is an ancestor.

Otherwise, as an example, for a rooted tree what is the nearest  
common ancestor between the root node and any node in the tree? Do  
you claim that in this case there is no common ancestor?

The above definition (intentionally) does not say that x != y.

	-hilmar

-- 
===========================================================
: Hilmar Lapp  -:-  Durham, NC  -:-  hlapp at gmx dot net :
===========================================================