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