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