SequenceIdMatcher.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.DBRefEntry;
  24 import jalview.datamodel.SequenceI;
  25
  26 import java.util.ArrayList;
  27 import java.util.Hashtable;
  28 import java.util.Vector;
  29
  30 /**
  31  * Routines for approximate Sequence Id resolution by name using string
  32  * containment (on word boundaries) rather than equivalence. It also attempts to
  33  * resolve ties where no exact match is available by picking the the id closest
  34  * to the query.
  35  */
  36 public class SequenceIdMatcher
  37 {
  38   private Hashtable names;
  39
  40   public SequenceIdMatcher(SequenceI[] seqs)
  41   {
  42     names = new Hashtable();
  43     for (int i = 0; i < seqs.length; i++)
  44     {
  45       // TODO: deal with ID collisions - SequenceI should be appended to list
  46       // associated with this key.
  47       names.put(new SeqIdName(seqs[i].getDisplayId(true)), seqs[i]);
  48       SequenceI dbseq = seqs[i];
  49       while (dbseq.getDatasetSequence()!=null)
  50       {
  51         dbseq = dbseq.getDatasetSequence();
  52       }
  53       // add in any interesting identifiers
  54       if (dbseq.getDBRef() != null)
  55       {
  56         DBRefEntry dbr[] = dbseq.getDBRef();
  57         SeqIdName sid = null;
  58         for (int r = 0; r < dbr.length; r++)
  59         {
  60           sid = new SeqIdName(dbr[r].getAccessionId());
  61           if (!names.contains(sid))
  62           {
  63             names.put(sid, seqs[i]);
  64           }
  65         }
  66       }
  67     }
  68   }
  69
  70   /**
  71    * returns the closest SequenceI in matches to SeqIdName and returns all the
  72    * matches to the names hash.
  73    *
  74    * @param candName
  75    *          SeqIdName
  76    * @param matches
  77    *          Vector of SequenceI objects
  78    * @return SequenceI closest SequenceI to SeqIdName
  79    */
  80   private SequenceI pickbestMatch(SeqIdName candName, Vector matches)
  81   {
  82     SequenceI[] st = pickbestMatches(candName, matches);
  83     return st == null || st.length == 0 ? null : st[0];
  84   }
  85
  86   /**
  87    * returns the closest SequenceI in matches to SeqIdName and returns all the
  88    * matches to the names hash.
  89    *
  90    * @param candName
  91    *          SeqIdName
  92    * @param matches
  93    *          Vector of SequenceI objects
  94    * @return Object[] { SequenceI closest SequenceI to SeqIdName, SequenceI[]
  95    *         ties }
  96    */
  97   private SequenceI[] pickbestMatches(SeqIdName candName, Vector matches)
  98   {
  99     ArrayList best = new ArrayList();
 100     SequenceI match = null;
 101     if (candName == null || matches == null || matches.size() == 0)
 102     {
 103       return null;
 104     }
 105     match = (SequenceI) matches.elementAt(0);
 106     matches.removeElementAt(0);
 107     best.add(match);
 108     names.put(new SeqIdName(match.getName()), match);
 109     int matchlen = match.getName().length();
 110     int namlen = candName.id.length();
 111     while (matches.size() > 0)
 112     {
 113       // look through for a better one.
 114       SequenceI cand = (SequenceI) matches.elementAt(0);
 115       matches.remove(0);
 116       names.put(new SeqIdName(cand.getName()), cand);
 117       int q, w, candlen = cand.getName().length();
 118       // keep the one with an id 'closer' to the given seqnam string
 119       if ((q = Math.abs(matchlen - namlen)) > (w = Math.abs(candlen
 120               - namlen))
 121               && candlen > matchlen)
 122       {
 123         best.clear();
 124         match = cand;
 125         matchlen = candlen;
 126         best.add(match);
 127       }
 128       if (q == w && candlen == matchlen)
 129       {
 130         // record any ties
 131         best.add(cand);
 132       }
 133     }
 134     if (best.size() == 0)
 135     {
 136       return null;
 137     }
 138     ;
 139     return (SequenceI[]) best.toArray(new SequenceI[0]);
 140   }
 141
 142   /**
 143    * get SequenceI with closest SequenceI.getName() to seq.getName()
 144    *
 145    * @param seq
 146    *          SequenceI
 147    * @return SequenceI
 148    */
 149   public SequenceI findIdMatch(SequenceI seq)
 150   {
 151     SeqIdName nam = new SeqIdName(seq.getName());
 152     return findIdMatch(nam);
 153   }
 154
 155   public SequenceI findIdMatch(String seqnam)
 156   {
 157     SeqIdName nam = new SeqIdName(seqnam);
 158     return findIdMatch(nam);
 159   }
 160
 161   /**
 162    * Find all matches for a given sequence name.
 163    *
 164    * @param seqnam
 165    *          string to query Matcher with.
 166    */
 167   public SequenceI[] findAllIdMatches(String seqnam)
 168   {
 169
 170     SeqIdName nam = new SeqIdName(seqnam);
 171     return findAllIdMatches(nam);
 172   }
 173
 174   /**
 175    * findIdMatch
 176    *
 177    * Return pointers to sequences (or sequence object containers) which have
 178    * same Id as a given set of different sequence objects
 179    *
 180    * @param seqs
 181    *          SequenceI[]
 182    * @return SequenceI[]
 183    */
 184   public SequenceI[] findIdMatch(SequenceI[] seqs)
 185   {
 186     SequenceI[] namedseqs = null;
 187     int i = 0;
 188     SeqIdName nam;
 189
 190     if (seqs.length > 0)
 191     {
 192       namedseqs = new SequenceI[seqs.length];
 193       do
 194       {
 195         nam = new SeqIdName(seqs[i].getName());
 196
 197         if (names.containsKey(nam))
 198         {
 199           namedseqs[i] = findIdMatch(nam);
 200         }
 201         else
 202         {
 203           namedseqs[i] = null;
 204         }
 205       } while (++i < seqs.length);
 206     }
 207
 208     return namedseqs;
 209   }
 210
 211   /**
 212    * core findIdMatch search method
 213    *
 214    * @param nam
 215    *          SeqIdName
 216    * @return SequenceI
 217    */
 218   private SequenceI findIdMatch(
 219           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
 220   {
 221     Vector matches = new Vector();
 222     while (names.containsKey(nam))
 223     {
 224       matches.addElement(names.remove(nam));
 225     }
 226     return pickbestMatch(nam, matches);
 227   }
 228
 229   /**
 230    * core findIdMatch search method for finding all equivalent matches
 231    *
 232    * @param nam
 233    *          SeqIdName
 234    * @return SequenceI[]
 235    */
 236   private SequenceI[] findAllIdMatches(
 237           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
 238   {
 239     Vector matches = new Vector();
 240     while (names.containsKey(nam))
 241     {
 242       matches.addElement(names.remove(nam));
 243     }
 244     SequenceI[] r = pickbestMatches(nam, matches);
 245     return r;
 246   }
 247
 248   private class SeqIdName
 249   {
 250     String id;
 251
 252     SeqIdName(String s)
 253     {
 254       if (s != null)
 255       {
 256         id = new String(s);
 257       }
 258       else
 259       {
 260         id = "";
 261       }
 262     }
 263
 264     @Override
 265     public int hashCode()
 266     {
 267       return ((id.length() >= 4) ? id.substring(0, 4).hashCode() : id
 268               .hashCode());
 269     }
 270
 271     @Override
 272     public boolean equals(Object s)
 273     {
 274       if (s == null)
 275       {
 276         return false;
 277       }
 278       if (s instanceof SeqIdName)
 279       {
 280         return this.equals((SeqIdName) s);
 281       }
 282       else
 283       {
 284         if (s instanceof String)
 285         {
 286           return this.equals((String) s);
 287         }
 288       }
 289
 290       return false;
 291     }
 292
 293     /**
 294      * Characters that define the end of a unique sequence ID at the beginning
 295      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
 296      * arbritrarily extended sequence id's (like portions of an aligned set of
 297      * repeats from one sequence)
 298      */
 299     private String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4)
 300             + "$%^*)}[@',?_";
 301
 302     /**
 303      * matches if one ID properly contains another at a whitespace boundary.
 304      * TODO: (JBPNote) These are not efficient. should use char[] for speed
 305      * todo: (JBPNote) Set separator characters appropriately
 306      *
 307      * @param s
 308      *          SeqIdName
 309      * @return boolean
 310      */
 311     public boolean equals(SeqIdName s)
 312     {
 313       // TODO: JAL-732 patch for cases when name includes a list of IDs, and the
 314       // match contains one ID flanked
 315       if (id.length() > s.id.length())
 316       {
 317         return id.startsWith(s.id) ? (WORD_SEP.indexOf(id.charAt(s.id
 318                 .length())) > -1) : false;
 319       }
 320       else
 321       {
 322         return s.id.startsWith(id) ? (s.id.equals(id) ? true : (WORD_SEP
 323                 .indexOf(s.id.charAt(id.length())) > -1)) : false;
 324       }
 325     }
 326
 327     public boolean equals(String s)
 328     {
 329       if (id.length() > s.length())
 330       {
 331         return id.startsWith(s) ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
 332                 : false;
 333       }
 334       else
 335       {
 336         return s.startsWith(id) ? (s.equals(id) ? true : (WORD_SEP
 337                 .indexOf(s.charAt(id.length())) > -1)) : false;
 338       }
 339     }
 340   }
 341 }