src/jalview/ext/so/SequenceOntology.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.ext.so;
  22
  23 import jalview.bin.Cache;
  24 import jalview.datamodel.ontology.OntologyBase;
  25 import jalview.io.gff.SequenceOntologyI;
  26
  27 import java.io.BufferedInputStream;
  28 import java.io.BufferedReader;
  29 import java.io.IOException;
  30 import java.io.InputStream;
  31 import java.io.InputStreamReader;
  32 import java.text.ParseException;
  33 import java.util.ArrayList;
  34 import java.util.Collections;
  35 import java.util.HashMap;
  36 import java.util.HashSet;
  37 import java.util.List;
  38 import java.util.Map;
  39 import java.util.NoSuchElementException;
  40 import java.util.Set;
  41 import java.util.zip.ZipEntry;
  42 import java.util.zip.ZipInputStream;
  43
  44 import org.biojava.nbio.ontology.Ontology;
  45 import org.biojava.nbio.ontology.Synonym;
  46 import org.biojava.nbio.ontology.Term;
  47 import org.biojava.nbio.ontology.Term.Impl;
  48 import org.biojava.nbio.ontology.Triple;
  49 import org.biojava.nbio.ontology.io.OboParser;
  50 import org.biojava.nbio.ontology.utils.Annotation;
  51
  52 /**
  53  * A wrapper class that parses the Sequence Ontology and exposes useful access
  54  * methods. This version uses the BioJava parser.
  55  */
  56 public class SequenceOntology extends OntologyBase
  57         implements SequenceOntologyI
  58 {
  59   /*
  60    * the parsed Ontology data as modelled by BioJava
  61    */
  62   private Ontology ontology;
  63
  64   /*
  65    * the ontology term for the isA relationship
  66    */
  67   private Term isA;
  68
  69   /*
  70    * lookup of terms by user readable name (NB not guaranteed unique)
  71    */
  72   private Map<String, Term> aliases;
  73
  74   /*
  75    * Map where key is a Term and value is a (possibly empty) list of
  76    * all Terms to which the key has an 'isA' relationship, either
  77    * directly or indirectly (A isA B isA C)
  78    */
  79   private Map<Term, List<Term>> termIsA;
  80
  81   private List<String> termsFound;
  82
  83   private List<String> termsNotFound;
  84
  85   /**
  86    * Package private constructor to enforce use of singleton. Parses and caches
  87    * the SO OBO data file.
  88    */
  89   public SequenceOntology()
  90   {
  91     termsFound = new ArrayList<>();
  92     termsNotFound = new ArrayList<>();
  93     aliases = new HashMap<>();
  94     termIsA = new HashMap<>();
  95
  96     loadOntologyZipFile("so-simple.obo");
  97   }
  98
  99   /**
 100    * Loads the given ontology file from a zip file with ".zip" appended
 101    *
 102    * @param ontologyFile
 103    */
 104   protected void loadOntologyZipFile(String ontologyFile)
 105   {
 106     long now = System.currentTimeMillis();
 107     ZipInputStream zipStream = null;
 108     try
 109     {
 110       String zipFile = ontologyFile + ".zip";
 111       InputStream inStream = this.getClass()
 112               .getResourceAsStream("/" + zipFile);
 113       zipStream = new ZipInputStream(new BufferedInputStream(inStream));
 114       ZipEntry entry;
 115       while ((entry = zipStream.getNextEntry()) != null)
 116       {
 117         if (entry.getName().equals(ontologyFile))
 118         {
 119           loadOboFile(zipStream);
 120         }
 121       }
 122       long elapsed = System.currentTimeMillis() - now;
 123       System.out.println("Loaded Sequence Ontology from " + zipFile + " ("
 124               + elapsed + "ms)");
 125     } catch (Exception e)
 126     {
 127       e.printStackTrace();
 128     } finally
 129     {
 130       closeStream(zipStream);
 131     }
 132   }
 133
 134   /**
 135    * Closes the input stream, swallowing all exceptions
 136    *
 137    * @param is
 138    */
 139   protected void closeStream(InputStream is)
 140   {
 141     if (is != null)
 142     {
 143       try
 144       {
 145         is.close();
 146       } catch (IOException e)
 147       {
 148         // ignore
 149       }
 150     }
 151   }
 152
 153   /**
 154    * Reads, parses and stores the OBO file data
 155    *
 156    * @param is
 157    * @throws ParseException
 158    * @throws IOException
 159    */
 160   protected void loadOboFile(InputStream is)
 161           throws ParseException, IOException
 162   {
 163     BufferedReader oboFile = new BufferedReader(new InputStreamReader(is));
 164     OboParser parser = new OboParser();
 165     ontology = parser.parseOBO(oboFile, "SO", "the SO ontology");
 166     isA = ontology.getTerm("is_a");
 167     storeTermAliases();
 168   }
 169
 170   /**
 171    * Stores a lookup table of terms by description or synonym. Note that
 172    * description is not guaranteed unique. Where duplicate descriptions are
 173    * found, try to discard the term that is flagged as obsolete. However we do
 174    * store obsolete terms where there is no duplication of description.
 175    */
 176   protected void storeTermAliases()
 177   {
 178     Set<String> ambiguous = new HashSet<>();
 179
 180     for (Term term : ontology.getTerms())
 181     {
 182       if (term instanceof Impl)
 183       {
 184         boolean newTermIsObsolete = isObsolete(term);
 185         String description = term.getDescription();
 186         if (description != null)
 187         {
 188           description = canonicalise(description);
 189           Term replaced = aliases.get(description);
 190           if (replaced != null)
 191           {
 192             boolean oldTermIsObsolete = isObsolete(replaced);
 193             if (newTermIsObsolete && !oldTermIsObsolete)
 194             {
 195               Cache.log.debug("SequenceOntology ignoring " + term.getName()
 196                       + " as obsolete and duplicated by "
 197                       + replaced.getName());
 198               term = replaced;
 199             }
 200             else if (!newTermIsObsolete && oldTermIsObsolete)
 201             {
 202               Cache.log.debug("SequenceOntology ignoring "
 203                       + replaced.getName()
 204                       + " as obsolete and duplicated by " + term.getName());
 205             }
 206             else
 207             {
 208               Cache.log.debug("SequenceOntology warning: " + term.getName()
 209                       + " has replaced " + replaced.getName()
 210                       + " for lookup of '" + description + "'");
 211             }
 212           }
 213           aliases.put(description, term);
 214
 215           /*
 216            * also store synonyms if not ambiguous
 217            */
 218           if (!newTermIsObsolete)
 219           {
 220             storeSynonymsForTerm(term, ambiguous);
 221           }
 222         }
 223       }
 224     }
 225
 226     /*
 227      * remove ambiguous synonyms for safety;
 228      * problem: what if a synonym matches a description?
 229      * only one case found:
 230      * nmd_transcript is synonym for SO:0001621:NMD_transcript_variant
 231      * and also the description for SO:0002114:NMD_transcript
 232      */
 233     for (String syn : ambiguous)
 234     {
 235       aliases.remove(syn);
 236     }
 237   }
 238
 239   /**
 240    * Stores any synonyms as an alternative lookup for the term, canonicalised
 241    * for case/hyphen/space insensitivity on lookup.
 242    * <p>
 243    * Some synonyms may be ambiguous (present for more than one term), and these
 244    * are handled as follows:
 245    * <ul>
 246    * <li>if a synonym matches the <em>description</em> of another term, it is
 247    * not saved, so that a term can always be found by description
 248    * <ul>
 249    * <li>Example: {@code nmd_transcript} is the description for
 250    * {@code NMD_transcript} and also a synonym for
 251    * {@code NMD_transcript_variant} - the synonym is ignored</li>
 252    * </ul>
 253    * </li>
 254    * <li>if one term is a sub-term (directly or indirectly) of the other, the
 255    * synonym is retained for the more general term
 256    * <ul>
 257    * <li>Example: {@code helix} is a synonym for
 258    * {@code alpha_helix, right_handed_peptide_helix, peptide_helix} - it is kept
 259    * for {@code peptide_helix} as this is a parent of the other terms</li>
 260    * </ul>
 261    * </li>
 262    * <li>otherwise the synonym is added to the {@code ambiguous} list for
 263    * removal
 264    * <ul>
 265    * <li>Example: {@code sequence variation} is a synonym for
 266    * {@code sequence_alteration} and {@code alternate_sequence_site} but these
 267    * have no {@code isA} relationship - the synonym is ignored as ambiguous</li>
 268    * </ul>
 269    * </ul>
 270    *
 271    * @param term
 272    * @param ambiguous
 273    */
 274   void storeSynonymsForTerm(Term term, Set<String> ambiguous)
 275   {
 276     for (Object syn : term.getSynonyms())
 277     {
 278       String name = ((Synonym) syn).getName();
 279       String synonym = canonicalise(name);
 280       if (aliases.containsKey(synonym))
 281       {
 282         final Term found = aliases.get(synonym);
 283         if (found != term)
 284         {
 285           /*
 286            * this alias is ambiguous - matches description,
 287            * or an alias, of another term
 288            */
 289           String msg = String.format(
 290                   "SequenceOntology ambiguous synonym %s for '%s:%s' and '%s:%s'",
 291                   synonym, term.getName(), term.getDescription(),
 292                   found.getName(), found.getDescription());
 293           Cache.log.debug(msg);
 294
 295           /*
 296            * preserve any entry whose canonical description happens to match
 297            * a synonym (NMD_transcript is a valid description, and also
 298            * a synonym for NMD_transcript_variant)
 299            * also preserve a parent (more general) term
 300            */
 301           if (synonym.equals(canonicalise(found.getDescription()))
 302                   || termIsA(term, found))
 303           {
 304             // leave it alone
 305           }
 306           /*
 307            * replace a specialised term with a more general one
 308            * with the same alias
 309            */
 310           // else if
 311           // (synonym.equals(canonicalise(term.getDescription())))
 312           else if (termIsA(found, term))
 313           {
 314             aliases.put(synonym, term);
 315           }
 316           else
 317           {
 318             ambiguous.add(synonym);
 319           }
 320         }
 321       }
 322       else
 323       {
 324         aliases.put(synonym, term);
 325       }
 326     }
 327   }
 328
 329   /**
 330    * Converts a string to lower case and changes hyphens and spaces to
 331    * underscores
 332    *
 333    * @param s
 334    * @return
 335    */
 336   static String canonicalise(String s)
 337   {
 338     return s == null ? null
 339             : s.toLowerCase().replace('-', '_').replace(' ', '_');
 340   }
 341
 342   /**
 343    * Answers true if the term has property "is_obsolete" with value true, else
 344    * false
 345    *
 346    * @param term
 347    * @return
 348    */
 349   public static boolean isObsolete(Term term)
 350   {
 351     Annotation ann = term.getAnnotation();
 352     if (ann != null)
 353     {
 354       try
 355       {
 356         if (Boolean.TRUE.equals(ann.getProperty("is_obsolete")))
 357         {
 358           return true;
 359         }
 360       } catch (NoSuchElementException e)
 361       {
 362         // fall through to false
 363       }
 364     }
 365     return false;
 366   }
 367
 368   /**
 369    * Test whether the given Sequence Ontology term is nucleotide_match (either
 370    * directly or via is_a relationship)
 371    *
 372    * @param soTerm
 373    *          SO name or description
 374    * @return
 375    */
 376   public boolean isNucleotideMatch(String soTerm)
 377   {
 378     return isA(soTerm, NUCLEOTIDE_MATCH);
 379   }
 380
 381   /**
 382    * Test whether the given Sequence Ontology term is protein_match (either
 383    * directly or via is_a relationship)
 384    *
 385    * @param soTerm
 386    *          SO name or description
 387    * @return
 388    */
 389   public boolean isProteinMatch(String soTerm)
 390   {
 391     return isA(soTerm, PROTEIN_MATCH);
 392   }
 393
 394   /**
 395    * Test whether the given Sequence Ontology term is polypeptide (either
 396    * directly or via is_a relationship)
 397    *
 398    * @param soTerm
 399    *          SO name or description
 400    * @return
 401    */
 402   public boolean isPolypeptide(String soTerm)
 403   {
 404     return isA(soTerm, POLYPEPTIDE);
 405   }
 406
 407   /**
 408    * Returns true if the given term has a (direct or indirect) 'isA'
 409    * relationship with the parent
 410    *
 411    * @param child
 412    * @param parent
 413    * @return
 414    */
 415   @Override
 416   public boolean isA(String child, String parent)
 417   {
 418     if (child == null || parent == null)
 419     {
 420       return false;
 421     }
 422     /*
 423      * optimise trivial checks like isA("CDS", "CDS")
 424      */
 425     if (child.equals(parent))
 426     {
 427       termFound(child);
 428       return true;
 429     }
 430
 431     Term childTerm = getTerm(child);
 432     if (childTerm != null)
 433     {
 434       termFound(child);
 435     }
 436     else
 437     {
 438       termNotFound(child);
 439     }
 440     Term parentTerm = getTerm(parent);
 441
 442     return termIsA(childTerm, parentTerm);
 443   }
 444
 445   /**
 446    * Records a valid term queried for, for reporting purposes
 447    *
 448    * @param term
 449    */
 450   private void termFound(String term)
 451   {
 452     synchronized (termsFound)
 453     {
 454       if (!termsFound.contains(term))
 455       {
 456         termsFound.add(term);
 457       }
 458     }
 459   }
 460
 461   /**
 462    * Records an invalid term queried for, for reporting purposes
 463    *
 464    * @param term
 465    */
 466   private void termNotFound(String term)
 467   {
 468     synchronized (termsNotFound)
 469     {
 470       if (!termsNotFound.contains(term))
 471       {
 472         Cache.log.debug("SequenceOntology term " + term + " invalid");
 473         termsNotFound.add(term);
 474       }
 475     }
 476   }
 477
 478   /**
 479    * Returns true if the childTerm 'isA' parentTerm (directly or indirectly).
 480    *
 481    * @param childTerm
 482    * @param parentTerm
 483    * @return
 484    */
 485   protected synchronized boolean termIsA(Term childTerm, Term parentTerm)
 486   {
 487     /*
 488      * null term could arise from a misspelled SO description
 489      */
 490     if (childTerm == null || parentTerm == null)
 491     {
 492       return false;
 493     }
 494
 495     /*
 496      * recursive search endpoint:
 497      */
 498     if (childTerm == parentTerm)
 499     {
 500       return true;
 501     }
 502
 503     /*
 504      * lazy initialisation - find all of a term's parents (recursively)
 505      * the first time this is called, and save them in a map.
 506      */
 507     if (!termIsA.containsKey(childTerm))
 508     {
 509       findParents(childTerm);
 510     }
 511
 512     List<Term> parents = termIsA.get(childTerm);
 513     for (Term parent : parents)
 514     {
 515       if (termIsA(parent, parentTerm))
 516       {
 517         /*
 518          * add (great-)grandparents to parents list as they are discovered,
 519          * for faster lookup next time
 520          */
 521         if (!parents.contains(parentTerm))
 522         {
 523           parents.add(parentTerm);
 524         }
 525         return true;
 526       }
 527     }
 528
 529     return false;
 530   }
 531
 532   /**
 533    * Finds all the 'isA' parents of the childTerm and stores them as a (possibly
 534    * empty) list.
 535    *
 536    * @param childTerm
 537    */
 538   protected synchronized void findParents(Term childTerm)
 539   {
 540     List<Term> result = new ArrayList<>();
 541     for (Triple triple : ontology.getTriples(childTerm, null, isA))
 542     {
 543       Term parent = triple.getObject();
 544       result.add(parent);
 545
 546       /*
 547        * and search for the parent's parents recursively
 548        */
 549       findParents(parent);
 550     }
 551     termIsA.put(childTerm, result);
 552   }
 553
 554   /**
 555    * Returns the Term for a given name (e.g. "SO:0000735") or description (e.g.
 556    * "sequence_location"), or alias, or null if not found
 557    *
 558    * @param child
 559    * @return
 560    */
 561   protected Term getTerm(final String nameOrDescription)
 562   {
 563     if (nameOrDescription == null)
 564     {
 565       return null;
 566     }
 567     Term t = aliases.get(canonicalise(nameOrDescription));
 568     if (t == null)
 569     {
 570       try
 571       {
 572         t = ontology.getTerm(nameOrDescription);
 573       } catch (NoSuchElementException e)
 574       {
 575         // not found
 576       }
 577     }
 578     return t;
 579   }
 580
 581   public boolean isSequenceVariant(String soTerm)
 582   {
 583     return isA(soTerm, SEQUENCE_VARIANT);
 584   }
 585
 586   /**
 587    * Sorts (case-insensitive) and returns the list of valid terms queried for
 588    */
 589   @Override
 590   public List<String> termsFound()
 591   {
 592     synchronized (termsFound)
 593     {
 594       Collections.sort(termsFound, String.CASE_INSENSITIVE_ORDER);
 595       return termsFound;
 596     }
 597   }
 598
 599   /**
 600    * Sorts (case-insensitive) and returns the list of invalid terms queried for
 601    */
 602   @Override
 603   public List<String> termsNotFound()
 604   {
 605     synchronized (termsNotFound)
 606     {
 607       Collections.sort(termsNotFound, String.CASE_INSENSITIVE_ORDER);
 608       return termsNotFound;
 609     }
 610   }
 611
 612   /**
 613    * {@inheritDoc}
 614    *
 615    * @throws IllegalStateException
 616    *           if a loop is detected in the ontology
 617    */
 618   @Override
 619   public List<String> getRootParents(final String term)
 620   {
 621     /*
 622      * check in cache first
 623      */
 624     if (rootParents.containsKey(term))
 625     {
 626       return rootParents.get(term);
 627     }
 628     Term t = getTerm(term);
 629     if (t == null)
 630     {
 631       return null;
 632     }
 633
 634     /*
 635      * todo: check for loops using 'seen', allowing for alternate paths e.g.
 636      * stop_gained isA feature_truncation isA feature_variant
 637      * " isA nonsynonymous_variant ... isA geneVariant isA feature_variant
 638      */
 639     List<Term> seen = new ArrayList<>();
 640     List<Term> top = new ArrayList<>();
 641     List<Term> query = new ArrayList<>();
 642     query.add(t);
 643
 644     while (!query.isEmpty())
 645     {
 646       List<Term> nextQuery = new ArrayList<>();
 647       for (Term q : query)
 648       {
 649         Set<Triple> parents = ontology.getTriples(q, null, isA);
 650         if (parents.isEmpty())
 651         {
 652           /*
 653            * q has no parents so is a top level term
 654            */
 655           top.add(q);
 656         }
 657         else
 658         {
 659           /*
 660            * search all parent terms
 661            */
 662           for (Triple triple : parents)
 663           {
 664             Term parent = triple.getObject();
 665             nextQuery.add(parent);
 666           }
 667         }
 668       }
 669       query = nextQuery;
 670     }
 671
 672     List<String> result = new ArrayList<>();
 673     for (Term found : top)
 674     {
 675       String desc = found.getDescription();
 676       if (!result.contains(desc))
 677       {
 678         result.add(desc);
 679       }
 680     }
 681
 682     /*
 683      * save result in cache
 684      */
 685     rootParents.put(term, result);
 686
 687     return result;
 688   }
 689
 690   @Override
 691   public List<String> getParents(String term)
 692   {
 693     List<String> parents = new ArrayList<>();
 694     Term t = getTerm(term);
 695     if (t != null)
 696     {
 697       for (Triple triple : ontology.getTriples(t, null, isA))
 698       {
 699         Term parent = triple.getObject();
 700         parents.add(parent.getDescription());
 701       }
 702     }
 703     return parents;
 704   }
 705
 706   @Override
 707   public boolean isValidTerm(String term)
 708   {
 709     return getTerm(term) != null;
 710   }
 711 }