src/jalview/analysis/SequenceIdMatcher.java

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