e6a48531f322ac5e80ffe03e1d18789544700216
[jalview.git] / SequenceIdMatcher.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
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
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.analysis;
22
23 import jalview.datamodel.DBRefEntry;
24 import jalview.datamodel.SequenceI;
25
26 import java.util.ArrayList;
27 import java.util.Hashtable;
28 import java.util.Vector;
29
30 /**
31  * Routines for approximate Sequence Id resolution by name using string
32  * containment (on word boundaries) rather than equivalence. It also attempts to
33  * resolve ties where no exact match is available by picking the the id closest
34  * to the query.
35  */
36 public class SequenceIdMatcher
37 {
38   private Hashtable names;
39
40   public SequenceIdMatcher(SequenceI[] seqs)
41   {
42     names = new Hashtable();
43     for (int i = 0; i < seqs.length; i++)
44     {
45       // TODO: deal with ID collisions - SequenceI should be appended to list
46       // associated with this key.
47       names.put(new SeqIdName(seqs[i].getDisplayId(true)), seqs[i]);
48       SequenceI dbseq = seqs[i];
49       while (dbseq.getDatasetSequence()!=null)
50       {
51         dbseq = dbseq.getDatasetSequence();
52       }
53       // add in any interesting identifiers
54       if (dbseq.getDBRef() != null)
55       {
56         DBRefEntry dbr[] = dbseq.getDBRef();
57         SeqIdName sid = null;
58         for (int r = 0; r < dbr.length; r++)
59         {
60           sid = new SeqIdName(dbr[r].getAccessionId());
61           if (!names.contains(sid))
62           {
63             names.put(sid, seqs[i]);
64           }
65         }
66       }
67     }
68   }
69
70   /**
71    * returns the closest SequenceI in matches to SeqIdName and returns all the
72    * matches to the names hash.
73    * 
74    * @param candName
75    *          SeqIdName
76    * @param matches
77    *          Vector of SequenceI objects
78    * @return SequenceI closest SequenceI to SeqIdName
79    */
80   private SequenceI pickbestMatch(SeqIdName candName, Vector matches)
81   {
82     SequenceI[] st = pickbestMatches(candName, matches);
83     return st == null || st.length == 0 ? null : st[0];
84   }
85
86   /**
87    * returns the closest SequenceI in matches to SeqIdName and returns all the
88    * matches to the names hash.
89    * 
90    * @param candName
91    *          SeqIdName
92    * @param matches
93    *          Vector of SequenceI objects
94    * @return Object[] { SequenceI closest SequenceI to SeqIdName, SequenceI[]
95    *         ties }
96    */
97   private SequenceI[] pickbestMatches(SeqIdName candName, Vector matches)
98   {
99     ArrayList best = new ArrayList();
100     SequenceI match = null;
101     if (candName == null || matches == null || matches.size() == 0)
102     {
103       return null;
104     }
105     match = (SequenceI) matches.elementAt(0);
106     matches.removeElementAt(0);
107     best.add(match);
108     names.put(new SeqIdName(match.getName()), match);
109     int matchlen = match.getName().length();
110     int namlen = candName.id.length();
111     while (matches.size() > 0)
112     {
113       // look through for a better one.
114       SequenceI cand = (SequenceI) matches.elementAt(0);
115       matches.remove(0);
116       names.put(new SeqIdName(cand.getName()), cand);
117       int q, w, candlen = cand.getName().length();
118       // keep the one with an id 'closer' to the given seqnam string
119       if ((q = Math.abs(matchlen - namlen)) > (w = Math.abs(candlen
120               - namlen))
121               && candlen > matchlen)
122       {
123         best.clear();
124         match = cand;
125         matchlen = candlen;
126         best.add(match);
127       }
128       if (q == w && candlen == matchlen)
129       {
130         // record any ties
131         best.add(cand);
132       }
133     }
134     if (best.size() == 0)
135     {
136       return null;
137     }
138     ;
139     return (SequenceI[]) best.toArray(new SequenceI[0]);
140   }
141
142   /**
143    * get SequenceI with closest SequenceI.getName() to seq.getName()
144    * 
145    * @param seq
146    *          SequenceI
147    * @return SequenceI
148    */
149   public SequenceI findIdMatch(SequenceI seq)
150   {
151     SeqIdName nam = new SeqIdName(seq.getName());
152     return findIdMatch(nam);
153   }
154
155   public SequenceI findIdMatch(String seqnam)
156   {
157     SeqIdName nam = new SeqIdName(seqnam);
158     return findIdMatch(nam);
159   }
160
161   /**
162    * Find all matches for a given sequence name.
163    * 
164    * @param seqnam
165    *          string to query Matcher with.
166    */
167   public SequenceI[] findAllIdMatches(String seqnam)
168   {
169
170     SeqIdName nam = new SeqIdName(seqnam);
171     return findAllIdMatches(nam);
172   }
173
174   /**
175    * findIdMatch
176    * 
177    * Return pointers to sequences (or sequence object containers) which have
178    * same Id as a given set of different sequence objects
179    * 
180    * @param seqs
181    *          SequenceI[]
182    * @return SequenceI[]
183    */
184   public SequenceI[] findIdMatch(SequenceI[] seqs)
185   {
186     SequenceI[] namedseqs = null;
187     int i = 0;
188     SeqIdName nam;
189
190     if (seqs.length > 0)
191     {
192       namedseqs = new SequenceI[seqs.length];
193       do
194       {
195         nam = new SeqIdName(seqs[i].getName());
196
197         if (names.containsKey(nam))
198         {
199           namedseqs[i] = findIdMatch(nam);
200         }
201         else
202         {
203           namedseqs[i] = null;
204         }
205       } while (++i < seqs.length);
206     }
207
208     return namedseqs;
209   }
210
211   /**
212    * core findIdMatch search method
213    * 
214    * @param nam
215    *          SeqIdName
216    * @return SequenceI
217    */
218   private SequenceI findIdMatch(
219           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
220   {
221     Vector matches = new Vector();
222     while (names.containsKey(nam))
223     {
224       matches.addElement(names.remove(nam));
225     }
226     return pickbestMatch(nam, matches);
227   }
228
229   /**
230    * core findIdMatch search method for finding all equivalent matches
231    * 
232    * @param nam
233    *          SeqIdName
234    * @return SequenceI[]
235    */
236   private SequenceI[] findAllIdMatches(
237           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
238   {
239     Vector matches = new Vector();
240     while (names.containsKey(nam))
241     {
242       matches.addElement(names.remove(nam));
243     }
244     SequenceI[] r = pickbestMatches(nam, matches);
245     return r;
246   }
247
248   private class SeqIdName
249   {
250     String id;
251
252     SeqIdName(String s)
253     {
254       if (s != null)
255       {
256         id = new String(s);
257       }
258       else
259       {
260         id = "";
261       }
262     }
263
264     @Override
265     public int hashCode()
266     {
267       return ((id.length() >= 4) ? id.substring(0, 4).hashCode() : id
268               .hashCode());
269     }
270
271     @Override
272     public boolean equals(Object s)
273     {
274       if (s == null)
275       {
276         return false;
277       }
278       if (s instanceof SeqIdName)
279       {
280         return this.equals((SeqIdName) s);
281       }
282       else
283       {
284         if (s instanceof String)
285         {
286           return this.equals((String) s);
287         }
288       }
289
290       return false;
291     }
292
293     /**
294      * Characters that define the end of a unique sequence ID at the beginning
295      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
296      * arbritrarily extended sequence id's (like portions of an aligned set of
297      * repeats from one sequence)
298      */
299     private String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4)
300             + "$%^*)}[@',?_";
301
302     /**
303      * matches if one ID properly contains another at a whitespace boundary.
304      * TODO: (JBPNote) These are not efficient. should use char[] for speed
305      * todo: (JBPNote) Set separator characters appropriately
306      * 
307      * @param s
308      *          SeqIdName
309      * @return boolean
310      */
311     public boolean equals(SeqIdName s)
312     {
313       // TODO: JAL-732 patch for cases when name includes a list of IDs, and the
314       // match contains one ID flanked
315       if (id.length() > s.id.length())
316       {
317         return id.startsWith(s.id) ? (WORD_SEP.indexOf(id.charAt(s.id
318                 .length())) > -1) : false;
319       }
320       else
321       {
322         return s.id.startsWith(id) ? (s.id.equals(id) ? true : (WORD_SEP
323                 .indexOf(s.id.charAt(id.length())) > -1)) : false;
324       }
325     }
326
327     public boolean equals(String s)
328     {
329       if (id.length() > s.length())
330       {
331         return id.startsWith(s) ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
332                 : false;
333       }
334       else
335       {
336         return s.startsWith(id) ? (s.equals(id) ? true : (WORD_SEP
337                 .indexOf(s.charAt(id.length())) > -1)) : false;
338       }
339     }
340   }
341 }