[Bioperl-l] OntologyTermI

[Paul Gordon]

> This sounds right.  Is cycle checking computationally expensive?
For each term (vertex) that you add you'll need to check if there is a
cycle from that vertex (the cycle property is common of course to all
vertices in a cycle, so you need only check the one for edges that
introduce it).  There are some fancy parallel algorithms that probably
aren't worth implementing for Joe Blow user, e.g.:

http://hpc.eece.unm.edu/papers/99013.html

As far as I can tell, you're going to be left with a path search on
the order of Dijkstra's shortest path algorithm. If the graph has m edges
and n vertices, O(m + n log n).  In practice though, if you implement it 
correctly, it would be trivial for leaf nodes, and generally inversely
proportional to the depth of the term in the tree.  So it'd be expensive
only to add new well connected, high up terms.

My CDN$0.02,

	Paul

----------------------------------------------------
Purgamentum init, exit purgamentum

Paul Gordon
Research Associate
University of Calgary

> Lincoln
> 
> On Tuesday 03 September 2002 08:47 pm, Hilmar Lapp wrote:
> > Essentially Graph::DAG would override $G->add_cycle() to throw an
> > exception, and add checks such that $G->add_edge() can't introduce a
> > cycle? Would it need more than that?
> >
> > Has anyone gone through the exercise of putting e.g. GO into a
> > Graph::Directed object?
> >
> > 	-hilmar
> >
> > On Tuesday, September 3, 2002, at 04:44  PM, Lincoln Stein wrote:
> > > That's certainly a possibility.  The Graph::* namespace on CPAN has
> > > room for a
> > > DAG.  Presumably it would inherit from Graph::Directed.
> > >
> > > Lincoln
> > >
> > > Module          Graph           (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::BFS      (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::Base     (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::DFS      (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::Directed (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::HeapElem (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::Kruskal  (S/ST/STBEY/Graph-Kruskal-2.0.tar.gz)
> > > Module          Graph::Reader   (N/NE/NEILB/Graph-
> > > ReadWrite-1.07.tar.gz)
> > > Module          Graph::Reader::Dot (N/NE/NEILB/Graph-
> > > ReadWrite-1.07.tar.gz)
> > > Module          Graph::Reader::HTK (N/NE/NEILB/Graph-
> > > ReadWrite-1.07.tar.gz)
> > > Module          Graph::Reader::XML (N/NE/NEILB/Graph-
> > > ReadWrite-1.07.tar.gz)
> > > Module          Graph::Traversal (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::Undirected (J/JH/JHI/Graph-0.201.tar.gz)
> > > Module          Graph::Vertex   (J/JH/JHI/Graph-0.005.tar.gz)
> > >
> > > On Monday 02 September 2002 12:43 am, Chris Mungall wrote:
> > >> I like this
> > >>
> > >> however, as Bio::Ontology::Graph is likely to be a completely generic
> > >> graph module, why not just use the namespace Graph:: and have it as a
> > >> seperate CPAN module (but possibly keeping the cvs in
> > >> bioperl-live)? just
> > >> a thought.
> > >>
> > >> once you seperate term from node, do you really need a node
> > >> object? why
> > >> not just have a graph object and treat the nodes and relationship
> > >> types as
> > >> strings (possibly namespaced, but the graph module doesn't care about
> > >> this).
> > >>
> > >> On Thu, 29 Aug 2002, Ewan Birney wrote:
> > >>> On Wed, 28 Aug 2002, Lincoln Stein wrote:
> > >>>> I believe that the idea of the term should be separated from the
> > >>>> idea
> > >>>> of a graph of terms.  I think also that the idea of an association
> > >>>> between a term and a set of biological objects should also be
> > >>>> separate.
> > >>>>
> > >>>> I'd propose something like this:
> > >>>>
> > >>>> 	Bio::Ontology::TermI;   # why repeat the word Ontology?
> > >>>>
> > >>>>
> > >>>> 		Encapsulates the term ID, the term name, the term definition, the
> > >>>> term aliases,and possibly the "obsolete" tag.
> > >>>>
> > >>>> 	Bio::Ontology::Graph::NodeI;
> > >>>>
> > >>>> 		A node in a graph.
> > >>>>
> > >>>> 	Bio::::Ontology::Graph::DAGI;
> > >>>>
> > >>>> 		Encapsulates the graph traversal methods.
> > >>>>
> > >>>> 	Bio::Ontology::Term::AssociationI;
> > >>>>
> > >>>> 		Maps a term to a set of biological objects.
> > >>>>
> > >>>> The nice thing about separating the Term from the DAG is that
> > >>>> you can
> > >>>> then reuse the same term in different types of graphs, or chuck the
> > >>>> graph entirely without scrambling the meaning of the term.
> > >>>
> > >>> I am with Lincoln here. This would be the set up I would use as well.
> > >
> > > --
> > > ========================================================================
> > > Lincoln D. Stein                           Cold Spring Harbor
> > > Laboratory
> > > lstein@cshl.org			                  Cold Spring Harbor, NY
> > > ========================================================================
> 
> -- 
> Lincoln Stein
> lstein@cshl.org
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l@bioperl.org
> http://bioperl.org/mailman/listinfo/bioperl-l
>