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