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       // add in any interesting identifiers
  59       if (seqs[i].getDBRef()!=null)
  60       {
  61         DBRefEntry dbr[] = seqs[i].getDBRef();
  62         SeqIdName sid=null;
  63         for (int r=0;r<dbr.length;r++)
  64         {
  65           sid = new SeqIdName(dbr[r].getAccessionId());
  66           if (!names.contains(sid))
  67           {
  68             names.put(sid, seqs[i]);
  69           }
  70         }
  71       }
  72     }
  73   }
  74
  75   /**
  76    * returns the closest SequenceI in matches to SeqIdName and returns all the
  77    * matches to the names hash.
  78    *
  79    * @param candName
  80    *                SeqIdName
  81    * @param matches
  82    *                Vector of SequenceI objects
  83    * @return SequenceI closest SequenceI to SeqIdName
  84    */
  85   private SequenceI pickbestMatch(SeqIdName candName, Vector matches)
  86   {
  87     SequenceI match = null;
  88     if (candName == null || matches == null || matches.size() == 0)
  89     {
  90       return null;
  91     }
  92     match = (SequenceI) matches.elementAt(0);
  93     matches.removeElementAt(0);
  94     names.put(new SeqIdName(match.getName()), match);
  95     int matchlen = match.getName().length();
  96     int namlen = candName.id.length();
  97     while (matches.size() > 0)
  98     {
  99       // look through for a better one.
 100       SequenceI cand = (SequenceI) matches.elementAt(0);
 101       names.put(new SeqIdName(cand.getName()), cand);
 102       int candlen = cand.getName().length();
 103       // keep the one with an id 'closer' to the given seqnam string
 104       if (Math.abs(matchlen - namlen) > Math.abs(candlen - namlen)
 105               && candlen > matchlen)
 106       {
 107         match = cand;
 108         matchlen = candlen;
 109       }
 110     }
 111     return match;
 112   }
 113
 114   /**
 115    * get SequenceI with closest SequenceI.getName() to seq.getName()
 116    *
 117    * @param seq
 118    *                SequenceI
 119    * @return SequenceI
 120    */
 121   SequenceI findIdMatch(SequenceI seq)
 122   {
 123     SeqIdName nam = new SeqIdName(seq.getName());
 124     return findIdMatch(nam);
 125   }
 126
 127   SequenceI findIdMatch(String seqnam)
 128   {
 129     SeqIdName nam = new SeqIdName(seqnam);
 130     return findIdMatch(nam);
 131   }
 132
 133   /**
 134    * findIdMatch
 135    *
 136    * Return pointers to sequences (or sequence object containers) which have
 137    * same Id as a given set of different sequence objects
 138    *
 139    * @param seqs
 140    *                SequenceI[]
 141    * @return SequenceI[]
 142    */
 143   SequenceI[] findIdMatch(SequenceI[] seqs)
 144   {
 145     SequenceI[] namedseqs = null;
 146     int i = 0;
 147     SeqIdName nam;
 148
 149     if (seqs.length > 0)
 150     {
 151       namedseqs = new SequenceI[seqs.length];
 152       do
 153       {
 154         nam = new SeqIdName(seqs[i].getName());
 155
 156         if (names.containsKey(nam))
 157         {
 158           namedseqs[i] = findIdMatch(nam);
 159         }
 160         else
 161         {
 162           namedseqs[i] = null;
 163         }
 164       } while (++i < seqs.length);
 165     }
 166
 167     return namedseqs;
 168   }
 169
 170   /**
 171    * core findIdMatch search method
 172    *
 173    * @param nam
 174    *                SeqIdName
 175    * @return SequenceI
 176    */
 177   private SequenceI findIdMatch(
 178           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
 179   {
 180     Vector matches = new Vector();
 181     while (names.containsKey(nam))
 182     {
 183       matches.addElement(names.remove(nam));
 184     }
 185     return pickbestMatch(nam, matches);
 186   }
 187
 188   private class SeqIdName
 189   {
 190     String id;
 191
 192     SeqIdName(String s)
 193     {
 194       if (s != null)
 195       {
 196         id = new String(s);
 197       }
 198       else
 199       {
 200         id = "";
 201       }
 202     }
 203
 204     public int hashCode()
 205     {
 206       return ((id.length() >= 4) ? id.substring(0, 4).hashCode() : id
 207               .hashCode());
 208     }
 209
 210     public boolean equals(Object s)
 211     {
 212       if (s instanceof SeqIdName)
 213       {
 214         return this.equals((SeqIdName) s);
 215       }
 216       else
 217       {
 218         if (s instanceof String)
 219         {
 220           return this.equals((String) s);
 221         }
 222       }
 223
 224       return false;
 225     }
 226
 227     /**
 228      * Characters that define the end of a unique sequence ID at the beginning
 229      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
 230      * arbritrarily extended sequence id's (like portions of an aligned set of
 231      * repeats from one sequence)
 232      */
 233     private String WORD_SEP = "~. |#\\/<>!\"£$%^*)}[@',?_";
 234
 235     /**
 236      * matches if one ID properly contains another at a whitespace boundary.
 237      * TODO: (JBPNote) These are not efficient. should use char[] for speed
 238      * todo: (JBPNote) Set separator characters appropriately
 239      *
 240      * @param s
 241      *                SeqIdName
 242      * @return boolean
 243      */
 244     public boolean equals(SeqIdName s)
 245     {
 246       if (id.length() > s.id.length())
 247       {
 248         return id.startsWith(s.id) ? (WORD_SEP.indexOf(id.charAt(s.id
 249                 .length())) > -1) : false;
 250       }
 251       else
 252       {
 253         return s.id.startsWith(id) ? (s.id.equals(id) ? true : (WORD_SEP
 254                 .indexOf(s.id.charAt(id.length())) > -1)) : false;
 255       }
 256     }
 257
 258     public boolean equals(String s)
 259     {
 260       if (id.length() > s.length())
 261       {
 262         return id.startsWith(s) ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
 263                 : false;
 264       }
 265       else
 266       {
 267         return s.startsWith(id) ? (s.equals(id) ? true : (WORD_SEP
 268                 .indexOf(s.charAt(id.length())) > -1)) : false;
 269       }
 270     }
 271   }
 272 }