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.HashSet;
  30 import java.util.List;
  31 import java.util.Set;
  32
  33 /**
  34  * Routines for approximate Sequence Id resolution by name using string
  35  * containment (on word boundaries) rather than equivalence. It also attempts to
  36  * resolve ties where no exact match is available by picking the the id closest
  37  * to the query.
  38  */
  39 public class SequenceIdMatcher
  40 {
  41   /**
  42    * weak hash for each sequence
  43    */
  44   private HashMap<SeqIdName, Set<SequenceI>> names;
  45
  46   // /**
  47   // * cache of values removed for each query string.
  48   // */
  49   // private HashMap<String, List<SequenceI>> resolved;
  50
  51   /**
  52    * do we index sequences on all 'words' in ID string ?
  53    */
  54   private boolean wordBased = false;
  55
  56   /**
  57    * Characters that define the end of a unique sequence ID at the beginning of
  58    * an arbitrary ID string JBPNote: This is a heuristic that will fail for
  59    * arbritrarily extended sequence id's (like portions of an aligned set of
  60    * repeats from one sequence)
  61    */
  62   static String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4)
  63           + "$%^*)}[@',?_";
  64
  65   /**
  66    * @return true if matcher is word-based (ie string key matches one of the
  67    *         words within the body of one or more sequence IDs)
  68    */
  69   public boolean isWordBased()
  70   {
  71     return wordBased;
  72   }
  73
  74   /**
  75    * Construct a standard (non-word based) matcher. To configure word based
  76    * matching, use the fully qualified constructor
  77    *
  78    * @param seqs
  79    */
  80   public SequenceIdMatcher(List<SequenceI> seqs)
  81   {
  82     this(false, seqs);
  83   }
  84
  85   /**
  86    * construct a new matcher for a set of sequences, configured as required.
  87    * Note: enabling word based matching
  88    *
  89    * @param wordBasedMatch
  90    *          - when true, "myseq" matches "X|myseq" and "myseq"
  91    * @param seqs
  92    */
  93   public SequenceIdMatcher(boolean wordBasedMatch, List<SequenceI> seqs)
  94   {
  95     wordBased = wordBasedMatch;
  96     names = new HashMap<SeqIdName, Set<SequenceI>>();
  97     addAll(seqs);
  98   }
  99
 100   /**
 101    * add more sequences to this matcher - also used by the constructor
 102    *
 103    * @param seqs
 104    */
 105   public void addAll(List<SequenceI> seqs)
 106   {
 107     for (SequenceI seq : seqs)
 108     {
 109       addSeq(seq);
 110     }
 111   }
 112
 113   private void addSeqIdName(SeqIdName idname, SequenceI seq)
 114   {
 115     Set<SequenceI> seqset = names.get(idname);
 116     if (seqset == null)
 117     {
 118       seqset = new HashSet<SequenceI>();
 119       names.put(idname, seqset);
 120     }
 121     seqset.add(seq);
 122   }
 123
 124   public void addSeq(SequenceI seq)
 125   {
 126     // TODO: deal with ID collisions - SequenceI should be appended to list
 127     // associated with this key.
 128     addSeqIdName(new SeqIdName(seq.getDisplayId(true)), seq);
 129     if (wordBased)
 130     {
 131       for (SeqIdName key : getWordsFor(seq))
 132       {
 133         addSeqIdName(key, seq);
 134       }
 135     }
 136     SequenceI dbseq = seq;
 137     // TODO add test for database xref resolution
 138     while (dbseq.getDatasetSequence() != null)
 139     {
 140       dbseq = dbseq.getDatasetSequence();
 141     }
 142     // add in any interesting identifiers
 143     if (dbseq.getDBRefs() != null)
 144     {
 145       DBRefEntry dbr[] = dbseq.getDBRefs();
 146       SeqIdName sid = null;
 147       for (int r = 0; r < dbr.length; r++)
 148       {
 149         sid = new SeqIdName(dbr[r].getAccessionId());
 150         if (!names.containsKey(sid))
 151         {
 152           addSeqIdName(sid, seq);
 153         }
 154       }
 155     }
 156   }
 157
 158   /**
 159    * generate word based keys for the given sequence
 160    *
 161    * @param seq
 162    * @return list of split keys
 163    */
 164   public static List<SeqIdName> getWordsFor(SequenceI seq)
 165   {
 166     ArrayList<SeqIdName> keys = new ArrayList<SeqIdName>();
 167     String name = seq.getName(), limits = "/" + seq.getStart() + "-"
 168             + seq.getEnd();
 169     int namel = name.length();
 170     char[] sep = new char[WORD_SEP.length()];
 171     // find only the separators present in the ID.
 172     for (int i = 0; i < sep.length; i++)
 173     {
 174       sep[i] = WORD_SEP.charAt(i);
 175       if (seq.getName().indexOf("" + sep[i]) == -1)
 176       {
 177         sep[i] = 0;
 178       }
 179     }
 180     ;
 181     // make words
 182     for (int i = 0; i < sep.length; i++)
 183     {
 184       if (sep[i] > 0)
 185       {
 186         int p = 0, m = -1;
 187         while ((m = name.indexOf(sep[i], p)) > p)
 188         {
 189
 190           if (m > 0 && m - p > 5)
 191           {
 192             // split to end of word m with this delimiter
 193             keys.add(new SeqIdName(name.substring(p, m - 1) + limits));
 194           }
 195           if (namel - m > 5)
 196           {
 197             // index word after this delimiter m
 198             keys.add(new SeqIdName(name.substring(m + 1) + limits));
 199           }
 200           p = m + 1;
 201         }
 202         if (namel - p > 4)
 203         {
 204           // index word after this delimiter m
 205           keys.add(new SeqIdName(name.substring(p) + limits));
 206         }
 207       }
 208     }
 209     return keys;
 210   }
 211
 212   /**
 213    * convenience method to make a matcher from concrete array Note: in order to
 214    * support word based matching, use the fully qualified constructor
 215    *
 216    * @param sequences
 217    */
 218   public SequenceIdMatcher(SequenceI[] sequences)
 219   {
 220     this(Arrays.asList(sequences));
 221   }
 222
 223   /**
 224    * returns the closest SequenceI in matches to SeqIdName and returns all the
 225    * matches to the names hash.
 226    *
 227    * @param candName
 228    *          SeqIdName
 229    * @param matches
 230    *          List of SequenceI objects
 231    * @return SequenceI closest SequenceI to SeqIdName
 232    */
 233   private SequenceI pickbestMatch(SeqIdName candName,
 234           List<SequenceI> matches)
 235   {
 236     List<SequenceI> st = pickbestMatches(candName, matches);
 237     return st == null || st.size() == 0 ? null : st.get(0);
 238   }
 239
 240   /**
 241    * returns the closest SequenceI in matches to SeqIdName and returns all the
 242    * matches to the names hash.
 243    *
 244    * @param candName
 245    *          SeqIdName
 246    * @param matches
 247    *          Vector of SequenceI objects
 248    * @return Object[] { SequenceI closest SequenceI to SeqIdName, SequenceI[]
 249    *         ties }
 250    */
 251   private List<SequenceI> pickbestMatches(SeqIdName candName,
 252           List<SequenceI> matches)
 253   {
 254     ArrayList<SequenceI> best = new ArrayList<SequenceI>();
 255     if (candName == null || matches == null || matches.size() == 0)
 256     {
 257       return null;
 258     }
 259     SequenceI match = matches.remove(0);
 260     best.add(match);
 261     addSeq(match);
 262     int matchlen = match.getName().length();
 263     int namlen = candName.id.length();
 264     while (matches.size() > 0)
 265     {
 266       // look through for a better one.
 267       SequenceI cand = matches.remove(0);
 268       addSeq(cand);
 269       int q, w, candlen = cand.getName().length();
 270       // keep the one with an id 'closer' to the given seqnam string
 271       boolean is_closer = ((q = Math.abs(matchlen - namlen)) > (w = Math
 272               .abs(candlen - namlen)) && candlen > matchlen);
 273       // if not closer, then check if current best is actually identical in case
 274       // as
 275       // well
 276       if (is_closer
 277               || (candName.equalsCase(cand.getName()) && !candName
 278                       .equalsCase(best.get(0).getName())))
 279       {
 280         best.clear();
 281         match = cand;
 282         matchlen = candlen;
 283         best.add(match);
 284       }
 285       else
 286       {
 287         if (q == w && candlen == matchlen)
 288         {
 289           // equivalently good, and matches with case as well. so
 290           // record any ties
 291           best.add(cand);
 292         }
 293       }
 294     }
 295     if (best.size() == 0)
 296     {
 297       return null;
 298     }
 299     ;
 300     return best;
 301   }
 302
 303   /**
 304    * get SequenceI with closest SequenceI.getName() to seq.getName()
 305    *
 306    * @param seq
 307    *          SequenceI
 308    * @return SequenceI
 309    */
 310   public SequenceI findIdMatch(SequenceI seq)
 311   {
 312     SeqIdName nam = new SeqIdName(seq.getName());
 313     return findIdMatch(nam);
 314   }
 315
 316   public SequenceI findIdMatch(String seqnam)
 317   {
 318     SeqIdName nam = new SeqIdName(seqnam);
 319     return findIdMatch(nam);
 320   }
 321
 322   /**
 323    * Find all matches for a given sequence name.
 324    *
 325    * @param seqnam
 326    *          string to query Matcher with.
 327    * @return a new array or (possibly) null
 328    */
 329   public SequenceI[] findAllIdMatches(String seqnam)
 330   {
 331
 332     SeqIdName nam = new SeqIdName(seqnam);
 333     List<SequenceI> m = findAllIdMatches(nam);
 334     if (m != null)
 335     {
 336       return m.toArray(new SequenceI[m.size()]);
 337     }
 338     return null;
 339   }
 340
 341   /**
 342    * findIdMatch
 343    *
 344    * Return pointers to sequences (or sequence object containers) which have
 345    * same Id as a given set of different sequence objects
 346    *
 347    * @param seqs
 348    *          SequenceI[]
 349    * @return SequenceI[]
 350    */
 351   public SequenceI[] findIdMatch(SequenceI[] seqs)
 352   {
 353     SequenceI[] namedseqs = null;
 354     int i = 0;
 355     SeqIdName nam;
 356
 357     if (seqs.length > 0)
 358     {
 359       namedseqs = new SequenceI[seqs.length];
 360       do
 361       {
 362         nam = new SeqIdName(seqs[i].getName());
 363
 364         if (names.containsKey(nam))
 365         {
 366           namedseqs[i] = findIdMatch(nam);
 367         }
 368         else
 369         {
 370           namedseqs[i] = null;
 371         }
 372       } while (++i < seqs.length);
 373     }
 374
 375     return namedseqs;
 376   }
 377
 378   /**
 379    * core findIdMatch search method
 380    *
 381    * @param nam
 382    *          SeqIdName
 383    * @return SequenceI
 384    */
 385   private SequenceI findIdMatch(
 386           jalview.analysis.SeqIdName nam)
 387   {
 388     ArrayList<SequenceI> matches = new ArrayList<SequenceI>();
 389     while (names.containsKey(nam))
 390     {
 391       matches.addAll(names.remove(nam));
 392     }
 393     return pickbestMatch(nam, matches);
 394   }
 395
 396   /**
 397    * core findIdMatch search method for finding all equivalent matches
 398    *
 399    * @param nam
 400    *          SeqIdName
 401    * @return SequenceI[]
 402    */
 403   private List<SequenceI> findAllIdMatches(
 404           jalview.analysis.SeqIdName nam)
 405   {
 406     ArrayList<SequenceI> matches = new ArrayList<SequenceI>();
 407     while (names.containsKey(nam))
 408     {
 409       matches.addAll(names.remove(nam));
 410     }
 411     List<SequenceI> r = pickbestMatches(nam, matches);
 412     return r;
 413   }
 414 }