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