[Bioperl-l] common ancestor for ontology terms

[Hilmar Lapp]

For the transitive closure computation we'll need to answer questions 
like for two predicates A and B encountered along a path, is there a 
common ancestor predicate that covers both. Per our definition, the 
path would then receive the ancestor as predicate, and the path would 
be void otherwise.

This query also comes up in other contexts; e.g. for two feature types 
A and B, what is the super-type.

I'd be interested whether anyone (ChrisM? Biojava folks?) has had any 
experience with working with and implementing this kind of query. 
Generally speaking it appears to me it's a O(V^2) problem; using sets 
and a transitive closure it could actually be solved pretty easily and 
elegant (that's why in SQL it's easy to come up with a query that 
answers this).

I wrote a POD section (no implementation yet) and whether this makes 
sense to people.

	-hilmar

=head2 common_ancestor_path

  Title   : common_ancestor_path
  Usage   :
  Function: Get the paths from two terms A and B to term C, such that
            there is no other term D to which A and B would have a 
shorter
            path, provided there is a term C to which both A and B are
            connected by a path.

            Note that the path to the common ancestor between A and A
            exists, has distance zero, and predicate "identity".

            The search for the common ancestor C can be further
            constrained by supplying a predicate term. If supplied, the
            predicates of the two paths (A,C) and (B,C) must have a
            common ancestor identical to the predicate, or that has a
            path to the predicate.

  Example :
  Returns : The path of the first term to the common ancestor in scalar
            context, and both paths in list context. Paths are
            Bio::Ontology::PathI compliant objects.
  Args    : The two terms (Bio::Ontology::TermI objects), and optionally
            a constraining common predicate (Bio::Ontology::TermI 
object).
            The latter may also be given as a scalar, in which case it
            is treated as a boolean that, if TRUE, means that the two 
paths
            must have identical predicates in order to be returned.


=cut

-- 
-------------------------------------------------------------
Hilmar Lapp                            email: lapp at gnf.org
GNF, San Diego, Ca. 92121              phone: +1-858-812-1757
-------------------------------------------------------------