src/jalview/analysis/SequenceIdMatcher.java

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