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.datamodel.ontology.OntologyBase;
  24 import jalview.io.gff.SequenceOntologyI;
  25
  26 import java.io.BufferedInputStream;
  27 import java.io.BufferedReader;
  28 import java.io.IOException;
  29 import java.io.InputStream;
  30 import java.io.InputStreamReader;
  31 import java.text.ParseException;
  32 import java.util.ArrayList;
  33 import java.util.Collections;
  34 import java.util.HashMap;
  35 import java.util.List;
  36 import java.util.Map;
  37 import java.util.NoSuchElementException;
  38 import java.util.Set;
  39 import java.util.zip.ZipEntry;
  40 import java.util.zip.ZipInputStream;
  41
  42 import org.biojava.nbio.ontology.Ontology;
  43 import org.biojava.nbio.ontology.Term;
  44 import org.biojava.nbio.ontology.Term.Impl;
  45 import org.biojava.nbio.ontology.Triple;
  46 import org.biojava.nbio.ontology.io.OboParser;
  47 import org.biojava.nbio.ontology.utils.Annotation;
  48
  49 /**
  50  * A wrapper class that parses the Sequence Ontology and exposes useful access
  51  * methods. This version uses the BioJava parser.
  52  */
  53 public class SequenceOntology extends OntologyBase
  54         implements SequenceOntologyI
  55 {
  56   /*
  57    * the parsed Ontology data as modelled by BioJava
  58    */
  59   private Ontology ontology;
  60
  61   /*
  62    * the ontology term for the isA relationship
  63    */
  64   private Term isA;
  65
  66   /*
  67    * lookup of terms by user readable name (NB not guaranteed unique)
  68    */
  69   private Map<String, Term> termsByDescription;
  70
  71   /*
  72    * Map where key is a Term and value is a (possibly empty) list of
  73    * all Terms to which the key has an 'isA' relationship, either
  74    * directly or indirectly (A isA B isA C)
  75    */
  76   private Map<Term, List<Term>> termIsA;
  77
  78   private List<String> termsFound;
  79
  80   private List<String> termsNotFound;
  81
  82   /**
  83    * Package private constructor to enforce use of singleton. Parses and caches
  84    * the SO OBO data file.
  85    */
  86   public SequenceOntology()
  87   {
  88     termsFound = new ArrayList<>();
  89     termsNotFound = new ArrayList<>();
  90     termsByDescription = new HashMap<>();
  91     termIsA = new HashMap<>();
  92
  93     loadOntologyZipFile("so-xp-simple.obo");
  94   }
  95
  96   /**
  97    * Loads the given ontology file from a zip file with ".zip" appended
  98    *
  99    * @param ontologyFile
 100    */
 101   protected void loadOntologyZipFile(String ontologyFile)
 102   {
 103     long now = System.currentTimeMillis();
 104     ZipInputStream zipStream = null;
 105     try
 106     {
 107       String zipFile = ontologyFile + ".zip";
 108       InputStream inStream = this.getClass()
 109               .getResourceAsStream("/" + zipFile);
 110       zipStream = new ZipInputStream(new BufferedInputStream(inStream));
 111       ZipEntry entry;
 112       while ((entry = zipStream.getNextEntry()) != null)
 113       {
 114         if (entry.getName().equals(ontologyFile))
 115         {
 116           loadOboFile(zipStream);
 117         }
 118       }
 119       long elapsed = System.currentTimeMillis() - now;
 120       System.out.println("Loaded Sequence Ontology from " + zipFile + " ("
 121               + elapsed + "ms)");
 122     } catch (Exception e)
 123     {
 124       e.printStackTrace();
 125     } finally
 126     {
 127       closeStream(zipStream);
 128     }
 129   }
 130
 131   /**
 132    * Closes the input stream, swallowing all exceptions
 133    *
 134    * @param is
 135    */
 136   protected void closeStream(InputStream is)
 137   {
 138     if (is != null)
 139     {
 140       try
 141       {
 142         is.close();
 143       } catch (IOException e)
 144       {
 145         // ignore
 146       }
 147     }
 148   }
 149
 150   /**
 151    * Reads, parses and stores the OBO file data
 152    *
 153    * @param is
 154    * @throws ParseException
 155    * @throws IOException
 156    */
 157   protected void loadOboFile(InputStream is)
 158           throws ParseException, IOException
 159   {
 160     BufferedReader oboFile = new BufferedReader(new InputStreamReader(is));
 161     OboParser parser = new OboParser();
 162     ontology = parser.parseOBO(oboFile, "SO", "the SO ontology");
 163     isA = ontology.getTerm("is_a");
 164     storeTermNames();
 165   }
 166
 167   /**
 168    * Stores a lookup table of terms by description. Note that description is not
 169    * guaranteed unique. Where duplicate descriptions are found, try to discard
 170    * the term that is flagged as obsolete. However we do store obsolete terms
 171    * where there is no duplication of description.
 172    */
 173   protected void storeTermNames()
 174   {
 175     for (Term term : ontology.getTerms())
 176     {
 177       if (term instanceof Impl)
 178       {
 179         String description = term.getDescription();
 180         if (description != null)
 181         {
 182           Term replaced = termsByDescription.get(description);
 183           if (replaced != null)
 184           {
 185             boolean newTermIsObsolete = isObsolete(term);
 186             boolean oldTermIsObsolete = isObsolete(replaced);
 187             if (newTermIsObsolete && !oldTermIsObsolete)
 188             {
 189               System.err.println("Ignoring " + term.getName()
 190                       + " as obsolete and duplicated by "
 191                       + replaced.getName());
 192               term = replaced;
 193             }
 194             else if (!newTermIsObsolete && oldTermIsObsolete)
 195             {
 196               System.err.println("Ignoring " + replaced.getName()
 197                       + " as obsolete and duplicated by " + term.getName());
 198             }
 199             else
 200             {
 201               System.err.println("Warning: " + term.getName()
 202                       + " has replaced " + replaced.getName()
 203                       + " for lookup of '" + description + "'");
 204             }
 205           }
 206           termsByDescription.put(description, term);
 207         }
 208       }
 209     }
 210   }
 211
 212   /**
 213    * Answers true if the term has property "is_obsolete" with value true, else
 214    * false
 215    *
 216    * @param term
 217    * @return
 218    */
 219   public static boolean isObsolete(Term term)
 220   {
 221     Annotation ann = term.getAnnotation();
 222     if (ann != null)
 223     {
 224       try
 225       {
 226         if (Boolean.TRUE.equals(ann.getProperty("is_obsolete")))
 227         {
 228           return true;
 229         }
 230       } catch (NoSuchElementException e)
 231       {
 232         // fall through to false
 233       }
 234     }
 235     return false;
 236   }
 237
 238   /**
 239    * Test whether the given Sequence Ontology term is nucleotide_match (either
 240    * directly or via is_a relationship)
 241    *
 242    * @param soTerm
 243    *          SO name or description
 244    * @return
 245    */
 246   public boolean isNucleotideMatch(String soTerm)
 247   {
 248     return isA(soTerm, NUCLEOTIDE_MATCH);
 249   }
 250
 251   /**
 252    * Test whether the given Sequence Ontology term is protein_match (either
 253    * directly or via is_a relationship)
 254    *
 255    * @param soTerm
 256    *          SO name or description
 257    * @return
 258    */
 259   public boolean isProteinMatch(String soTerm)
 260   {
 261     return isA(soTerm, PROTEIN_MATCH);
 262   }
 263
 264   /**
 265    * Test whether the given Sequence Ontology term is polypeptide (either
 266    * directly or via is_a relationship)
 267    *
 268    * @param soTerm
 269    *          SO name or description
 270    * @return
 271    */
 272   public boolean isPolypeptide(String soTerm)
 273   {
 274     return isA(soTerm, POLYPEPTIDE);
 275   }
 276
 277   /**
 278    * Returns true if the given term has a (direct or indirect) 'isA'
 279    * relationship with the parent
 280    *
 281    * @param child
 282    * @param parent
 283    * @return
 284    */
 285   @Override
 286   public boolean isA(String child, String parent)
 287   {
 288     if (child == null || parent == null)
 289     {
 290       return false;
 291     }
 292     /*
 293      * optimise trivial checks like isA("CDS", "CDS")
 294      */
 295     if (child.equals(parent))
 296     {
 297       termFound(child);
 298       return true;
 299     }
 300
 301     Term childTerm = getTerm(child);
 302     if (childTerm != null)
 303     {
 304       termFound(child);
 305     }
 306     else
 307     {
 308       termNotFound(child);
 309     }
 310     Term parentTerm = getTerm(parent);
 311
 312     return termIsA(childTerm, parentTerm);
 313   }
 314
 315   /**
 316    * Records a valid term queried for, for reporting purposes
 317    *
 318    * @param term
 319    */
 320   private void termFound(String term)
 321   {
 322     synchronized (termsFound)
 323     {
 324       if (!termsFound.contains(term))
 325       {
 326         termsFound.add(term);
 327       }
 328     }
 329   }
 330
 331   /**
 332    * Records an invalid term queried for, for reporting purposes
 333    *
 334    * @param term
 335    */
 336   private void termNotFound(String term)
 337   {
 338     synchronized (termsNotFound)
 339     {
 340       if (!termsNotFound.contains(term))
 341       {
 342         System.err.println("SO term " + term + " invalid");
 343         termsNotFound.add(term);
 344       }
 345     }
 346   }
 347
 348   /**
 349    * Returns true if the childTerm 'isA' parentTerm (directly or indirectly).
 350    *
 351    * @param childTerm
 352    * @param parentTerm
 353    * @return
 354    */
 355   protected synchronized boolean termIsA(Term childTerm, Term parentTerm)
 356   {
 357     /*
 358      * null term could arise from a misspelled SO description
 359      */
 360     if (childTerm == null || parentTerm == null)
 361     {
 362       return false;
 363     }
 364
 365     /*
 366      * recursive search endpoint:
 367      */
 368     if (childTerm == parentTerm)
 369     {
 370       return true;
 371     }
 372
 373     /*
 374      * lazy initialisation - find all of a term's parents (recursively)
 375      * the first time this is called, and save them in a map.
 376      */
 377     if (!termIsA.containsKey(childTerm))
 378     {
 379       findParents(childTerm);
 380     }
 381
 382     List<Term> parents = termIsA.get(childTerm);
 383     for (Term parent : parents)
 384     {
 385       if (termIsA(parent, parentTerm))
 386       {
 387         /*
 388          * add (great-)grandparents to parents list as they are discovered,
 389          * for faster lookup next time
 390          */
 391         if (!parents.contains(parentTerm))
 392         {
 393           parents.add(parentTerm);
 394         }
 395         return true;
 396       }
 397     }
 398
 399     return false;
 400   }
 401
 402   /**
 403    * Finds all the 'isA' parents of the childTerm and stores them as a (possibly
 404    * empty) list.
 405    *
 406    * @param childTerm
 407    */
 408   protected synchronized void findParents(Term childTerm)
 409   {
 410     List<Term> result = new ArrayList<>();
 411     for (Triple triple : ontology.getTriples(childTerm, null, isA))
 412     {
 413       Term parent = triple.getObject();
 414       result.add(parent);
 415
 416       /*
 417        * and search for the parent's parents recursively
 418        */
 419       findParents(parent);
 420     }
 421     termIsA.put(childTerm, result);
 422   }
 423
 424   /**
 425    * Returns the Term for a given name (e.g. "SO:0000735") or description (e.g.
 426    * "sequence_location"), or null if not found.
 427    *
 428    * @param child
 429    * @return
 430    */
 431   protected Term getTerm(String nameOrDescription)
 432   {
 433     Term t = termsByDescription.get(nameOrDescription);
 434     if (t == null)
 435     {
 436       try
 437       {
 438         t = ontology.getTerm(nameOrDescription);
 439       } catch (NoSuchElementException e)
 440       {
 441         // not found
 442       }
 443     }
 444     return t;
 445   }
 446
 447   public boolean isSequenceVariant(String soTerm)
 448   {
 449     return isA(soTerm, SEQUENCE_VARIANT);
 450   }
 451
 452   /**
 453    * Sorts (case-insensitive) and returns the list of valid terms queried for
 454    */
 455   @Override
 456   public List<String> termsFound()
 457   {
 458     synchronized (termsFound)
 459     {
 460       Collections.sort(termsFound, String.CASE_INSENSITIVE_ORDER);
 461       return termsFound;
 462     }
 463   }
 464
 465   /**
 466    * Sorts (case-insensitive) and returns the list of invalid terms queried for
 467    */
 468   @Override
 469   public List<String> termsNotFound()
 470   {
 471     synchronized (termsNotFound)
 472     {
 473       Collections.sort(termsNotFound, String.CASE_INSENSITIVE_ORDER);
 474       return termsNotFound;
 475     }
 476   }
 477
 478   /**
 479    * {@inheritDoc}
 480    *
 481    * @throws IllegalStateException
 482    *           if a loop is detected in the ontology
 483    */
 484   @Override
 485   public List<String> getRootParents(final String term)
 486   {
 487     /*
 488      * check in cache first
 489      */
 490     if (rootParents.containsKey(term))
 491     {
 492       return rootParents.get(term);
 493     }
 494     Term t = getTerm(term);
 495     if (t == null)
 496     {
 497       return null;
 498     }
 499
 500     /*
 501      * todo: check for loops using 'seen', allowing for alternate paths e.g.
 502      * stop_gained isA feature_truncation isA feature_variant
 503      * " isA nonsynonymous_variant ... isA geneVariant isA feature_variant
 504      */
 505     List<Term> seen = new ArrayList<>();
 506     List<Term> top = new ArrayList<>();
 507     List<Term> query = new ArrayList<>();
 508     query.add(t);
 509
 510     while (!query.isEmpty())
 511     {
 512       List<Term> nextQuery = new ArrayList<>();
 513       for (Term q : query)
 514       {
 515         Set<Triple> parents = ontology.getTriples(q, null, isA);
 516         if (parents.isEmpty())
 517         {
 518           /*
 519            * q has no parents so is a top level term
 520            */
 521           top.add(q);
 522         }
 523         else
 524         {
 525           /*
 526            * search all parent terms
 527            */
 528           for (Triple triple : parents)
 529           {
 530             Term parent = triple.getObject();
 531             nextQuery.add(parent);
 532           }
 533         }
 534       }
 535       query = nextQuery;
 536     }
 537
 538     List<String> result = new ArrayList<>();
 539     for (Term found : top)
 540     {
 541       String desc = found.getDescription();
 542       if (!result.contains(desc))
 543       {
 544         result.add(desc);
 545       }
 546     }
 547
 548     /*
 549      * save result in cache
 550      */
 551     rootParents.put(term, result);
 552
 553     return result;
 554   }
 555 }