source: orange-bioinformatics/orangecontrib/bio/obiOntology.py @ 1907:9b35fd5ebae0

Revision 1907:9b35fd5ebae0, 33.0 KB checked in by Ales Erjavec <ales.erjavec@…>, 5 months ago (diff)

Fixed obo tag value parsing.

Line 
1"""
2===========
3obiOntology
4===========
5
6This module provides an interface for parsing, creating and manipulating of
7OBO ontologies (http://www.obofoundry.org/)
8
9Construct an ontology from scratch with custom terms ::
10
11    >>> term = OBOObject("Term", id="foo:bar", name="Foo bar")
12    >>> print term
13    [Term]
14    id: foo:bar
15    name: Foo bar
16
17    >>> ontology = OBOOntology()
18    >>> ontology.add_object(term)
19    >>> ontology.add_header_tag("created-by", "ales") # add a header tag
20    >>> from StringIO import StringIO
21    >>> buffer = StringIO()
22    >>> ontology.dump(buffer) # Save the ontology to a file like object
23    >>> print buffer.getvalue() # Print the contents of the buffer
24    created-by: ales
25    <BLANKLINE>
26    [Term]
27    id: foo:bar
28    name: Foo bar
29    <BLANKLINE>
30
31To load an ontology from a file pass the file or filename to the
32:class:`OBOOntology` constructor or call its load method ::
33
34    >>> buffer.seek(0) # rewind
35    >>> ontology = OBOOntology(buffer)
36    >>> # Or equivalently
37    >>> buffer.seek(0) # rewind
38    >>> ontology = OBOOntology()
39    >>> ontology.load(buffer)
40
41
42See http://www.geneontology.org/GO.format.obo-1_2.shtml for the definition
43of the .obo file format.
44
45"""
46
47import re
48import urllib2
49import warnings
50import keyword
51from collections import defaultdict
52from StringIO import StringIO
53
54
55#: These are builtin OBO objects present in any ontology by default.
56BUILTIN_OBO_OBJECTS = [
57"""[Typedef]
58id: is_a
59name: is_a
60range: OBO:TERM_OR_TYPE
61domain: OBO:TERM_OR_TYPE
62definition: The basic subclassing relationship [OBO:defs]""",
63
64"""[Typedef]
65id: disjoint_from
66name: disjoint_from
67range: OBO:TERM
68domain: OBO:TERM
69definition: Indicates that two classes are disjoint [OBO:defs]""",
70
71"""[Typedef]
72id: instance_of
73name: instance_of
74range: OBO:TERM
75domain: OBO:INSTANCE
76definition: Indicates the type of an instance [OBO:defs]""",
77
78"""[Typedef]
79id: inverse_of
80name: inverse_of
81range: OBO:TYPE
82domain: OBO:TYPE
83definition: Indicates that one relationship type is the inverse of another [OBO:defs]""",
84
85"""[Typedef]
86id: union_of
87name: union_of
88range: OBO:TERM
89domain: OBO:TERM
90definition: Indicates that a term is the union of several others [OBO:defs]""",
91
92"""[Typedef]
93id: intersection_of
94name: intersection_of
95range: OBO:TERM
96domain: OBO:TERM
97definition: Indicates that a term is the intersection of several others [OBO:defs]"""
98]
99
100
101def _split_and_strip(string, sep):
102    """
103    Split the `string` by separator `sep` in to two parts and strip
104    any whitespace between the inner parts.
105
106    """
107    head, tail = _split_esc(string, sep)
108    return head.rstrip(" "), tail.lstrip(" ")
109
110
111def _rsplit_and_strip(string, sep):
112    """
113    Right split the `string` by separator `sep` in to two parts and
114    strip any whitespace between the inner parts.
115
116    """
117    head, tail = _rsplit_esc(string, sep)
118    return head.rstrip(" "), tail.lstrip(" ")
119
120
121def _find_esc(string, char):
122    i = string.find(char)
123    while i != -1:
124        if (i > 0 and string[i - 1] != "\\") or string[i - 1] != "\\":
125            return i
126        else:
127            i = string.find(char, i + 1)
128    return i
129
130
131def _rfind_esc(string, char):
132    i = string.rfind(char)
133    while i != -1:
134        if (i > 0 and string[i - 1] != "\\") or string[i - 1] != "\\":
135            return i
136        else:
137            i = string.rfind(char, 0, i - 1)
138    return i
139
140
141def _split_esc(string, sep, _find_esc=_find_esc):
142    i = _find_esc(string, sep)
143    if i != -1:
144        return string[:i], string[i + 1:]
145    else:
146        return string, ""
147
148
149def _rsplit_esc(string, sep):
150    i = _rfind_esc(string, sep)
151    if i != -1:
152        return string[:i], string[i + 1:]
153    else:
154        return string, ""
155
156
157def parse_tag_value(tag_value_string):
158    """
159    Parse a tag value string and return a four-tuple containing
160    a (tag, value, modifiers, comment). If comment or modifiers are
161    not present the corresponding entry will be ``None``.
162
163    >>> parse_tag_value("foo: bar {modifier=frob} ! Comment")
164    ('foo', 'bar', 'modifier=frob', 'Comment')
165    >>> parse_tag_value("foo: bar")
166    ('foo', 'bar', None, None)
167    >>> parse_tag_value("foo: bar [baz:0] { fizz=buzz } ! Comment")
168    ('foo', 'bar [baz:0]', 'fizz=buzz', 'Comment')
169
170    """
171    comment = modifiers = None
172    # First get rid of the comment if present
173    if _rfind_esc(tag_value_string, "!") != -1:
174        tag_value_string, comment = _rsplit_and_strip(tag_value_string, "!")
175
176    # Split on the first unescaped ":"
177    tag, value = _split_and_strip(tag_value_string, ":")
178
179    # Split the value on { to get the modifiers if present
180    value = value.rstrip()
181    if value.endswith("}") and not value.endswith(r"\}") and \
182            _rfind_esc(value, "{") != -1:
183        value, modifiers = _rsplit_and_strip(value, "{")
184        # remove closing } and any whitespace
185        modifiers = modifiers[: -1].rstrip()
186
187    return tag, value, modifiers, comment
188
189
190class OBOObject(object):
191    """
192    Represents a generic OBO object (e.g. Term, Typedef, Instance, ...)
193    Example::
194
195        >>> term = OBOObject(stanza_type="Term", id="FOO:001", name="bar")
196
197        >>> term = OBOObject(
198        ...     stanza_type="Term",
199        ...     id="FOO:001",
200        ...     name="bar",
201        ...     def_="Example definition { modifier=frob } ! Comment"
202        ... )
203        ...
204
205    An alternative way to specify tags in the constructor::
206
207        >>> term = OBOObject(stanza_type="Term", id="FOO:001", name="bar",
208        ...                  def_=("Example definition",
209        ...                        [("modifier", "frob")],
210        ...                        "Comment"))
211        ...
212
213    .. note::
214        Note the use of ``def_`` to define the 'def' tag. This is to
215        avoid the name clash with the python's ``def`` keyword.
216
217    """
218    def __init__(self, stanza_type="Term", **kwargs):
219        """
220        Initialize from keyword arguments.
221        """
222        self.stanza_type = stanza_type
223
224        self.modifiers = []
225        self.comments = []
226        self.tag_values = []
227        self.values = {}
228
229        sorted_tags = sorted(
230            kwargs.iteritems(),
231            key=lambda key_val: chr(1) if key_val[0] == "id" else key_val[0]
232        )
233
234        for tag, value in sorted_tags:
235            if isinstance(value, basestring):
236                tag, value, modifiers, comment = \
237                    self.parse_tag_value(self.name_demangle(tag), value)
238            elif isinstance(value, tuple):
239                tag, value, modifiers, comment = \
240                    ((self.name_demangle(tag),) + value + (None, None))[:4]
241            self.add_tag(tag, value, modifiers, comment)
242
243        self.related = set()
244
245    @property
246    def is_annonymous(self):
247        """
248        Is this object anonymous.
249        """
250        value = self.get_value("is_annonymous")
251        return bool(value)
252
253    def name_mangle(self, tag):
254        """
255        Mangle tag name if it conflicts with python keyword.
256
257        Example::
258
259            >>> term.name_mangle("def"), term.name_mangle("class")
260            ('def_', 'class_')
261
262        """
263        if keyword.iskeyword(tag):
264            return tag + "_"
265        else:
266            return tag
267
268    def name_demangle(self, tag):
269        """
270        Reverse of `name_mangle`.
271        """
272        if tag.endswith("_") and keyword.iskeyword(tag[:-1]):
273            return tag[:-1]
274        else:
275            return tag
276
277    def add_tag(self, tag, value, modifiers=None, comment=None):
278        """
279        Add `tag`, `value` pair to the object with optional modifiers and
280        comment.
281
282        Example::
283
284            >>> term = OBOObject("Term")
285            >>> term.add_tag("id", "FOO:002", comment="This is an id")
286            >>> print term
287            [Term]
288            id: FOO:002 ! This is an id
289
290        """
291        tag = intern(tag)  # a small speed and memory benefit
292        self.tag_values.append((tag, value))
293        self.modifiers.append(modifiers)
294        self.comments.append(comment)
295        self.values.setdefault(tag, []).append(value)
296
297        #  TODO: fix multiple tags grouping
298        if hasattr(self, tag):
299            if isinstance(getattr(self, tag), list):
300                getattr(self, tag).append(value)
301            else:
302                setattr(self, tag, [getattr(self, tag)] + [value])
303        else:
304            setattr(self, self.name_mangle(tag), value)
305
306    def update(self, other):
307        """
308        Update the term with tag value pairs from `other`
309        (:class:`OBOObject`). The tag value pairs are appended to the
310        end except for the `id` tag.
311
312        """
313        for (tag, value), modifiers, comment in \
314                zip(other.tag_values, other.modifiers, other.comments):
315            if tag != "id":
316                self.add_tag(tag, value, modifiers, comment)
317
318    def get_value(self, tag, group=True):
319        if group:
320            pairs = [pair for pair in self.tag_values if pair[0] == tag]
321            return pairs
322        else:
323            tag = self.name_mangle(tag)
324            if tag in self.__dict__:
325                return self.__dict__[tag]
326            else:
327                raise ValueError("No value for tag: %s" % tag)
328
329    def tag_count(self):
330        """
331        Return the number of tags in this object.
332        """
333        return len(self.tag_values)
334
335    def tags(self):
336        """
337        Return an iterator over the (tag, value) pairs.
338        """
339        for i in range(self.tag_count()):
340            yield self.tag_values[i] + (self.modifiers[i], self.comments[i])
341
342    def format_single_tag(self, index):
343        """
344        Return a formated string representing index-th tag pair value
345
346        Example::
347
348            >>> term = OBOObject(
349            ...     "Term", id="FOO:001", name="bar",
350            ...      def_="Example definition {modifier=frob} ! Comment")
351            ...
352            >>> term.format_single_tag(0)
353            'id: FOO:001'
354            >>> term.format_single_tag(1)
355            'def: Example definition { modifier=frob } ! Comment'
356
357        ..
358            Why by index, and not by tag?
359
360        """
361        tag, value = self.tag_values[index]
362        modifiers = self.modifiers[index]
363        comment = self.comments[index]
364        res = ["%s: %s" % (tag, value)]
365        if modifiers:
366            res.append("{ %s }" % modifiers)
367        if comment:
368            res.append("! " + comment)
369        return " ".join(res)
370
371    def format_stanza(self):
372        """
373        Return a string stanza representation of this object.
374        """
375        stanza = ["[%s]" % self.stanza_type]
376        for i in range(self.tag_count()):
377            stanza.append(self.format_single_tag(i))
378        return "\n".join(stanza)
379
380    @classmethod
381    def parse_stanza(cls, stanza):
382        r"""
383        Parse and return an OBOObject instance from a stanza string.
384
385        Example::
386
387            >>> term = OBOObject.parse_stanza("[Term]\nid: FOO:001\nname:bar")
388            >>> print term.id, term.name
389            FOO:001 bar
390
391        """
392        lines = stanza.splitlines()
393        stanza_type = lines[0].strip("[]")
394#        tag_values = []
395#        for line in lines[1:]:
396#            if ":" in line:
397#                tag_values.append(cls.parse_tag_value(line))
398        tag_values = [cls.parse_tag_value(line) for line in lines[1:]
399                      if ":" in line]
400
401        obo = OBOObject(stanza_type)
402        for tag, value, modifiers, comment in tag_values:
403            obo.add_tag(tag, value, modifiers, comment)
404        return obo
405
406    @classmethod
407    def parse_tag_value(cls, tag_value_pair, *args):
408        """
409        Parse and return a four-tuple containing a tag, value, a
410        list of modifier pairs, comment. If no modifiers or comments
411        are present the corresponding entries will be ``None``.
412
413        Example::
414
415            >>> OBOObject.parse_tag_value("foo: bar {modifier=frob} ! Comment")
416            ('foo', 'bar', 'modifier=frob', 'Comment')
417            >>> OBOObject.parse_tag_value("foo: bar")
418            ('foo', 'bar', None, None)
419            >>> # Can also pass tag, value pair already split
420            >>> OBOObject.parse_tag_value("foo", "bar {modifier=frob} ! Comment")
421            ('foo', 'bar', 'modifier=frob', 'Comment')
422
423        """
424        if args and ":" not in tag_value_pair:
425            tag, rest = tag_value_pair, args[0]
426        else:
427            tag, rest = _split_and_strip(tag_value_pair, ":")
428        value, modifiers, comment = None, None, None
429
430        if "{" in rest:
431            value, rest = _split_and_strip(rest, "{",)
432            modifiers, rest = _split_and_strip(rest, "}")
433        if "!" in rest:
434            if value is None:
435                value, comment = _split_and_strip(rest, "!")
436            else:
437                _, comment = _split_and_strip(rest, "!")
438        if value is None:
439            value = rest
440
441        if modifiers is not None:
442            modifiers = modifiers  # TODO: split modifiers in a list
443
444        return tag, value, modifiers, comment
445
446    _RE_TAG_VALUE = re.compile(r"^(?P<tag>.+?[^\\])\s*:\s*(?P<value>.+?)\s*(?P<modifiers>[^\\]{.+?[^\\]})?\s*(?P<comment>[^\\]!.*)?$")
447    _RE_VALUE = re.compile(r"^\s*(?P<value>.+?)\s*(?P<modifiers>[^\\]{.+?[^\\]})?\s*(?P<comment>[^\\]!.*)?$")
448
449    _RE_TAG_VALUE = re.compile(
450        r"^(?P<tag>.+?)\s*(?<!\\):\s*(?P<value>.+?)\s*(?P<modifiers>(?<!//){.*?(?<!//)})?\s*(?P<coment>(?<!//)!.*)?$")
451    _RE_VALUE = re.compile(
452        r"^\s*(?P<value>.+?)\s*(?P<modifiers>(?<!//){.*?(?<!//)})?\s*(?P<coment>(?<!//)!.*)?$")
453
454    @classmethod
455    def parse_tag_value_1(cls, tag_value_pair, arg=None):
456        """
457        Parse and return a four-tuple containing a tag, value, a list
458        of modifier pairs, comment. If no modifiers or comments are
459        present the corresponding entries will be None.
460
461        Example::
462            >>> OBOObject.parse_tag_value("foo: bar {modifier=frob} ! Comment")
463            ('foo', 'bar', 'modifier=frob', 'Comment')
464            >>> OBOObject.parse_tag_value("foo: bar")
465            ('foo', 'bar', None, None)
466            >>> #  Can also pass tag, value pair already split
467            >>> OBOObject.parse_tag_value("foo", "bar {modifier=frob} ! Comment")
468            ('foo', 'bar', 'modifier=frob', 'Comment')
469
470        .. warning: This function assumes comment an modifiers are prefixed
471            with a whitespace i.e. 'tag: bla! comment' will be parsed
472            incorrectly!
473
474        """
475        if arg is not None:  # tag_value_pair is actually a tag only
476            tag = tag_value_pair
477            value, modifiers, comment = cls._RE_VALUE.findall(arg)[0]
478        else:
479            tag, value, modifiers, comment = \
480                cls._RE_TAG_VALUE.findall(tag_value_pair)[0]
481        none_if_empyt = lambda val: None if not val.strip() else val.strip()
482        modifiers = modifiers.strip(" {}")
483        comment = comment.lstrip(" !")
484        return (none_if_empyt(tag), none_if_empyt(value),
485                none_if_empyt(modifiers), none_if_empyt(comment))
486
487    def related_objects(self):
488        """
489        Return a list of tuple pairs where the first element is
490        relationship (typedef id) and the second object id whom the
491        relationship applies to.
492
493        """
494        result = [(type_id, id)
495                  for type_id in ["is_a"]  # TODO add other defined Typedef ids
496                  for id in self.values.get(type_id, [])]
497
498        result = result + [tuple(r.split(None, 1))
499                           for r in self.values.get("relationship", [])]
500        return result
501
502    def __repr__(self):
503        """
504        Return a string representation of the object in OBO format
505        """
506        return self.format_stanza()
507
508    def __iter__(self):
509        """
510        Iterates over sub terms
511        """
512        return iter(self.related_objects())
513
514
515class Term(OBOObject):
516    """
517    A 'Term' object in the ontology.
518    """
519    def __init__(self, *args, **kwargs):
520        OBOObject.__init__(self, "Term", *args, **kwargs)
521
522
523class Typedef(OBOObject):
524    """
525    A 'Typedef' object in the ontology.
526    """
527    def __init__(self, *args, **kwargs):
528        OBOObject.__init__(self, "Typedef", *args, **kwargs)
529
530
531class Instance(OBOObject):
532    """
533    An 'Instance' object in the ontology
534    """
535    def __init__(self, *args, **kwargs):
536        OBOObject.__init__(self, "Instance", *args, **kwargs)
537
538
539class OBOParser(object):
540    r""" A simple parser for .obo files (inspired by xml.dom.pulldom)
541
542    Example::
543
544        >>> from StringIO import StringIO
545        >>> file = StringIO("header_tag: header_value\n[Term]\nid: "
546        ...                 "FOO { modifier=bar } ! comment\n\n")
547        ...
548        >>> parser = OBOParser(file)
549        >>> for event, value in parser:
550        ...     print event, value
551        ...
552        HEADER_TAG ['header_tag', 'header_value']
553        START_STANZA Term
554        TAG_VALUE ('id', 'FOO', 'modifier=bar', 'comment')
555        CLOSE_STANZA None
556
557    """
558    def __init__(self, file):
559        self.file = file
560
561    def parse(self, progress_callback=None):
562        """
563        Parse the file and yield parse events.
564
565        .. todo List events and values
566
567        """
568        data = self.file.read()
569        header = data[: data.index("\n[")]
570        body = data[data.index("\n[") + 1:]
571        for line in header.splitlines():
572            if line.strip():
573                yield "HEADER_TAG", line.split(": ", 1)
574
575        current = None
576        #  For speed make these functions local
577        startswith = str.startswith
578        endswith = str.endswith
579#        parse_tag_value = OBOObject.parse_tag_value
580        parse_tag_value_ = parse_tag_value
581
582        for line in body.splitlines():
583            if startswith(line, "[") and endswith(line, "]"):
584                yield "START_STANZA", line.strip("[]")
585                current = line
586            elif startswith(line, "!"):
587                yield "COMMENT", line[1:]
588            elif line:
589                yield "TAG_VALUE", parse_tag_value_(line)
590            else:  # empty line is the end of a term
591                yield "CLOSE_STANZA", None
592                current = None
593        if current is not None:
594            yield "CLOSE_STANZA", None
595
596    def __iter__(self):
597        """
598        Iterate over parse events (same as parse())
599        """
600        return self.parse()
601
602
603class OBOOntology(object):
604    """
605    An class for representing OBO ontologies.
606
607    :param file-like file:
608        A optional file like object describing the ontology in obo format.
609
610    """
611
612    BUILTINS = BUILTIN_OBO_OBJECTS
613
614    def __init__(self, file=None):
615        """
616        Initialize an ontology instance from a file like object (.obo format)
617        """
618        self.objects = []
619        self.header_tags = []
620        self.id2term = {}
621        self.alt2id = {}
622        self._resolved_imports = []
623        self._invalid_cache_flag = False
624        self._related_to = {}
625
626        # First load the built in OBO objects
627        builtins = StringIO("\n" + "\n\n".join(self.BUILTINS) + "\n")
628        self.load(builtins)
629        if file:
630            self.load(file)
631
632    def add_object(self, object):
633        """
634        Add an :class:`OBOObject` instance to this ontology.
635        """
636        if object.id in self.id2term:
637            raise ValueError("OBOObject with id: %s already in "
638                             "the ontology" % object.id)
639        self.objects.append(object)
640        self.id2term[object.id] = object
641        self._invalid_cache_flag = True
642
643    def add_header_tag(self, tag, value):
644        """
645        Add header tag, value pair to this ontology.
646        """
647        self.header_tags.append((tag, value))
648
649    def load(self, file, progress_callback=None):
650        """
651        Load terms from a file.
652
653        :param file-like file:
654            A file-like like object describing the ontology in obo format.
655        :param function progress_callback:
656            An optional function callback to report on the progress.
657
658        """
659        if isinstance(file, basestring):
660            file = open(file, "rb")
661
662        parser = OBOParser(file)
663        current = None
664        for event, value in parser.parse(progress_callback=progress_callback):
665            if event == "TAG_VALUE":
666                current.add_tag(*value)
667            elif event == "START_STANZA":
668                current = OBOObject(value)
669            elif event == "CLOSE_STANZA":
670                self.add_object(current)
671                current = None
672            elif event == "HEADER_TAG":
673                self.add_header_tag(*value)
674            elif event != "COMMENT":
675                raise Exception("Parse Error! Unknown parse "
676                                "event {0}".format(event))
677
678        imports = [value for tag, value in self.header_tags
679                   if tag == "import"]
680
681        if imports:
682            warnings.warn("Import header tags are not supported")
683
684#        while imports:
685#            url = imports.pop(0)
686#            if uri not in self._resolved_imports:
687#                imported = self.parse_file(open(url, "rb"))
688#                ontology.update(imported)
689#                self._resolved_imports.append(uri)
690
691    def dump(self, file):
692        """
693        Dump the contents of the ontology to a `file` in .obo format.
694
695        :param file-like file:
696            A file like object.
697
698        """
699        if isinstance(file, basestring):
700            file = open(file, "wb")
701
702        for key, value in self.header_tags:
703            file.write(key + ": " + value + "\n")
704
705        # Skip the builtins
706        for object in self.objects[len(self.BUILTINS):]:
707            file.write("\n")
708            file.write(object.format_stanza())
709            file.write("\n")
710
711    def update(self, other):
712        """
713        Update this ontology with the terms from `other`.
714        """
715        for term in other:
716            if term.id in self:
717                if not term.is_annonymous:
718                    self.term(term.id).update(term)
719                else:  # Do nothing
720                    pass
721            else:
722                self.add_object(term)
723        self._invalid_cache_flag = True
724
725    def _cache_validate(self, force=False):
726        """
727        Update the relations cache if `self._invalid_cache` flag is set.
728        """
729        if self._invalid_cache_flag or force:
730            self._cache_relations()
731
732    def _cache_relations(self):
733        """
734        Collect all relations from parent to a child and store it in
735        `self._related_to` member.
736
737        """
738        related_to = defaultdict(list)
739        for obj in self.objects:
740            for rel_type, id in self.related_terms(obj):
741                term = self.term(id)
742                related_to[term].append((rel_type, obj))
743
744        self._related_to = related_to
745        self._invalid_cache_flag = False
746
747    def term(self, id):
748        """
749        Return the :class:`OBOObject` associated with this id.
750
751        :param str id:
752            Term id string.
753
754        """
755        if isinstance(id, basestring):
756            if id in self.id2term:
757                return self.id2term[id]
758            elif id in self.alt2id:
759                return self.id2term[self.alt2id[id]]
760            else:
761                raise ValueError("Unknown term id: %r" % id)
762        elif isinstance(id, OBOObject):
763            return id
764
765    def terms(self):
766        """
767        Return all :class:`Term` instances in the ontology.
768        """
769        return [obj for obj in self.objects if obj.stanza_type == "Term"]
770
771    def term_by_name(self, name):
772        """
773        Return the term with name `name`.
774        """
775        terms = [t for t in self.terms() if t.name == name]
776        if len(terms) != 1:
777            raise ValueError("Unknown term name: %r" % name)
778        return terms[0]
779
780    def typedefs(self):
781        """
782        Return all :class:`Typedef` instances in the ontology.
783        """
784        return [obj for obj in self.objects if obj.stanza_type == "Typedef"]
785
786    def instances(self):
787        """
788        Return all :class:`Instance` instances in the ontology.
789        """
790        return [obj for obj in self.objects if obj.stanza_type == "Instance"]
791
792    def related_terms(self, term):
793        """
794        Return a list of (`rel_type`, `term_id`) tuples where `rel_type` is
795        relationship type (e.g. 'is_a', 'has_part', ...) and `term_id` is
796        the id of the term in the relationship.
797
798        """
799        term = self.term(term) if not isinstance(term, OBOObject) else term
800        related = [(tag, value)
801                   for tag in ["is_a"]  # TODO: add other typedef ids
802                   for value in term.values.get(tag, [])]
803        relationships = term.values.get("relationship", [])
804        for rel in relationships:
805            related.append(tuple(rel.split(None, 1)))
806        return related
807
808    def edge_types(self):
809        """
810        Return a list of all edge types in the ontology.
811        """
812        return [obj.id for obj in self.objects if obj.stanza_type == "Typedef"]
813
814    def parent_edges(self, term):
815        """
816        Return a list of (rel_type, parent_term) tuples.
817        """
818        term = self.term(term)
819        parents = []
820        for rel_type, parent in self.related_terms(term):
821            parents.append((rel_type, self.term(parent)))
822        return parents
823
824    def child_edges(self, term):
825        """
826        Return a list of (rel_type, source_term) tuples.
827        """
828        self._cache_validate()
829        term = self.term(term)
830        return self._related_to.get(term, [])
831
832    def super_terms(self, term):
833        """
834        Return a set of all super terms of `term` up to the most general one.
835        """
836        terms = self.parent_terms(term)
837        visited = set()
838        queue = set(terms)
839        while queue:
840            term = queue.pop()
841            visited.add(term)
842            queue.update(self.parent_terms(term) - visited)
843        return visited
844
845    def sub_terms(self, term):
846        """
847        Return a set of all sub terms for `term`.
848        """
849        terms = self.child_terms(term)
850        visited = set()
851        queue = set(terms)
852        while queue:
853            term = queue.pop()
854            visited.add(term)
855            queue.update(self.child_terms(term) - visited)
856        return visited
857
858    def child_terms(self, term):
859        """
860        Return a set of all child terms for this `term`.
861        """
862        self._cache_validate()
863        term = self.term(term)
864        children = []
865        for rel_type, term in self.child_edges(term):
866            children.append(term)
867        return set(children)
868
869    def parent_terms(self, term):
870        """
871        Return a set of all parent terms for this `term`
872        """
873        term = self.term(term)
874        parents = []
875        for rel_type, id in self.parent_edges(term):
876            parents.append(self.term(id))
877        return set(parents)
878
879    def relations(self):
880        """
881        Return a list of all relations in the ontology.
882        """
883        relations = []
884        for obj in self.objects:
885            for type_id, id in  obj.related:
886                target_term = self.term(id)
887            relations.append((obj, type_id, target_term))
888        return relations
889
890    def __len__(self):
891        return len(self.objects)
892
893    def __iter__(self):
894        return iter(self.objects)
895
896    def __contains__(self, obj):
897        if isinstance(obj, basestring):
898            return obj in self.id2term
899        else:
900            return obj in self.objects
901
902    def __getitem__(self, key):
903        return self.id2term[key]
904
905    def has_key(self, key):
906        return key in self.id2term
907
908    def traverse_bf(self, term):
909        """
910        BF traverse of the ontology down from term.
911        """
912        queue = list(self.child_terms(term))
913        while queue:
914            term = queue.pop(0)
915            queue.extend(self.child_terms(term))
916            yield term
917
918    def traverse_df(self, term, depth=1e30):
919        """
920        DF traverse of the ontology down from term.
921        """
922        if depth >= 1:
923            for child in self.child_terms(term):
924                yield child
925                for t in self.traverse_df(child, depth - 1):
926                    yield t
927
928    def to_network(self, terms=None):
929        """
930        Return an Orange.network.Network instance constructed from
931        this ontology.
932
933        """
934        edge_types = self.edge_types()
935        terms = self.terms()
936        from Orange.orng import orngNetwork
937        import orange
938
939        network = orngNetwork.Network(len(terms), True, len(edge_types))
940        network.objects = dict([(term.id, i) for i, term in enumerate(terms)])
941
942        edges = defaultdict(set)
943        for term in self.terms():
944            related = self.related_terms(term)
945            for relType, relTerm in related:
946                edges[(term.id, relTerm)].add(relType)
947
948        edgeitems = edges.items()
949        for (src, dst), eTypes in edgeitems:
950            network[src, dst] = [1 if e in eTypes else 0 for e in edge_types]
951
952        domain = orange.Domain([orange.StringVariable("id"),
953                                orange.StringVariable("name"),
954                                orange.StringVariable("def"),
955                                ], False)
956
957        items = orange.ExampleTable(domain)
958        for term in terms:
959            ex = orange.Example(domain, [term.id, term.name, term.values.get("def", [""])[0]])
960            items.append(ex)
961
962        relationships = set([", ".join(sorted(eTypes)) for (_, _), eTypes in edgeitems])
963        domain = orange.Domain([orange.FloatVariable("u"),
964                                orange.FloatVariable("v"),
965                                orange.EnumVariable("relationship", values=list(edge_types))
966                                ], False)
967
968        id2index = dict([(term.id, i + 1) for i, term in enumerate(terms)])
969        links = orange.ExampleTable(domain)
970        for (src, dst), eTypes in edgeitems:
971            ex = orange.Example(domain, [id2index[src], id2index[dst], eTypes.pop()])
972            links.append(ex)
973
974        network.items = items
975        network.links = links
976        network.optimization = None
977        return network
978
979    def to_networkx(self, terms=None):
980        """
981        Return a NetworkX graph of this ontology.
982        """
983        import networkx
984        graph = networkx.Graph()
985
986        edge_types = self.edge_types()
987
988        edge_colors = {"is_a": "red"}
989
990        if terms is None:
991            terms = self.terms()
992        else:
993            terms = [self.term(term) for term in terms]
994            super_terms = [self.super_terms(term) for term in terms]
995            terms = reduce(set.union, super_terms, set(terms))
996
997        for term in terms:
998            graph.add_node(term.id, name=term.name)
999
1000        for term in terms:
1001            for rel_type, rel_term in self.related_terms(term):
1002                rel_term = self.term(rel_term)
1003                if rel_term in terms:
1004                    graph.add_edge(term.id, rel_term.id, label=rel_type,
1005                                   color=edge_colors.get(rel_type, "blue"))
1006
1007        return graph
1008
1009    def to_graphviz(self, terms=None):
1010        """
1011        Return an pygraphviz.AGraph representation of the ontology.
1012        If `terms` is not `None` it must be a list of terms in the ontology.
1013        The graph will in this case contain only the super graph of those
1014        terms.
1015
1016        """
1017        import pygraphviz as pgv
1018        graph = pgv.AGraph(directed=True, name="ontology")
1019
1020        edge_types = self.edge_types()
1021
1022        edge_colors = {"is_a": "red"}
1023
1024        if terms is None:
1025            terms = self.terms()
1026        else:
1027            terms = [self.term(term) for term in terms]
1028            super_terms = [self.super_terms(term) for term in terms]
1029            terms = reduce(set.union, super_terms, set(terms))
1030
1031        for term in terms:
1032            graph.add_node(term.id, name=term.name)
1033
1034        for term in terms:
1035            for rel_type, rel_term in self.related_terms(term):
1036                rel_term = self.term(rel_term)
1037                if rel_term in terms:
1038                    graph.add_edge(term.id, rel_term.id, label=rel_type,
1039                                   color=edge_colors.get(rel_type, "blue"))
1040
1041        return graph
1042
1043
1044def load(file):
1045    """
1046    Load an ontology from a .obo file
1047    """
1048    return OBOOntology(file)
1049
1050
1051def foundry_ontologies():
1052    """
1053    Return a list of ontologies available from the OBOFoundry `website
1054    <http://www.obofoundry.org/>`_. The list contains a tuples of the form
1055    `(title, url)` for instance
1056    ``('Biological process', 'http://purl.obolibrary.org/obo/go.obo')``
1057
1058    """
1059    stream = urllib2.urlopen("http://www.obofoundry.org/")
1060    text = stream.read()
1061    pattern = r'<td class=".+?">\s*<a href=".+?">(.+?)</a>\s*</td>\s*<td class=".+?">.*?</td>\s*<td class=".+?">.*?</td>\s*?<td class=".+?">\s*<a href="(.+?obo)">.+?</a>'
1062    return re.findall(pattern, text)
1063
1064
1065if __name__ == "__main__":
1066    import doctest
1067    stanza = '''[Term]
1068id: FOO:001
1069name: bar
1070'''
1071    seinfeld = StringIO("""
1072[Typedef]
1073id: parent
1074
1075[Typedef]
1076id: child
1077inverse_of: parent ! not actually used yet
1078
1079[Term]
1080id: 001
1081name: George
1082
1083[Term]
1084id: 002
1085name: Estelle
1086relationship: parent 001 ! George
1087
1088[Term]
1089id: 003
1090name: Frank
1091relationship: parent 001 ! George
1092
1093""")  # TODO: fill the ontology with all characters
1094    term = OBOObject.parse_stanza(stanza)
1095
1096    seinfeld = OBOOntology(seinfeld)
1097    print seinfeld.child_edges("001")
1098
1099    doctest.testmod(extraglobs={"stanza": stanza, "term": term},
1100                    optionflags=doctest.ELLIPSIS)
Note: See TracBrowser for help on using the repository browser.