src/jalview/analysis/CrossRef.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.analysis;
  22
  23 import jalview.datamodel.AlignedCodonFrame;
  24 import jalview.datamodel.Alignment;
  25 import jalview.datamodel.AlignmentI;
  26 import jalview.datamodel.DBRefEntry;
  27 import jalview.datamodel.DBRefSource;
  28 import jalview.datamodel.Mapping;
  29 import jalview.datamodel.Sequence;
  30 import jalview.datamodel.SequenceFeature;
  31 import jalview.datamodel.SequenceI;
  32 import jalview.util.DBRefUtils;
  33 import jalview.ws.SequenceFetcher;
  34 import jalview.ws.seqfetcher.ASequenceFetcher;
  35
  36 import java.util.ArrayList;
  37 import java.util.List;
  38 import java.util.Vector;
  39
  40 /**
  41  * Functions for cross-referencing sequence databases. user must first specify
  42  * if cross-referencing from protein or dna (set dna==true)
  43  *
  44  * @author JimP
  45  *
  46  */
  47 public class CrossRef
  48 {
  49   /*
  50    * A sub-class that ignores Parent attribute when comparing sequence
  51    * features. This avoids 'duplicate' CDS features that only
  52    * differ in their parent Transcript ids.
  53    */
  54   class MySequenceFeature extends SequenceFeature
  55   {
  56     private SequenceFeature feat;
  57
  58     MySequenceFeature(SequenceFeature sf)
  59     {
  60       this.feat = sf;
  61     }
  62
  63     @Override
  64     public boolean equals(Object o)
  65     {
  66       return feat.equals(o, true);
  67     }
  68   }
  69
  70   /**
  71    * Select just the DNA or protein references for a protein or dna sequence
  72    *
  73    * @param fromDna
  74    *          if true, select references from DNA (i.e. Protein databases), else
  75    *          DNA database references
  76    * @param refs
  77    *          a set of references to select from
  78    * @return
  79    */
  80   public static DBRefEntry[] findXDbRefs(boolean fromDna, DBRefEntry[] refs)
  81   {
  82     return DBRefUtils.selectRefs(refs, fromDna ? DBRefSource.PROTEINDBS
  83             : DBRefSource.DNACODINGDBS);
  84     // could attempt to find other cross
  85     // refs here - ie PDB xrefs
  86     // (not dna, not protein seq)
  87   }
  88
  89   /**
  90    * @param dna
  91    *          true if seqs are DNA seqs
  92    * @param seqs
  93    * @return a list of sequence database cross reference source types
  94    */
  95   public static String[] findSequenceXrefTypes(boolean dna, SequenceI[] seqs)
  96   {
  97     return findSequenceXrefTypes(dna, seqs, null);
  98   }
  99
 100   /**
 101    * Indirect references are references from other sequences from the dataset to
 102    * any of the direct DBRefEntrys on the given sequences.
 103    *
 104    * @param dna
 105    *          true if seqs are DNA seqs
 106    * @param seqs
 107    * @return a list of sequence database cross reference source types
 108    */
 109   public static String[] findSequenceXrefTypes(boolean dna,
 110           SequenceI[] seqs, AlignmentI dataset)
 111   {
 112     String[] dbrefs = null;
 113     List<String> refs = new ArrayList<String>();
 114     for (SequenceI seq : seqs)
 115     {
 116       if (seq != null)
 117       {
 118         SequenceI dss = seq;
 119         while (dss.getDatasetSequence() != null)
 120         {
 121           dss = dss.getDatasetSequence();
 122         }
 123         DBRefEntry[] rfs = findXDbRefs(dna, dss.getDBRefs());
 124         if (rfs != null)
 125         {
 126           for (DBRefEntry ref : rfs)
 127           {
 128             if (!refs.contains(ref.getSource()))
 129             {
 130               refs.add(ref.getSource());
 131             }
 132           }
 133         }
 134         if (dataset != null)
 135         {
 136           // search for references to this sequence's direct references.
 137           DBRefEntry[] lrfs = CrossRef.findXDbRefs(!dna, seq.getDBRefs());
 138           List<SequenceI> rseqs = new ArrayList<SequenceI>();
 139           CrossRef.searchDatasetXrefs(seq, !dna, lrfs, dataset, rseqs,
 140                   null); // don't need to specify codon frame for mapping here
 141           for (SequenceI rs : rseqs)
 142           {
 143             DBRefEntry[] xrs = findXDbRefs(dna, rs.getDBRefs());
 144             if (xrs != null)
 145             {
 146               for (DBRefEntry ref : xrs)
 147               {
 148                 if (!refs.contains(ref.getSource()))
 149                 {
 150                   refs.add(ref.getSource());
 151                 }
 152               }
 153             }
 154             // looks like copy and paste - change rfs to xrs?
 155             // for (int r = 0; rfs != null && r < rfs.length; r++)
 156             // {
 157             // if (!refs.contains(rfs[r].getSource()))
 158             // {
 159             // refs.add(rfs[r].getSource());
 160             // }
 161             // }
 162           }
 163         }
 164       }
 165     }
 166     if (refs.size() > 0)
 167     {
 168       dbrefs = new String[refs.size()];
 169       refs.toArray(dbrefs);
 170     }
 171     return dbrefs;
 172   }
 173
 174   public static boolean hasCdnaMap(SequenceI[] seqs)
 175   {
 176     // TODO unused - remove?
 177     String[] reftypes = findSequenceXrefTypes(false, seqs);
 178     for (int s = 0; s < reftypes.length; s++)
 179     {
 180       if (reftypes.equals(DBRefSource.EMBLCDS))
 181       {
 182         return true;
 183         // no map
 184       }
 185     }
 186     return false;
 187   }
 188
 189   public static SequenceI[] getCdnaMap(SequenceI[] seqs)
 190   {
 191     // TODO unused - remove?
 192     Vector cseqs = new Vector();
 193     for (int s = 0; s < seqs.length; s++)
 194     {
 195       DBRefEntry[] cdna = findXDbRefs(true, seqs[s].getDBRefs());
 196       for (int c = 0; c < cdna.length; c++)
 197       {
 198         if (cdna[c].getSource().equals(DBRefSource.EMBLCDS))
 199         {
 200           System.err
 201                   .println("TODO: unimplemented sequence retrieval for coding region sequence.");
 202           // TODO: retrieve CDS dataset sequences
 203           // need global dataset sequence retriever/resolver to reuse refs
 204           // and construct Mapping entry.
 205           // insert gaps in CDS according to peptide gaps.
 206           // add gapped sequence to cseqs
 207         }
 208       }
 209     }
 210     if (cseqs.size() > 0)
 211     {
 212       SequenceI[] rsqs = new SequenceI[cseqs.size()];
 213       cseqs.copyInto(rsqs);
 214       return rsqs;
 215     }
 216     return null;
 217
 218   }
 219
 220   /**
 221    *
 222    * @param seqs
 223    *          sequences whose xrefs are being retrieved
 224    * @param dna
 225    *          true if sequences are nucleotide
 226    * @param source
 227    * @param al
 228    *          alignment to search for cross-referenced sequences (and possibly
 229    *          add to)
 230    * @param addedPeers
 231    *          a list of sequences to add to if 'peers' to the original sequences
 232    *          are found e.g. alternative protein products for a protein's gene
 233    * @return products (as dataset sequences)
 234    */
 235   public static Alignment findXrefSequences(SequenceI[] seqs, boolean dna,
 236           String source, AlignmentI al, List<SequenceI> addedPeers)
 237   {
 238     AlignmentI dataset = al.getDataset() == null ? al : al.getDataset();
 239     List<SequenceI> rseqs = new ArrayList<SequenceI>();
 240     AlignedCodonFrame cf = new AlignedCodonFrame();
 241     for (SequenceI seq : seqs)
 242     {
 243       SequenceI dss = seq;
 244       while (dss.getDatasetSequence() != null)
 245       {
 246         dss = dss.getDatasetSequence();
 247       }
 248       boolean found = false;
 249       DBRefEntry[] xrfs = CrossRef.findXDbRefs(dna, dss.getDBRefs());
 250       if ((xrfs == null || xrfs.length == 0) && dataset != null)
 251       {
 252         System.out.println("Attempting to find ds Xrefs refs.");
 253         // FIXME should be dss not seq here?
 254         DBRefEntry[] lrfs = CrossRef.findXDbRefs(!dna, seq.getDBRefs());
 255         // less ambiguous would be a 'find primary dbRefEntry' method.
 256         // filter for desired source xref here
 257         found = CrossRef.searchDatasetXrefs(dss, !dna, lrfs, dataset,
 258                 rseqs, cf);
 259       }
 260       for (int r = 0; xrfs != null && r < xrfs.length; r++)
 261       {
 262         DBRefEntry xref = xrfs[r];
 263         if (source != null && !source.equals(xref.getSource()))
 264         {
 265           continue;
 266         }
 267         if (xref.hasMap())
 268         {
 269           if (xref.getMap().getTo() != null)
 270           {
 271             SequenceI rsq = new Sequence(xref.getMap().getTo());
 272             rseqs.add(rsq);
 273             if (xref.getMap().getMap().getFromRatio() != xref
 274                     .getMap().getMap().getToRatio())
 275             {
 276               // get sense of map correct for adding to product alignment.
 277               if (dna)
 278               {
 279                 // map is from dna seq to a protein product
 280                 cf.addMap(dss, rsq, xref.getMap().getMap());
 281               }
 282               else
 283               {
 284                 // map should be from protein seq to its coding dna
 285                 cf.addMap(rsq, dss, xref.getMap().getMap().getInverse());
 286               }
 287             }
 288             found = true;
 289           }
 290         }
 291         if (!found)
 292         {
 293           // do a bit more work - search for sequences with references matching
 294           // xrefs on this sequence.
 295           if (dataset != null)
 296           {
 297             found |= searchDataset(dss, xref, dataset, rseqs, cf); // ,false,!dna);
 298             if (found)
 299             {
 300               xrfs[r] = null; // we've recovered seqs for this one.
 301             }
 302           }
 303         }
 304       }
 305       if (!found)
 306       {
 307         if (xrfs != null && xrfs.length > 0)
 308         {
 309           // Try and get the sequence reference...
 310           /*
 311            * Ideal world - we ask for a sequence fetcher implementation here if
 312            * (jalview.io.RunTimeEnvironment.getSequenceFetcher()) (
 313            */
 314           ASequenceFetcher sftch = new SequenceFetcher();
 315           SequenceI[] retrieved = null;
 316           int l = xrfs.length;
 317           for (int r = 0; r < xrfs.length; r++)
 318           {
 319             // filter out any irrelevant or irretrievable references
 320             if (xrfs[r] == null
 321                     || ((source != null && !source.equals(xrfs[r]
 322                             .getSource())) || !sftch.isFetchable(xrfs[r]
 323                             .getSource())))
 324             {
 325               l--;
 326               xrfs[r] = null;
 327             }
 328           }
 329           if (l > 0)
 330           {
 331             System.out
 332                     .println("Attempting to retrieve cross referenced sequences.");
 333             DBRefEntry[] t = new DBRefEntry[l];
 334             l = 0;
 335             for (int r = 0; r < xrfs.length; r++)
 336             {
 337               if (xrfs[r] != null)
 338               {
 339                 t[l++] = xrfs[r];
 340               }
 341             }
 342             xrfs = t;
 343             try
 344             {
 345               retrieved = sftch.getSequences(xrfs, !dna);
 346               // problem here is we don't know which of xrfs resulted in which
 347               // retrieved element
 348             } catch (Exception e)
 349             {
 350               System.err
 351                       .println("Problem whilst retrieving cross references for Sequence : "
 352                               + seq.getName());
 353               e.printStackTrace();
 354             }
 355
 356             if (retrieved != null)
 357             {
 358               List<SequenceFeature> copiedFeatures = new ArrayList<SequenceFeature>();
 359               CrossRef me = new CrossRef();
 360               for (int rs = 0; rs < retrieved.length; rs++)
 361               {
 362                 // TODO: examine each sequence for 'redundancy'
 363                 DBRefEntry[] dbr = retrieved[rs].getDBRefs();
 364                 if (dbr != null && dbr.length > 0)
 365                 {
 366                   for (int di = 0; di < dbr.length; di++)
 367                   {
 368                     // find any entry where we should put in the sequence being
 369                     // cross-referenced into the map
 370                     Mapping map = dbr[di].getMap();
 371                     if (map != null)
 372                     {
 373                       if (map.getTo() != null && map.getMap() != null)
 374                       {
 375                         // should search the local dataset to find any existing
 376                         // candidates for To !
 377                         try
 378                         {
 379                           // compare ms with dss and replace with dss in mapping
 380                           // if map is congruent
 381                           SequenceI ms = map.getTo();
 382                           int sf = map.getMap().getToLowest();
 383                           int st = map.getMap().getToHighest();
 384                           SequenceI mappedrg = ms.getSubSequence(sf, st);
 385                           // SequenceI loc = dss.getSubSequence(sf, st);
 386                           if (mappedrg.getLength() > 0
 387                                   && ms.getSequenceAsString().equals(
 388                                           dss.getSequenceAsString()))
 389                           // && mappedrg.getSequenceAsString().equals(
 390                           // loc.getSequenceAsString()))
 391                           {
 392                             String msg = "Mapping updated from "
 393                                     + ms.getName()
 394                                     + " to retrieved crossreference "
 395                                     + dss.getName();
 396                             System.out.println(msg);
 397                             // method to update all refs of existing To on
 398                             // retrieved sequence with dss and merge any props
 399                             // on To onto dss.
 400                             map.setTo(dss);
 401                             /*
 402                              * copy sequence features as well, avoiding
 403                              * duplication (e.g. from 2 transcripts)
 404                              */
 405                             SequenceFeature[] sfs = ms
 406                                     .getSequenceFeatures();
 407                             if (sfs != null)
 408                             {
 409                               for (SequenceFeature feat : sfs)
 410                               {
 411                                 /*
 412                                  * we override SequenceFeature.equals here (but
 413                                  * not elsewhere) to ignore Parent attribute
 414                                  * TODO not quite working yet!
 415                                  */
 416                                 if (!copiedFeatures
 417                                         .contains(me.new MySequenceFeature(
 418                                                 feat)))
 419                                 {
 420                                   dss.addSequenceFeature(feat);
 421                                   copiedFeatures.add(feat);
 422                                 }
 423                               }
 424                             }
 425                             cf.addMap(retrieved[rs].getDatasetSequence(),
 426                                     dss, map.getMap());
 427                           }
 428                           else
 429                           {
 430                             addedPeers.add(map.getTo());
 431                             cf.addMap(retrieved[rs].getDatasetSequence(),
 432                                     map.getTo(), map.getMap());
 433                           }
 434                         } catch (Exception e)
 435                         {
 436                           System.err
 437                                   .println("Exception when consolidating Mapped sequence set...");
 438                           e.printStackTrace(System.err);
 439                         }
 440                       }
 441                     }
 442                   }
 443                 }
 444                 retrieved[rs].updatePDBIds();
 445                 rseqs.add(retrieved[rs]);
 446               }
 447             }
 448           }
 449         }
 450       }
 451     }
 452
 453     Alignment ral = null;
 454     if (rseqs.size() > 0)
 455     {
 456       ral = new Alignment(rseqs.toArray(new SequenceI[rseqs.size()]));
 457       if (cf != null && !cf.isEmpty())
 458       {
 459         ral.addCodonFrame(cf);
 460       }
 461     }
 462     return ral;
 463   }
 464
 465   /**
 466    * find references to lrfs in the cross-reference set of each sequence in
 467    * dataset (that is not equal to sequenceI) Identifies matching DBRefEntry
 468    * based on source and accession string only - Map and Version are nulled.
 469    *
 470    * @param sequenceI
 471    * @param lrfs
 472    * @param dataset
 473    * @param rseqs
 474    * @return true if matches were found.
 475    */
 476   private static boolean searchDatasetXrefs(SequenceI sequenceI,
 477           boolean dna, DBRefEntry[] lrfs, AlignmentI dataset,
 478           List<SequenceI> rseqs, AlignedCodonFrame cf)
 479   {
 480     boolean found = false;
 481     if (lrfs == null)
 482     {
 483       return false;
 484     }
 485     for (int i = 0; i < lrfs.length; i++)
 486     {
 487       DBRefEntry xref = new DBRefEntry(lrfs[i]);
 488       // add in wildcards
 489       xref.setVersion(null);
 490       xref.setMap(null);
 491       found = searchDataset(sequenceI, xref, dataset, rseqs, cf, false, dna);
 492     }
 493     return found;
 494   }
 495
 496   /**
 497    * search a given sequence dataset for references matching cross-references to
 498    * the given sequence
 499    *
 500    * @param sequenceI
 501    * @param xrf
 502    * @param dataset
 503    * @param rseqs
 504    *          set of unique sequences
 505    * @param cf
 506    * @return true if one or more unique sequences were found and added
 507    */
 508   public static boolean searchDataset(SequenceI sequenceI, DBRefEntry xrf,
 509           AlignmentI dataset, List<SequenceI> rseqs, AlignedCodonFrame cf)
 510   {
 511     return searchDataset(sequenceI, xrf, dataset, rseqs, cf, true, false);
 512   }
 513
 514   /**
 515    * TODO: generalise to different protein classifications Search dataset for
 516    * DBRefEntrys matching the given one (xrf) and add the associated sequence to
 517    * rseq.
 518    *
 519    * @param sequenceI
 520    * @param xrf
 521    * @param dataset
 522    * @param rseqs
 523    * @param direct
 524    *          - search all references or only subset
 525    * @param dna
 526    *          search dna or protein xrefs (if direct=false)
 527    * @return true if relationship found and sequence added.
 528    */
 529   public static boolean searchDataset(SequenceI sequenceI, DBRefEntry xrf,
 530           AlignmentI dataset, List<SequenceI> rseqs, AlignedCodonFrame cf,
 531           boolean direct, boolean dna)
 532   {
 533     boolean found = false;
 534     SequenceI[] typer = new SequenceI[1];
 535     if (dataset == null)
 536     {
 537       return false;
 538     }
 539     if (dataset.getSequences() == null)
 540     {
 541       System.err.println("Empty dataset sequence set - NO VECTOR");
 542       return false;
 543     }
 544     List<SequenceI> ds;
 545     synchronized (ds = dataset.getSequences())
 546     {
 547       for (SequenceI nxt : ds)
 548       {
 549         if (nxt != null)
 550         {
 551           if (nxt.getDatasetSequence() != null)
 552           {
 553             System.err
 554                     .println("Implementation warning: getProducts passed a dataset alignment without dataset sequences in it!");
 555           }
 556           if (nxt != sequenceI && nxt != sequenceI.getDatasetSequence())
 557           {
 558             // check if this is the correct sequence type
 559             {
 560               typer[0] = nxt;
 561               boolean isDna = jalview.util.Comparison.isNucleotide(typer);
 562               if ((direct && isDna == dna) || (!direct && isDna != dna))
 563               {
 564                 // skip this sequence because it is same molecule type
 565                 continue;
 566               }
 567             }
 568
 569             // look for direct or indirect references in common
 570             DBRefEntry[] poss = nxt.getDBRefs(), cands = null;
 571             if (direct)
 572             {
 573               cands = jalview.util.DBRefUtils.searchRefs(poss, xrf);
 574             }
 575             else
 576             {
 577               poss = CrossRef.findXDbRefs(dna, poss); //
 578               cands = jalview.util.DBRefUtils.searchRefs(poss, xrf);
 579             }
 580             if (cands != null)
 581             {
 582               if (!rseqs.contains(nxt))
 583               {
 584                 rseqs.add(nxt);
 585                 boolean foundmap = cf != null;
 586                 // don't search if we aren't given a codon map object
 587                 for (int r = 0; foundmap && r < cands.length; r++)
 588                 {
 589                   if (cands[r].hasMap())
 590                   {
 591                     if (cands[r].getMap().getTo() != null
 592                             && cands[r].getMap().getMap().getFromRatio() != cands[r]
 593                                     .getMap().getMap().getToRatio())
 594                     {
 595                       foundmap = true;
 596                       // get sense of map correct for adding to product
 597                       // alignment.
 598                       if (dna)
 599                       {
 600                         // map is from dna seq to a protein product
 601                         cf.addMap(sequenceI, nxt, cands[r].getMap()
 602                                 .getMap());
 603                       }
 604                       else
 605                       {
 606                         // map should be from protein seq to its coding dna
 607                         cf.addMap(nxt, sequenceI, cands[r].getMap()
 608                                 .getMap().getInverse());
 609                       }
 610                     }
 611                   }
 612                 }
 613                 // TODO: add mapping between sequences if necessary
 614                 found = true;
 615               }
 616             }
 617
 618           }
 619         }
 620       }
 621     }
 622     return found;
 623   }
 624
 625   /**
 626    * precalculate different products that can be found for seqs in dataset and
 627    * return them.
 628    *
 629    * @param dna
 630    * @param seqs
 631    * @param dataset
 632    * @param fake
 633    *          - don't actually build lists - just get types
 634    * @return public static Object[] buildXProductsList(boolean dna, SequenceI[]
 635    *         seqs, AlignmentI dataset, boolean fake) { String types[] =
 636    *         jalview.analysis.CrossRef.findSequenceXrefTypes( dna, seqs,
 637    *         dataset); if (types != null) { System.out.println("Xref Types for:
 638    *         "+(dna ? "dna" : "prot")); for (int t = 0; t < types.length; t++) {
 639    *         System.out.println("Type: " + types[t]); SequenceI[] prod =
 640    *         jalview.analysis.CrossRef.findXrefSequences(seqs, dna, types[t]);
 641    *         System.out.println("Found " + ((prod == null) ? "no" : "" +
 642    *         prod.length) + " products"); if (prod!=null) { for (int p=0;
 643    *         p<prod.length; p++) { System.out.println("Prod "+p+":
 644    *         "+prod[p].getDisplayId(true)); } } } } else {
 645    *         System.out.println("Trying getProducts for
 646    *         "+al.getSequenceAt(0).getDisplayId(true));
 647    *         System.out.println("Search DS Xref for: "+(dna ? "dna" : "prot"));
 648    *         // have a bash at finding the products amongst all the retrieved
 649    *         sequences. SequenceI[] prod =
 650    *         jalview.analysis.CrossRef.findXrefSequences(al
 651    *         .getSequencesArray(), dna, null, ds); System.out.println("Found " +
 652    *         ((prod == null) ? "no" : "" + prod.length) + " products"); if
 653    *         (prod!=null) { // select non-equivalent sequences from dataset list
 654    *         for (int p=0; p<prod.length; p++) { System.out.println("Prod "+p+":
 655    *         "+prod[p].getDisplayId(true)); } } } }
 656    */
 657 }