[Bioperl-l] Bio::Species, Bio::Taxonomy::Node overhaul
Hilmar Lapp
hlapp at gmx.net
Mon Aug 7 12:36:30 EDT 2006
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 :
===========================================================
More information about the Bioperl-l
mailing list