src/jalview/analysis/SequenceIdMatcher.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.4)
   3  * Copyright (C) 2008 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19 package jalview.analysis;
  20
  21 import java.util.*;
  22
  23 import jalview.datamodel.*;
  24
  25 /**
  26  * <p>
  27  * Title:
  28  * </p>
  29  * SequenceIdMatcher
  30  * <p>
  31  * Description:
  32  * </p>
  33  * Routine which does 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  * <p>
  38  * Copyright: Copyright (c) 2004
  39  * </p>
  40  *
  41  * <p>
  42  * Company: Dundee University
  43  * </p>
  44  *
  45  * @author not attributable
  46  * @version 1.0
  47  */
  48 public class SequenceIdMatcher
  49 {
  50   private Hashtable names;
  51
  52   public SequenceIdMatcher(SequenceI[] seqs)
  53   {
  54     names = new Hashtable();
  55     for (int i = 0; i < seqs.length; i++)
  56     {
  57       names.put(new SeqIdName(seqs[i].getName()), seqs[i]);
  58     }
  59   }
  60
  61   /**
  62    * returns the closest SequenceI in matches to SeqIdName and returns all the
  63    * matches to the names hash.
  64    *
  65    * @param candName
  66    *                SeqIdName
  67    * @param matches
  68    *                Vector of SequenceI objects
  69    * @return SequenceI closest SequenceI to SeqIdName
  70    */
  71   private SequenceI pickbestMatch(SeqIdName candName, Vector matches)
  72   {
  73     SequenceI match = null;
  74     if (candName == null || matches == null || matches.size() == 0)
  75     {
  76       return null;
  77     }
  78     match = (SequenceI) matches.elementAt(0);
  79     matches.removeElementAt(0);
  80     names.put(new SeqIdName(match.getName()), match);
  81     int matchlen = match.getName().length();
  82     int namlen = candName.id.length();
  83     while (matches.size() > 0)
  84     {
  85       // look through for a better one.
  86       SequenceI cand = (SequenceI) matches.elementAt(0);
  87       names.put(new SeqIdName(cand.getName()), cand);
  88       int candlen = cand.getName().length();
  89       // keep the one with an id 'closer' to the given seqnam string
  90       if (Math.abs(matchlen - namlen) > Math.abs(candlen - namlen)
  91               && candlen > matchlen)
  92       {
  93         match = cand;
  94         matchlen = candlen;
  95       }
  96     }
  97     return match;
  98   }
  99
 100   /**
 101    * get SequenceI with closest SequenceI.getName() to seq.getName()
 102    *
 103    * @param seq
 104    *                SequenceI
 105    * @return SequenceI
 106    */
 107   SequenceI findIdMatch(SequenceI seq)
 108   {
 109     SeqIdName nam = new SeqIdName(seq.getName());
 110     return findIdMatch(nam);
 111   }
 112
 113   SequenceI findIdMatch(String seqnam)
 114   {
 115     SeqIdName nam = new SeqIdName(seqnam);
 116     return findIdMatch(nam);
 117   }
 118
 119   /**
 120    * findIdMatch
 121    *
 122    * Return pointers to sequences (or sequence object containers) which have
 123    * same Id as a given set of different sequence objects
 124    *
 125    * @param seqs
 126    *                SequenceI[]
 127    * @return SequenceI[]
 128    */
 129   SequenceI[] findIdMatch(SequenceI[] seqs)
 130   {
 131     SequenceI[] namedseqs = null;
 132     int i = 0;
 133     SeqIdName nam;
 134
 135     if (seqs.length > 0)
 136     {
 137       namedseqs = new SequenceI[seqs.length];
 138       do
 139       {
 140         nam = new SeqIdName(seqs[i].getName());
 141
 142         if (names.containsKey(nam))
 143         {
 144           namedseqs[i] = findIdMatch(nam);
 145         }
 146         else
 147         {
 148           namedseqs[i] = null;
 149         }
 150       } while (++i < seqs.length);
 151     }
 152
 153     return namedseqs;
 154   }
 155
 156   /**
 157    * core findIdMatch search method
 158    *
 159    * @param nam
 160    *                SeqIdName
 161    * @return SequenceI
 162    */
 163   private SequenceI findIdMatch(
 164           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
 165   {
 166     Vector matches = new Vector();
 167     while (names.containsKey(nam))
 168     {
 169       matches.addElement(names.remove(nam));
 170     }
 171     return pickbestMatch(nam, matches);
 172   }
 173
 174   private class SeqIdName
 175   {
 176     String id;
 177
 178     SeqIdName(String s)
 179     {
 180       if (s != null)
 181       {
 182         id = new String(s);
 183       }
 184       else
 185       {
 186         id = "";
 187       }
 188     }
 189
 190     public int hashCode()
 191     {
 192       return ((id.length() >= 4) ? id.substring(0, 4).hashCode() : id
 193               .hashCode());
 194     }
 195
 196     public boolean equals(Object s)
 197     {
 198       if (s instanceof SeqIdName)
 199       {
 200         return this.equals((SeqIdName) s);
 201       }
 202       else
 203       {
 204         if (s instanceof String)
 205         {
 206           return this.equals((String) s);
 207         }
 208       }
 209
 210       return false;
 211     }
 212
 213     /**
 214      * Characters that define the end of a unique sequence ID at the beginning
 215      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
 216      * arbritrarily extended sequence id's (like portions of an aligned set of
 217      * repeats from one sequence)
 218      */
 219     private String WORD_SEP = "~. |#\\/<>!\"£$%^*)}[@',?_";
 220
 221     /**
 222      * matches if one ID properly contains another at a whitespace boundary.
 223      * TODO: (JBPNote) These are not efficient. should use char[] for speed
 224      * todo: (JBPNote) Set separator characters appropriately
 225      *
 226      * @param s
 227      *                SeqIdName
 228      * @return boolean
 229      */
 230     public boolean equals(SeqIdName s)
 231     {
 232       if (id.length() > s.id.length())
 233       {
 234         return id.startsWith(s.id) ? (WORD_SEP.indexOf(id.charAt(s.id
 235                 .length())) > -1) : false;
 236       }
 237       else
 238       {
 239         return s.id.startsWith(id) ? (s.id.equals(id) ? true : (WORD_SEP
 240                 .indexOf(s.id.charAt(id.length())) > -1)) : false;
 241       }
 242     }
 243
 244     public boolean equals(String s)
 245     {
 246       if (id.length() > s.length())
 247       {
 248         return id.startsWith(s) ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
 249                 : false;
 250       }
 251       else
 252       {
 253         return s.startsWith(id) ? (s.equals(id) ? true : (WORD_SEP
 254                 .indexOf(s.charAt(id.length())) > -1)) : false;
 255       }
 256     }
 257   }
 258 }