src/jalview/analysis/SequenceIdMatcher.java

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