src/jalview/analysis/SequenceIdMatcher.java

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