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