src/jalview/analysis/SequenceIdMatcher.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.6)
   3  * Copyright (C) 2010 J Procter, AM Waterhouse, G Barton, M Clamp, S Searle
   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  */
  18 package jalview.analysis;
  19
  20 import java.util.*;
  21
  22 import jalview.datamodel.*;
  23
  24 /**
  25  * <p>
  26  * Title:
  27  * </p>
  28  * SequenceIdMatcher
  29  * <p>
  30  * Description:
  31  * </p>
  32  * Routine which does approximate Sequence Id resolution by name using string
  33  * containment (on word boundaries) rather than equivalence. It also attempts to
  34  * resolve ties where no exact match is available by picking the the id closest
  35  * to the query.
  36  * <p>
  37  * Copyright: Copyright (c) 2004
  38  * </p>
  39  *
  40  * <p>
  41  * Company: Dundee University
  42  * </p>
  43  *
  44  * @author not attributable
  45  * @version 1.0
  46  */
  47 public class SequenceIdMatcher
  48 {
  49   private Hashtable names;
  50
  51   public SequenceIdMatcher(SequenceI[] seqs)
  52   {
  53     names = new Hashtable();
  54     for (int i = 0; i < seqs.length; i++)
  55     {
  56       names.put(new SeqIdName(seqs[i].getName()), seqs[i]);
  57       // add in any interesting identifiers
  58       if (seqs[i].getDBRef() != null)
  59       {
  60         DBRefEntry dbr[] = seqs[i].getDBRef();
  61         SeqIdName sid = null;
  62         for (int r = 0; r < dbr.length; r++)
  63         {
  64           sid = new SeqIdName(dbr[r].getAccessionId());
  65           if (!names.contains(sid))
  66           {
  67             names.put(sid, seqs[i]);
  68           }
  69         }
  70       }
  71     }
  72   }
  73
  74   /**
  75    * returns the closest SequenceI in matches to SeqIdName and returns all the
  76    * matches to the names hash.
  77    *
  78    * @param candName
  79    *          SeqIdName
  80    * @param matches
  81    *          Vector of SequenceI objects
  82    * @return SequenceI closest SequenceI to SeqIdName
  83    */
  84   private SequenceI pickbestMatch(SeqIdName candName, Vector matches)
  85   {
  86     SequenceI match = null;
  87     if (candName == null || matches == null || matches.size() == 0)
  88     {
  89       return null;
  90     }
  91     match = (SequenceI) matches.elementAt(0);
  92     matches.removeElementAt(0);
  93     names.put(new SeqIdName(match.getName()), match);
  94     int matchlen = match.getName().length();
  95     int namlen = candName.id.length();
  96     while (matches.size() > 0)
  97     {
  98       // look through for a better one.
  99       SequenceI cand = (SequenceI) matches.elementAt(0);
 100       names.put(new SeqIdName(cand.getName()), cand);
 101       int candlen = cand.getName().length();
 102       // keep the one with an id 'closer' to the given seqnam string
 103       if (Math.abs(matchlen - namlen) > Math.abs(candlen - namlen)
 104               && candlen > matchlen)
 105       {
 106         match = cand;
 107         matchlen = candlen;
 108       }
 109     }
 110     return match;
 111   }
 112
 113   /**
 114    * get SequenceI with closest SequenceI.getName() to seq.getName()
 115    *
 116    * @param seq
 117    *          SequenceI
 118    * @return SequenceI
 119    */
 120   SequenceI findIdMatch(SequenceI seq)
 121   {
 122     SeqIdName nam = new SeqIdName(seq.getName());
 123     return findIdMatch(nam);
 124   }
 125
 126   SequenceI findIdMatch(String seqnam)
 127   {
 128     SeqIdName nam = new SeqIdName(seqnam);
 129     return findIdMatch(nam);
 130   }
 131
 132   /**
 133    * findIdMatch
 134    *
 135    * Return pointers to sequences (or sequence object containers) which have
 136    * same Id as a given set of different sequence objects
 137    *
 138    * @param seqs
 139    *          SequenceI[]
 140    * @return SequenceI[]
 141    */
 142   SequenceI[] findIdMatch(SequenceI[] seqs)
 143   {
 144     SequenceI[] namedseqs = null;
 145     int i = 0;
 146     SeqIdName nam;
 147
 148     if (seqs.length > 0)
 149     {
 150       namedseqs = new SequenceI[seqs.length];
 151       do
 152       {
 153         nam = new SeqIdName(seqs[i].getName());
 154
 155         if (names.containsKey(nam))
 156         {
 157           namedseqs[i] = findIdMatch(nam);
 158         }
 159         else
 160         {
 161           namedseqs[i] = null;
 162         }
 163       } while (++i < seqs.length);
 164     }
 165
 166     return namedseqs;
 167   }
 168
 169   /**
 170    * core findIdMatch search method
 171    *
 172    * @param nam
 173    *          SeqIdName
 174    * @return SequenceI
 175    */
 176   private SequenceI findIdMatch(
 177           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
 178   {
 179     Vector matches = new Vector();
 180     while (names.containsKey(nam))
 181     {
 182       matches.addElement(names.remove(nam));
 183     }
 184     return pickbestMatch(nam, matches);
 185   }
 186
 187   private class SeqIdName
 188   {
 189     String id;
 190
 191     SeqIdName(String s)
 192     {
 193       if (s != null)
 194       {
 195         id = new String(s);
 196       }
 197       else
 198       {
 199         id = "";
 200       }
 201     }
 202
 203     public int hashCode()
 204     {
 205       return ((id.length() >= 4) ? id.substring(0, 4).hashCode() : id
 206               .hashCode());
 207     }
 208
 209     public boolean equals(Object s)
 210     {
 211       if (s instanceof SeqIdName)
 212       {
 213         return this.equals((SeqIdName) s);
 214       }
 215       else
 216       {
 217         if (s instanceof String)
 218         {
 219           return this.equals((String) s);
 220         }
 221       }
 222
 223       return false;
 224     }
 225
 226     /**
 227      * Characters that define the end of a unique sequence ID at the beginning
 228      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
 229      * arbritrarily extended sequence id's (like portions of an aligned set of
 230      * repeats from one sequence)
 231      */
 232     private String WORD_SEP = "~. |#\\/<>!\"£$%^*)}[@',?_";
 233
 234     /**
 235      * matches if one ID properly contains another at a whitespace boundary.
 236      * TODO: (JBPNote) These are not efficient. should use char[] for speed
 237      * todo: (JBPNote) Set separator characters appropriately
 238      *
 239      * @param s
 240      *          SeqIdName
 241      * @return boolean
 242      */
 243     public boolean equals(SeqIdName s)
 244     {
 245       if (id.length() > s.id.length())
 246       {
 247         return id.startsWith(s.id) ? (WORD_SEP.indexOf(id.charAt(s.id
 248                 .length())) > -1) : false;
 249       }
 250       else
 251       {
 252         return s.id.startsWith(id) ? (s.id.equals(id) ? true : (WORD_SEP
 253                 .indexOf(s.id.charAt(id.length())) > -1)) : false;
 254       }
 255     }
 256
 257     public boolean equals(String s)
 258     {
 259       if (id.length() > s.length())
 260       {
 261         return id.startsWith(s) ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
 262                 : false;
 263       }
 264       else
 265       {
 266         return s.startsWith(id) ? (s.equals(id) ? true : (WORD_SEP
 267                 .indexOf(s.charAt(id.length())) > -1)) : false;
 268       }
 269     }
 270   }
 271 }