src/jalview/analysis/SequenceIdMatcher.java

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