src/jalview/analysis/SequenceIdMatcher.java

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